[Algorithm] 스택(Stack)

1. 개요

스택(Stack)은 한쪽 끝에서만 자료를 넣고 뺼 수 있는 자료구조이다. 마지막으로 넣은 값이 가장 먼저 나오기 때문에 Last In First Out(LIFO) 구조라고 하며, push, pop, top, size, empty 5개의 명령이 존재한다. 예제를 통해 스택(Stack)의 동작 방식에 대해 알아보도록 하자.

• push {값} : 스택에 값을 넣음

• pop : 스택의 맨 위의 값을 뺌

• top : 스택의 맨 위의 값을 반환

• size : 스택의 크기 반환

• empty : 스택이 비어있는지 여부 반환(비어있으면 true, 비어있지 않으면 false)

2. 예제

1. 명령 : empty / 반환값 : true

   스택이 비어있으므로 true를 반환한다.

   

2. 명령 : push 2 / 반환값 : X

   스택의 빈 공간 중 가장 아래에 2를 넣는다.

   

3. 명령 : push 5 / 반환값 : X

   스택의 빈 공간 중 가장 아래에 5를 넣는다.

   

4. 명령 : push 7 / 반환값 : X

   스택의 빈 공간 중 가장 아래에 7을 넣는다.

   

5. 명령 : top / 반환값 : 7

   스택의 맨 위의 값인 7을 반환한다.

   

6. 명령 : pop / 반환값 : X

   스택의 맨 위의 값인 7을 뺀다.

   

7. 명령 : top / 반환값 : 5

   스택의 맨 위의 값인 5를 반환한다.

   

8. 명령 : size / 반환값 : 2

   스택에 들어있는 값의 크기(갯수)를 반환한다.

   

9. 명령 : empty / 반환값 : false

   스택이 비어있지 않으므로 false를 반환한다.

   

3. 구현 코드

3-1. C++

3-1-1. 구현

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/stack.cpp

#include <iostream>
#include <vector>

using namespace std;

vector<int> v;

int main(void) {
    ios_base::sync_with_stdio(false);
    int n; for (cin >> n; n--;) {
        string cmd; cin >> cmd;
        if (cmd == "push") {
            int num; cin >> num;
            v.push_back(num);
        } else if (cmd == "pop") {
            if (v.size() != 0) {
                cout << v.back() << "\n";
                v.pop_back();
            } else {
                cout << "-1" << "\n";
            }
        } else if (cmd == "size") {
            cout << v.size() << "\n";
        } else if (cmd == "empty") {
            cout << (v.size() ? 0 : 1) << "\n";
        } else if (cmd == "top") {
            cout << (v.size() ? v.back() : -1) << "\n";
        }
    }
    return 0;
}

[실행 결과]

3-1-2. 라이브러리 이용

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/stack2.cpp

#include <iostream>
#include <stack>

using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    stack<int> s;
    int n; for (cin >> n; n--;) {
        string cmd; cin >> cmd;
        if (cmd == "push") {
            int num; cin >> num;
            s.push(num);
        } else if (cmd == "pop") {
            if (s.size() != 0) {
                cout << s.top() << "\n";
                s.pop();
            }
            else {
                cout << "-1" << "\n";
            }
        } else if (cmd == "size") {
            cout << s.size() << "\n";
        } else if (cmd == "empty") {
            cout << s.empty() << "\n";
        } else if (cmd == "top") {
            cout << (s.size() ? s.top() : -1) << "\n";
        }
    }
    return 0;
}

[실행 결과]

3-2. JAVA

3-2-1. 구현

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/stack.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class StackExample {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int arr[] = new int[10003];
        int size = 0;
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; ++i) {
            String cmd = br.readLine();
            StringTokenizer st = new StringTokenizer(cmd);
            if(st.nextToken().equals("push")) {
                int num = Integer.parseInt(st.nextToken());
                arr[size++] = num;
            } else if(cmd.equals("pop")) {
                if(size != 0) {
                    sb.append(arr[size - 1]).append("\n");
                    arr[(size--) - 1] = 0;
                } else {
                    sb.append("-1").append("\n");
                }
            } else if(cmd.equals("size")) {
                sb.append(size).append("\n");
            } else if(cmd.equals("empty")) {
                sb.append(size == 0 ? 1 : 0).append("\n");
            } else if(cmd.equals("top")) {
                sb.append(size == 0 ? -1 : arr[size - 1]).append("\n");
            }
        }
        System.out.println(sb);
    }
}

[실행 결과]

3-2-2. 라이브러리 이용

[소스 코드]

https://github.com/dev-aiden/problem-solving/blob/main/algorithm/stack2.java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class StackExample {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        Stack<Integer> s = new Stack<>();
        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; ++i) {
            String cmd = br.readLine();
            StringTokenizer st = new StringTokenizer(cmd);
            if(st.nextToken().equals("push")) {
                int num = Integer.parseInt(st.nextToken());
                s.push(num);
            } else if(cmd.equals("pop")) {
                if(s.size() != 0) {
                    sb.append(s.peek()).append("\n");
                    s.pop();
                } else {
                    sb.append("-1").append("\n");
                }
            } else if(cmd.equals("size")) {
                sb.append(s.size()).append("\n");
            } else if(cmd.equals("empty")) {
                sb.append(s.empty() ? 1 : 0).append("\n");
            } else if(cmd.equals("top")) {
                sb.append(s.size() != 0 ? s.peek() : -1).append("\n");
            }
        }
        System.out.println(sb);
    }
}

[실행 결과]