## 10.1 概要

stack や queue のデータの抽象化については、日常の事柄に例えることが出来ます。スタックの良い例は、机の上に積まれた書類や、食器棚の中に重ねられた皿などです。いずれの場合も、重要な事は、一番上にあるものが最も手を伸ばしやすいということです。新しい項目をコレクションに追加する最も簡単な方法は、現在のスタックの上に置くことです。この方法では、スタックから削除される項目は、最後にスタックに挿入された項目となります。上記の例でいえば、一番上にある書類や、一番上に重ねられた皿がそれに当たります。

一方、待ち行列の日常での例は、銀行の窓口や劇場の入口で並んで待っている人の列です。列に新しく加わる人のように、新しい項目は待ち行列の末尾に追加されます。一方、劇場に客が入っていくときのように、構造から削除されるのは先頭の項目からです。待ち行列から削除される順序は、スタックの場合とは逆になります。待ち行列の場合、削除される項目は最も長い時間待ち行列に存在した要素です。

一部の開発者の間では、スタックが LIFO 構造と称され、待ち行列は FIFO 構造と呼ばれます。LIFO は Last In, First Out の略語です。これは最初にスタックから削除されるエントリは、最後に挿入されたエントリであるという意味です。一方、FIFO という用語は、First In, First Out の略語です。これは、最初に待ち行列から削除される要素は、最初に待ち行列に挿入された要素であるという意味です。

標準 C++ ライブラリでは、stack と queue の両方がアダプタであり、実際に値を保持する他のコンテナの一番上に構築されます。stack は vector、list、deque の外側に構築することができ、一方、queue は list または deque のいずれかの一番上に構築することができます。stack または queue のいずれかに保持される要素は、`<` と `==` の両方の演算子を認識する必要があります。

stack と queue のいずれも反復子を定義しないため、1 つずつ値を削除する場合を除いて、コレクションの要素を検証することは不可能です。これらの構造が反復子を実装しないということは、いずれのデータ構造でも、第 IV 部で説明するほとんどの汎用アルゴリズムを使用できないことを意味します。

Copyright (c) 1998, Rogue Wave Software, Inc.
このマニュアルに関する誤りのご指摘やご質問は、電子メールにてお送りください。
OEM リリース, 1998 年 6 月