うさぎでもわかるスタックとキュー

2020年1月13日 2022年2月10日 19分36秒

ももうさ

スポンサードリンク

こんにちは、ももやまです。

今回は基本情報に頻出するデータ構造の「スタック」と「キュー」についてまとめていきたいと思います。

なお、他に重要なデータ構造として「配列」と「リスト」があります。

「配列」、「リスト」については下の記事にまとめているのでそちらをご覧ください！

www.momoyama-usagi.com

目次 [hide]

１．スタック
２．キュー
３．リングバッファ（応用）
４．スタックの実装
５．キュー（リングバッファ）の実装
６．練習問題
７．練習問題の答え
８．さいごに

スポンサードリンク

１．スタック

スタックは、下の図のように新しいデータから順番にデータを取り出すことができるデータ構造です。

上の図の場合、「データ4→データ3→データ2→データ1」の順に取り出します。

日常生活で例えると、Chromeなどのブラウザにある「戻るボタン」がまさにスタックです。
（戻るボタンを押すと直前見ていたページに移動し、さらに連打するとどんどん古い履歴にさかのぼっていきますね。）

スタックにデータを入れることをpush、一番新しいデータを取り出すことをpopと呼びます。

後に入ったものから順に取り出すのでLIFO(Last In Fist Out)と呼ぶ人もいます。

スポンサードリンク

２．キュー

キューは、下の図のように古いデータから順番にデータを取り出すことができるデータ構造です。

上の図の場合、「データ1→データ2→データ3→データ4」の順に取り出します。

日常生活でたとえると、ライブ会場などにできる行列がまさにキューです。
（先に並んだ人から順番に会場に入れますよね*1。）

キューにデータを入れることをenqueue、一番古いデータを取り出すことをdequeueと呼びます。

先に入ったものから順に取り出すので FIFO(First In First Out) と呼ぶ人もいます。

ここでスタックとキューの違いを簡単に復習しましょう。

スタックとキュー

スタック：新しいデータから順に取り出せるデータ構造
(LIFO Last In Last Out)

キュー：古いデータから順に取り出せるデータ構造
(FIFO First In Last Out)

スポンサードリンク

３．リングバッファ（応用）

queueが環状ではない場合、enqueue、dequeueを繰り返しているとデータに空きがあっても追加できなくなっています。そこで、下の図のようにキューを環状と考えることでデータに空きがあれば何回でも enqueue, dequeueができるようにしています。

上のような環状のキューのことをリングバッファと呼びます。

なお、基本情報にはあまりリングバッファは出てこないのでさらーと流してOKです。

４．スタックの実装

C言語でのスタックの実装例を紹介したいと思います。具体的には、

構造体スタックの定義
push, pop などの関数定義
実際にmain内で push, pop させて動作確認する

の3点を実装しています。

※ エラー処理まではしていませんのでご了承ください。本当は pushしすぎによる配列オーバーで Segmentation Fault などのエラーが発生しないように対策するのが理想です。

#include<stdio.h>
#define SIZE  10 // スタックサイズ
 
// スタック用構造体
struct STACK {
    int elm[SIZE]; // 各要素
    int top; // データがどの場所まであるかを記憶
} ;
 
// 初期化関数　STACKがポインタなのは参照渡しにするため
void init(struct STACK *s) {
    s->top = -1; // スタックが空 -> -1
}
 
// 出力関数　STACKがポインタなのは参照渡しにするため
void print(struct STACK *s){
    printf("スタックの中身:");
    for(int i = 0; i <= s->top; i += 1) {
        printf("%d ",s->elm[i]);
    }
    printf("\n");
}
 
// push関数　STACKが（以下省略）
void push(int x, struct STACK *s){
    s->top += 1; // データの場所が1つ増やす
    s->elm[s->top] = x; // 要素格納
}
 
// pop関数　
int pop(struct STACK *s){
    int out_data = s->elm[s->top]; // 出力する要素
    s->top -= 1; // データの場所が1つ減る
    return out_data;
}
 
// スタックが空か判定
int isEmpty(struct STACK *s){
    if(s->top != -1) {
        return 0;
    }
    else {
        return 1;
    }
}
 
int main() {
    struct STACK s;
    init(&s); // 初期化
 
    push(10,&s); // スタックの中身 10
    push(20,&s); // スタックの中身 10 -> 20
    push(30,&s); // スタックの中身 10 -> 20 -> 30
    print(&s);
 
    printf("pop: %2d\n",pop(&s)); // スタックの中身 10 -> 20
    printf("pop: %2d\n",pop(&s)); // スタックの中身 10
    push(40,&s); // スタックの中身 10 -> 40
    print(&s);
 
    // スタックが空になるまでひたすらpop
    while(! isEmpty(&s)) {
        printf("pop: %2d\n",pop(&s));
    }
 
    return 0;
}

