Skip to content

Files

Latest commit

7f728a0 · Oct 31, 2023

History

History

02_Stack

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Oct 31, 2023
Oct 31, 2023

stack

基本概念と主な特徴:

項目 説明
基本概念 stackはデータ構造の一つで、要素には「後入れ先出し」(Last In First Out, LIFO) の原則に従ってアクセスする。つまり、最後に追加された要素が最初に取り出される。
要素へのアクセス スタック上の最上部の要素のみにアクセスが可能。下にある要素に直接アクセスすることはできない。
要素の追加・削除 要素の追加(プッシュ)や削除(ポップ)はスタックの最上部でのみ行われる。
イテレーション stackはイテレーション(繰り返し処理)を直接サポートしていない。これは、stackがLIFO原則に基づいて設計されているため。
内部実装 stackは実際にはコンテナアダプタとして実装されており、内部実装としてdequevectorなどの他のコンテナを使用している。しかし、その実装の詳細は通常の使用時には気にする必要はない。
パフォーマンス stackのデータの追加や削除は高速である。特に、内部でdequeを使用している場合は、要素の追加や削除が定数時間で行われる。

基本的な操作:

操作 説明
push() スタックの最上部に要素を追加する。 s.push(5);
pop() スタックの最上部の要素を削除する。要素の値を返すわけではないので注意。 s.pop();
top() スタックの最上部の要素を参照する。この操作で要素は削除されない。 int x = s.top();
empty() スタックが空かどうかをチェックする。空の場合はtrue、それ以外はfalseを返す。 if (s.empty()) {...}
size() スタックに格納されている要素の数を返す。 int n = s.size();

queue

基本概念と主な特徴:

項目 説明
データ構造 queueはFIFO (First In, First Out) の原則に基づくデータ構造です。これは最初に追加された要素が最初に取り出されるという原則を意味します。
内部実装 queueは、実際にはデフォルトでdequeというデータ構造を使用して内部的に実装されていますが、他のコンテナでの実装も可能です。
スレッドセーフ 標準のqueueはスレッドセーフではありません。複数のスレッドからの同時アクセスを考慮する場合は、外部のロッキングメカニズムを使用する必要があります。
要素へのアクセス queueでは、先頭と末尾の要素のみにアクセスできます。ランダムアクセスや中間の要素への直接アクセスはサポートされていません。
主な用途 タスクのキューイング、ブレッドファーストサーチ (BFS) のようなアルゴリズムでの使用など、FIFOの原則が適用される場面で使用されます。

基本的な操作:

操作 説明
push() キューの末尾に要素を追加します。 q.push(5); // 5をキューの末尾に追加
pop() キューの先頭の要素を削除します。要素の値は返さないので、取得したい場合は先にfront()を使用します。 q.pop(); // キューの先頭要素を削除
front() キューの先頭の要素を参照します。 int x = q.front(); // キューの先頭要素を取得
back() キューの末尾の要素を参照します。 int y = q.back(); // キューの末尾要素を取得
empty() キューが空であるかどうかをチェックします。空の場合はtrue、そうでない場合はfalseを返します。 if (q.empty()) {...} // キューが空かどうかをチェック
size() キューに含まれる要素の数を返します。 int size = q.size(); // キューの要素数を取得