データ構造（スタックとキュー）に関する世界観です。
| データ構造 | 意味 |
|---|---|
| スタック | 最後に入れたものが最初に取り出される。 どんどん上に重ね、上から取る。 スタックにデータを積む操作をプッシュ、取り出す操作をポップという。 |
| キュー | 最初に入れたものが最初に取り出される。 列に並んで、最初に並んだ人から順に待機する。 キューに入れる操作をエンキュー、取り出す操作をデキューという。 |
（Ruby Way 第2版 (Professional Ruby Series)を参考に執筆しました。）
メッセージキューも参照のこと。
スタックとキューは、さまざまな場面で使われます。
特に、スタックは非常に一般的で、たとえばカッコを処理する際に、最後に開いたカッコが最初に閉じたカッコに対応します。
このように、「最後が最初に対応する」という場面は、意外と多く、そのため、スタックはさまざまな用途に使われます。
一方キューについては、カーネルのような低レベルレイヤーやプリンターのようなデバイス処理の中で、サブシステム同士を繋ぐインターフェースとして使うことが多いです。
特に、効率的な処理と非効率的な処理が一緒になる時に、非同期で処理をやり取りするような場合に、キューは使われることが多いです。
たとえば、Linuxのファイルシステムの中の、ダーティビットが付けられたi-nodeを順次書き込むために使われる、I/Oリクエストキューなどがこれに当たります。
そのように、スタックやキューはわりとよく使われます。配列や連結リストやツリーなど、単純なデータ構造よりも、少し癖のある形で使われるので、習得や理解は難しいですが、それらのデータ構造と同じぐらいよく使われるデータ構造だと言えます。
2023.07.28
Perl, PHP, Python, Rubyなどでは、リストに対してポップやプッシュなどのスタックやキューとしての操作を行うことができる。
Perl、PHP（言語）、Python（データ構造）、Ruby（基本）などを参照のこと。
2023.09.05
C言語でスタックを作るのは、意外と簡単です。
まず、スタックのアドレスを保持するスタックポインタを作り、スタックの値として配列を確保します。
その上で、スタックポインタをインクリメントして配列の最後に値を追加するpush()関数と、スタックポインタをデクリメントして値を配列の最後から削除してreturnで返すpop()関数を作ればいいのです。
キューも同様の方法で作れますが、キューを作る際にはシフト（全体をひとつずつずらす操作）が必要となるので、効率的なキューを作るのは難易度が高めです。
詳しくは以下の書籍に書かれているので、参照してください。
2024.08.15
Cでキューを実装する場合、配列を用いて実装しようとすると、メモリをできるだけ効率的に確保するようにしたいなら、両端のどちらかの端で要素を追加・削除する際にシフト操作（要素を全部ひとつひとつずらす操作）が必要となるため、効率的な実装ができません。
このような場合、メモリを余剰分に確保する方法もありますが（キューの要素数の最大数が決まっていて、その数が大きすぎないのであれば、それもいいでしょう）、配列ではなく連結リストを使うことで、要素を追加・削除する際に要素とともにポインタによる紐づけを追加・削除するだけで済みます。
なので、効率的なキューを実装したいなら、配列ではなく連結リストを使うといいでしょう。
と、ここまで配列によるキューを否定する内容を書きましたが、「Code Reading」という書籍によると、リングバッファ（循環バッファ）という方法で、配列でも効率的なキューを実装できるようです。
リングバッファにおいては、配列インデックスを追加する位置と削除する位置の二つ持ちます。追加する末尾の位置をテール、削除する先頭の位置をヘッドとします（あるいはその逆でもいい）。そして、配列インデックスが配列の終端の位置に達したら、配列の先頭の位置に戻ります。そのようにすることで、配列でも効率的なキューを実装できます。
後日注記：両終端キュー（前と後ろどちらの端にも要素を追加したり削除したりできるキューで、dequeとも呼ばれる）では、ダブル連結リスト（前にも後ろにもリンクされたリスト）がよく使われます。
2024.10.31
2025.08.12編集
以下はGoogleのAIが書いたスタックとキューのサンプルコード。
スタックの実装：
#include <stdio.h>
#define SIZE 5
int stack[SIZE];
int top = -1; // スタックのトップ位置
// スタックにデータを追加
void push(int data) {
if (top >= SIZE - 1) {
printf("Stack Overflow! (スタック満杯)\n");
} else {
stack[++top] = data;
printf("%d をプッシュしました。\n", data);
}
}
// スタックからデータを取り出し
int pop() {
if (top < 0) {
printf("Stack Underflow! (スタック空)\n");
return -1;
} else {
return stack[top--];
}
}
int main() {
push(10);
push(20);
push(30);
printf("ポップ: %d\n", pop()); // 30が出る
printf("ポップ: %d\n", pop()); // 20が出る
return 0;
}
キューの実装：
#include <stdio.h>
#define SIZE 5
int queue[SIZE];
int front = 0;
int rear = 0; // データを入れる位置
// キューにデータを追加
void enqueue(int data) {
if ((rear + 1) % SIZE == front) {
printf("Queue Full! (キュー満杯)\n");
} else {
queue[rear] = data;
rear = (rear + 1) % SIZE;
printf("%d をエンキューしました。\n", data);
}
}
// キューからデータを取り出し
int dequeue() {
if (front == rear) {
printf("Queue Empty! (キュー空)\n");
return -1;
} else {
int data = queue[front];
front = (front + 1) % SIZE;
return data;
}
}
int main() {
enqueue(1);
enqueue(2);
enqueue(3);
printf("デキュー: %d\n", dequeue()); // 1が出る
printf("デキュー: %d\n", dequeue()); // 2が出る
return 0;
}
2026.02.05
以下の書籍を参考に執筆しました。