上のプログラムを実行すると、実行結果は

スタックの中身:10 20 30
pop: 30
pop: 20
スタックの中身:10 40
pop: 40
pop: 10

となります。

スタック型の構造体は参照渡しにするため、関数定義のところでポインタ引数としています。

（※ 参照渡しってなんだっけと思った人 or 全然わからない人はこちらの記事で確認することをおすすめします）

５．キュー（リングバッファ）の実装

C言語でのキューの実装例を紹介したいと思います。

構造体キューの定義
リングバッファでの実装
enqueue, dequeue などの関数定義
実際にmain内で enqueue, dequeue させて動作確認する

の4点を実装しています。

※ エラー処理まではしていませんのでご了承ください。本当は enqueue しすぎによる配列オーバーで Segmentation Fault などのエラーが発生しないように対策するのが理想です。

#include<stdio.h>
#define SIZE 5
 
struct QUEUE {
    int elm[SIZE]; // データの中身
    int start;     // キューのデータの始まり
    int end;       // キューのデータの終わり
} ;
 
// 初期化関数　QUEUEがポインタなのは参照渡しにするため
void init(struct QUEUE *q) {
    q->start = 0;
    q->end = 0;
}
 
// キューを環状と考え、次のキューの場所を計算する関数
// Ex. SIZE = 5 のとき、3番目の次は4番目、4番目の次は0番目
int nextStep(int x) {
    return (x + 1) % SIZE;
}
 
// キュー内のデータ出力関数　QUEUEがポインタなのは参照渡しにするため
void print(struct QUEUE *q){
    printf("キューの中身:");
    for(int i = q->start; i != q->end; i = nextStep(i)) {
        printf("%d ",q->elm[i]);
    }
    printf("\n");
}
 
// enqueue関数　QUEUEが（以下省略）
void enqueue(int x, struct QUEUE *q){
    q->elm[q->end] = x;
    q->end = nextStep(q->end);
}
 
// dequeue関数　
int dequeue(struct QUEUE *q){
    int out_data = q->elm[q->start];
    q->start = nextStep(q->start);
    return out_data;
}
 
// キューが空かどうかを判定
int isEmpty(struct QUEUE *q){
    if(q->start != q->end) {
        return 0;
    }
    else {
        return 1;
    }
}
 
 
int main() {
    struct QUEUE q;
    init(&q); // 初期化
 
    enqueue(10,&q); // キューの中身 10
    enqueue(20,&q); // キューの中身 10 -> 20
    enqueue(30,&q); // キューの中身 10 -> 20 -> 30
    print(&q);
 
    printf("dequeue: %2d\n",dequeue(&q)); // キュー中身 20 -> 30
    printf("dequeue: %2d\n",dequeue(&q)); // キューの中身 30
 
    enqueue(40,&q); // キューの中身 30 -> 40
    enqueue(50,&q); // キューの中身 30 -> 40 -> 50
    enqueue(60,&q); // キューの中身 30 -> 40 -> 50 -> 60
 
    print(&q);
 
    // スタックが空になるまでひたすらpop
    while(! isEmpty(&q)) {
        printf("dequeue: %2d\n",dequeue(&q));
    }
 
    return 0;
}

上のプログラムを実行すると実行結果は、

キューの中身:10 20 30
dequeue: 10
dequeue: 20
キューの中身:30 40 50 60
dequeue: 30
dequeue: 40
dequeue: 50
dequeue: 60

となります。

スタックのときと同じく、キューの構造体は参照渡しにするため、関数定義のところでポインタ引数としています。

６．練習問題

では、少しスタックとキューの練習として基本情報や応用情報の問題を解いていきましょう。

なお、基本情報の問題

練習1

キューに関する記述として，最も適切なものはどれか。
[基本情報技術者平成27年春期午前問5]

ア：最後に格納されたデータが最初に取り出される。
イ：最初に格納されたデータが最初に取り出される。
ウ：添字を用いて特定のデータを参照する。
エ：二つ以上のポインタを用いてデータの階層関係を表現する。

練習2

空の状態のキューとスタックの二つのデータ構造がある。次の手続を順に実行した場合、変数xに代入されるデータはどれか。ここで、手続きに引用している関数は次のとおりとする。

[基本情報技術者平成24年秋期午前問5]

★関数の定義★

push(y) : データyをスタックに積む。
pop()   : データをスタックから取り出して，その値を返す。
enq(y)  : データyをキューに挿入する。
deq()   : データをキューから取り出して，その値を返す。

★手続★

push(a)
push(b)
enq(pop())
enq(c)
push(d)
push(deq())
x ← pop()

ア：a
イ：b
ウ：c
エ：d

練習3

