2021-06-03 · 3분

データ構造 — スタック

algorithm

この記事は公開から2年以上経過しています。

BOJ #10828 スタック問題：https://www.acmicpc.net/problem/10828

スタックとは？

スタック（Stack）は制限的にアクセスできる並び構造である。片方の端でのみデータを入れたり出したりできる LIFO（Last In First Out）形式のデータ構造である。

スタックの機能

いろいろあるが、最もよく使うものである。

pop()：スタックの一番上にある項目を削除する。
push(input)：input という変数をスタックの一番上に追加する。
size()：スタックに入っているサイズを教える。
top()：スタックの一番上の部分を返す（削除しない）。
empty()：スタックが空のとき true を返す。

なぜスタックを使うのか？

問題の種類によっては、配列よりスタックにデータを保存するほうが適した方法であることがある。

配列と違い、その位置にアクセスできない。
スタックでデータを追加・削除する演算は定数時間で可能である。
配列をスタックのように使うには、配列から要素を抜くたびに横にずらす必要があるが、スタックではその必要がない。

スタックの実装

BOJ #10828 スタック問題

#include<stdio.h>
#include<string.h>
 
#define TRUE 1            
#define FALSE 0           
#define MINUS -1          
#define MAX_SIZE 10000    
 
typedef struct _stack{    
    int arr[MAX_SIZE];
    int top;
} Stack;
 
void StackInit(Stack * sp){    
    sp->top = -1;
}
 
int IsEmpty(Stack * sp){    
    if(sp->top == -1) return TRUE;
        
    return FALSE;
}
 
int Size(Stack *sp){    
    return sp->top + 1;
}
 
 
int IsFull(Stack * sp){        
    if(sp->top + 1 >= MAX_SIZE) return TRUE;
    
    return FALSE;
}
 
void Push(Stack * sp, int data){    
    if(IsFull(sp)==TRUE) return;
    
    sp->arr[++(sp->top)] = data;    
}
 
int Pop(Stack * sp){    
    if(IsEmpty(sp) == TRUE) return MINUS;
 
    return sp->arr[(sp->top)--];
}
 
int Peek(Stack *sp){    
    if(IsEmpty(sp) == TRUE) return MINUS;
    
    return sp->arr[sp->top];
}
 
 
int main(void){
    int i;
    char str[6];
    Stack stack;
    int n, num;
    
    scanf("%d", &n);
    fgetc(stdin);    
    StackInit(&stack);    
    
    
    for(i=0; i<n; i++){
    
        scanf("%s", str);
        fgetc(stdin);    
 
        if(!strcmp(str, "push")){    
            
            scanf("%d", &num);
            fgetc(stdin);    
            Push(&stack, num);    
            
        }else if(!strcmp(str, "pop")){    
        
            printf("%d\n", Pop(&stack));
        
        }else if(!strcmp(str, "empty")){    
            
            printf("%d\n", IsEmpty(&stack));
            
        }else if(!strcmp(str, "size")){        
        
            printf("%d\n", Size(&stack));
        
        }else if(!strcmp(str, "top")){        
        
            printf("%d\n", Peek(&stack));
        
        }
    }
    
    
    return 0;    
}

直接このように作って使うこともできるが、c++ には stack というヘッダが存在する。

これは上の問題の答えではなく、stack というヘッダを使うときこのようにできるということである。

#include <stdio.h>
#include <string.h>
#include <stack>

using namespace std;

stack<int> Stack;

int main()
{
    int i;
    char str[7];
    int n, num;

    scanf("%d", &n);
    fgetc(stdin);

    for (int i = 0; i < n; i++)
    {
        scanf("%s", str);
        fgetc(stdin);

        if(!strcmp(str, "push")) {
            scanf("%d", &num);
            fgetc(stdin);
            Stack.push(num);
        }else if(!strcmp(str, "pop")) {
            if(Stack.empty()) printf("-1\n");
            else {
                printf("%d\n", Stack.top());
                Stack.pop();
            }
        }else if(!strcmp(str, "empty")) {
            if(Stack.empty()) printf("1\n");
            else printf("0\n");
        }else if(!strcmp(str, "size")) {
            printf("%ld\n", Stack.size());
        }else if(!strcmp(str, "top")) {
            printf("%d\n", Stack.top());
        }
    }
    
}

STL stack の使い方

// stack ヘッダを追加
#include <stack>

// 空の stack を生成
stack<int> Stack;

// {1, 2, 3, 4, 5} で初期化された stack を生成
stack<int> Stack({ 1, 2, 3, 4, 5 });

stack の関数たち

stack<int> Stack を基準として

Stack.push(n)：一番上に n を追加
Stack.pop()：一番上の要素を削除
Stack.top()：一番上の要素を返す
Stack.size()：スタックのサイズを返す
Stack.empty()：空かどうか確認

スタックを利用した問題解法：

**[アルゴリズム] - BOJ #9012 括弧**](https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html) 参照：https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D https://velog.io/@choiiis/C-STL-stack-%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%A0%95%EB%A6%AC [https://gmlwjd9405.g — data-structure-stack.html

写真：http://www.incodom.kr/%EC%8A%A4%ED%83%9D