[DS] Stack 스택

Introduction

스택이란 작업이 특정 순서로 이루어지는 선형 자료 구조 입니다. 여기서 말하는 특정 순서란 일반적으로 LIFO(Last In First Out) 또는 FILO(First In Last Out)입니다. 마지막으로 들어온 데이터가 가장 먼저 나가거나 가장 먼저 들어온 데이터가 가장 나중에 나간다, 결국 같은 말입니다. 스택의 실생활 예시(real life examples)는 굉장히 많은데, 가장 유명한 예는 '쌓여있는 접시들' 예가 있습니다. 다음으로 놓을 접시는 가장 밑이 아니라 가장 위로 놓아야 하고, 다음으로 꺼내올 접시 또한 가장 위에서 꺼내야하죠. 그리고 가장 밑에 있는 접시가 가장 오랬동안 존재하게되죠.  

<스택의 간단한 그림>

Basic operations

스택의 핵심은 주로 다음 네가지 작업을 말합니다(영어 단어의 느낌을 살려서 이해하시면 좋습니다).

- push: 스택에 아이템을 집어 넣습니다. 스택이 가득 찼다면, Overflow 상태가 됩니다. (cf.유명 프로그래밍 질문 사이트 Stack overflow도 여기에서 따온 이름입니다 ^^)

- pop: 스택에서 아이템 하나를 제거합니다. 아이템은 push된 순서와 반대로 pop됩니다. 

- peek or top: 스택의 제일 위의 아이템을 리턴합니다. 

- isEmpty: 스택이 비어있으면 true, 아니면 false를 리턴합니다.

Complexity

push(), pop(), isEmpty(), top()은 모두 O(1)입니다.

Application

- Infix to Postfix / Prefix 변환

- 포토샵 같은 편집툴에서 Redu-Undo 기능

- 웹 브라우저에서 앞으로가기, 뒤로기가 기능

- Tower of Hanoi, tree traversals, stock span problem, histogram problem

- Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver

- In Graph Algorithms like Topological Sorting and Strongly Connected Components

Implementation

C++ Array 이용

#include <iostream>
using namespace std;
 
#define MAX 1000
 
class Stack {
    int top;
 
public:
    int a[MAX]; // 스택의 최대 크기
 
    Stack() {
        top = -1;
    }
    bool push(int x);
    int pop();
    bool isEmpty();
};
 
bool Stack::push(int x) {
    if (top >= (MAX-1)){
        cout << "Stack Overflow";
        return false;
    }else {
        a[++top] = x;
        cout << x << " pushed into stack\n";
        return true;
    }
}
 
int Stack::pop(){
    if (top < 0) {
        cout << "Stack Underflow";
        return 0;
    } else {
        int x = a[top--];
        return x;
    }
}
 
bool Stack::isEmpty() {
    return (top < 0);
}
 
int main() {
    struct Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.pop() << " Popped from stack\n";
 
    return 0;
}

Colored by Color Scripter

output

10 pushed into stack 
20 pushed into stack 
30 pushed into stack 
30 popped from stack

C++ LinkedList 이용

#include <iostream>
using namespace std;
 
class UnderflowException{};
 
template<typename T>
class Node {
public:
    T value;
    Node<T> *next;
 
    Node<T>(T v, Node<T> *n): value(v), next(n){}
};
 
template<typename T>
class Stack {
public:
    int size;
    Node<T> *head;
 
    // 생성자
    Stack<T>(): size(0), head(nullptr){}
 
    // 소멸자
    ~Stack<T>() {
        Node<T> *t1 = head, *t2;
        while(t1 != nullptr) {
            t2 = t1->next;
            delete t1;
            t1 = t2;
        }
    }
 
    void push(T value) {
        head = new Node<T>(value, head); // 맨 위에 새 원소 삽입
        size++;
    }
 
    T top() {
        try {
            if(size == 0) throw UnderflowException();
            return head->value;
        }
        catch (UnderflowException e) {
            cerr << "스택이 비어있는데 top 연산을 시도했습니다." << endl;
            exit(1);
        }
    }
 
    int pop() { // 맨 위의 원소 제거
        try {
            // 예외 처리: 스택이 비어있는 경우
            if (size == 0) throw UnderflowException();
            Node<T> *temp = head->next;
            delete head;
            head = temp;
            size--;
        }
        catch (UnderflowException e) {
            cerr << "스택이 비어있는데 pop 연산을 시도했습니다." << endl;
            exit(2);
        }
    }
};
 
template<typename T>
ostream& operator <<(ostream &out, const Stack<T> &LL){ // 원소들을 한 줄에 차례대로 출력
    Node<T> *temp = LL.head;
    out << "top [";
    for(int i=0; i<LL.size; i++){
        out << temp->value;
        temp = temp->next;
        if(i < LL.size-1) out << ", ";
    }
    out << "] bottom";
    return out;
}
 
int main() {
    Stack<int> S;
    S.push(0); cout << S << endl;
    S.push(1); cout << S << endl;
    S.push(2); cout << S << endl;
    S.pop(); cout << S << endl;
    S.push(4); cout << S << endl;
    S.pop(); cout << S << endl;
    S.push(5); cout << S << endl;
    S.pop(); cout << S << endl;
    S.pop(); cout << S << endl;
    S.pop(); cout << S << endl;
}
 

output

top [0] bottom
top [1, 0] bottom
top [2, 1, 0] bottom
top [1, 0] bottom
top [4, 1, 0] bottom
top [1, 0] bottom
top [0] bottom
스택이 비어있는데 pop 연산을 시도했습니다.
top [5, 0] bottom
top [0] bottom
top [] bottom

LinkedList 이용 도식화 그림

References

https://defacto-standard.tistory.com/200#comment12037075

https://www.geeksforgeeks.org/stack-data-structure-introduction-program/

제 글이 도움이 되셨다면 간단하게 '공감', '댓글' 부탁드립니다!