四つのデータA，B，C，Dがこの順に入っているキューと空のスタックがある。手続pop_enq，deq_pushを使ってキューの中のデータをD，C，B，Aの順に並べ替えるとき、deq_push の実行回数は最小で何回か。ここで、pop_enqはスタックから取り出したデータをキューに入れる操作であり、deq_pushはキューから取り出したデータをスタックに入れる操作である。

[基本情報技術者平成24年秋期午前問5]

ア：2
イ：3
ウ：4
エ：5

練習4

PUSH命令でスタックにデータを入れ、POP命令でスタックからデータを取り出す。動作中のプログラムにおいて、ある状態から次の順で10個の命令を実行したとき、スタックの中のデータは図のようになった。1番目のPUSH命令でスタックに入れたデータはどれか。

[応用情報技術者平成23年特別午前問7]

ア：29
イ：7
ウ：326
エ：55

７．練習問題の答え

解答1

解答：イ

それぞれの選択肢ごとの解説

ア：最後に格納されたデータを取り出すのはスタック。
イ：大正解！
ウ：添字を用いるのは配列
エ：ポインタで階層関係を表現するのはリスト

解答2

解答：イ

★処理過程★

push(a)     # スタックにaを入れる　スタック [a]
push(b)     # スタックにbを入れる　スタック [a,b]
enq(pop())  # スタックからbを取り出し、キューへ入れる　スタック [a],  キュー [b]
enq(c)      # キューにcを入れる　キュー [b,c]
push(d)     # スタックにdを入れる　スタック [a,d]
push(deq()) # キューからbを取り出し、スタックに入れる　 キュー [c],  スタック [a,d,b]
x ← pop()   # スタックからbを取り出す

よって x はbとなるので答えはイ。

解答3

解答：イ

ウ（4回）と引っかからないように!!

（データDは deq_push しなくても並び替えることができます！）

初期状態　キュー [A,B,C,D]　スタック  []
deq_push(1回目)　キュー [B,C,D]　スタック　[A]  (Aをスタックに)
deq_push(2回目)　キュー [C,D]　スタック　[A,B] (Bをスタックに)
deq_push(3回目)　キュー [D]　スタック　[A,B,C] (Cをスタックに)
pop_enq(1回目)　キュー [D,C]　スタック　[A,B] (Cをキューに)
pop_enq(2回目)　キュー [D,C,B]　スタック　[A] (Bをキューに)
pop_enq(3回目)　キュー [D,C,B,A]　スタック　[] (Aをキューに)

とすることで D→C→B→A の順番にすることができる。

よって答えは3回となりイ。

解答4

解答：イ

今までの問題パターンとは逆で、操作を遡る必要があるので少しむずかしいかもしれません。

落ち着いて操作を巻き戻していきましょう。

操作順のメモ
push → push → pop → push → push
→ push → push → pop → pop → push

10個目の操作push：192をpush
→ 10個目の操作前のスタックの中身 [29, 7, 326, 55]

9個目の操作pop：何かしらの値 x をpopした
→ 9個目の操作前のスタックの中身 [29, 7, 326, 55, x]

8個目の操作pop：何かしらの値 y をpopした
→ 8個目の操作前のスタックの中身 [29, 7, 326, 55, x, y]

7個目の操作push：yをpush
→ 7個目の操作前のスタックの中身 [29, 7, 326, 55, x]

6個目の操作push：xをpush
→ 6個目の操作前のスタックの中身 [29, 7, 326, 55]

5個目の操作push：55をpush
→ 5個目の操作前のスタックの中身 [29, 7, 326]

4個目の操作push：326をpush
→ 4個目の操作前のスタックの中身 [29, 7]

3個目の操作pop：なにかしらの値 z をpop
→ 5個目の操作前のスタックの中身 [29, 7, z]

2個目の操作push：z をpush
→ 5個目の操作前のスタックの中身 [29, 7]

1個目の操作push：7 をpush（これが答え！！）
→ 1個目の操作前のスタックの中身 [29]

よって答えは7のイとなります！

すごい余談でしたが今回の練習問題の答えが全部「イ」でしたね……()

８．さいごに

今回は基本情報、応用情報に頻出するスタックとキューについてまとめていきました。

最後にスタックとキューのデータの出し入れの様子を同時にアニメーションしたもので取り出し方の違いを確認しましょう。

これで配列、連結リスト、スタック、キューの4つの基本データ構造について説明は終わりです！

次回は線形探索、二分探索についてまとめていきたいと思います。

それでは、さらば！

*1:割込みしてくる人がいなければ。

関連広告・スポンサードリンク

この記事を書いた人

ももうさ

数学と情報が得意な元工業大生（院卒）です。数学科目と情報科目をわかりやすく説明するブログを書いてます！