このページには最新のブラウザ(SharedArrayBuffer対応)が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
項目を保持する2つの方法
- スタックとキューはどちらも一連の項目を保持しますが、次に取り出される項目の違いがあります。
- スタックは LIFO(Last In, First Out)です。皿の山のように、最後に入れたものが最初に出ます。
- キューは FIFO(First In, First Out)です。行列のように、最初に並んだものが最初に出ます。
ス塔はLIFOである
- push は頂点に項目を追加します。pop は頂点の項目を取り出して返します。peek は取り出さずに頂点を参照します。
- 最後に入れた項目が最初に取り出されます。
- 項目を配列
dataに格納し、topに個数を保持します。
配列 backed スタック
topを個数とし、頂点の項目はdata[top - 1]にあります。- push:
data[top]に書き込み、次にtop++を増やす。pop:top--を減らし、次にdata[top]を返す。 - (これらのタスクでは配列に十分な大きさがあります。「full」のチェックは不要です)。
キューはFIFOである
- enqueue は末尾に項目を追加します。dequeue は先頭の項目を取り出して返します。
- 最初に入れた項目が最初に取り出されます。
- 2つのインデックスを保持します:
front(次に取り出す位置)とback(次の空きスロット)。
配列 backed キュー
- enqueue:
data[back]に書き込み、back++を増やします。dequeue:data[front]を読み取り、front++を増やし、それを返します。 - 項目が入ったり出たりするたびに、
frontがbackを追跡します。 - (これらのタスクでは配列に十分な大きさがあります。「wrap around」や「empty」のチェックは不要です)。
よくあるミス
- スタックは LIFO、キューは FIFO です。
- pop や dequeue する前に、構造体が空でないか確認してください。
あなたも試してみよう
StackとQueueの構造体はスタートアップで与えられています。s->top、q->front、q->backを使用してください。mainを書かないでください;チェックツールが用意します。
探索
スタックとキュー
A stack is LIFO; a queue is FIFO. Step through the operations.
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
The Stack struct (with data and a count top) is given. Complete void push(Stack *s, int v) かつ int pop(Stack *s) so the stack is LIFO. Do ~ではない write a main.
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
The Stack struct is given. Complete int peek(const Stack *s) so it returns the top item without removing it. Assume the stack is not empty. Do ~ではない write a main.
実行ボタンをクリックして出力を確認してください。
難易度 4/5 · 280 コイン + 今日初回達成時の小ボーナス
The Queue struct (with data, front, and back) is given. Complete void enqueue(Queue *q, int v) かつ int dequeue(Queue *q) so the queue is FIFO. Do ~ではない write a main.
実行ボタンをクリックして出力を確認してください。