스택 · 알고리즘 노트

개념

스택은 가장 나중에 삽입한 원소를 먼저 제거하는 후입선출(LIFO) 자료구조입니다. 삽입과 제거는 한쪽 끝인 top에서 수행합니다.

원소 추가

아래에서부터 $10,20,30,40,50$ 이 들어 있는 스택에 $60$ 을 추가합니다. 현재 top은 $50$ 입니다.

▲ [그림 1] 스택의 원소 추가 — 연산 전

$60$ 이 $50$ 위에 들어가고, 새 원소 $60$ 이 top이 됩니다.

▲ [그림 2] 스택의 원소 추가 — 연산 후

원소 삭제

$10,20,30,40,50,60$ 을 차례로 넣은 스택에서 원소를 하나 꺼냅니다.

▲ [그림 3] 스택의 원소 제거 — 연산 전

가장 나중에 넣은 $60$ 이 제거되고, 바로 아래에 있던 $50$ 이 새로운 top이 됩니다.

▲ [그림 4] 스택의 원소 제거 — 연산 후

언어별 사용법

동작	C++ `stack`	Java `ArrayDeque`	Python `list`
넣기	`push(x)`	`push(x)`	`append(x)`
맨 위 읽기	`top()`	`peek()`	`[-1]`
꺼내기	`pop()`	`pop()`	`pop()`
빈 상태 확인	`empty()`	`isEmpty()`	`not st`

C++의 pop()은 제거 동작을 수행하므로 값을 먼저 top()으로 읽습니다. Java와 Python의 pop()은 꺼낸 값도 반환합니다.

기본 연산은 $O(1)$ 이며, 내부 배열 크기를 조절하는 구현의 삽입·삭제는 분할 상환 $O(1)$ 입니다. 원소 $N$ 개를 저장하는 공간은 $O(N)$ 입니다. top 조회와 제거는 원소가 있을 때 수행합니다.

예제

문제

처음에 비어 있는 스택에 다음 명령을 순서대로 수행하여라.

명령	동작
`push x`	맨 위에 $x$ 를 추가한다.
`top`	맨 위 값을 출력한다. 빈 스택이면 `EMPTY`를 출력한다.
`pop`	맨 위 값을 출력하고 제거한다. 빈 스택이면 `EMPTY`를 출력한다.
`size`	원소 수를 출력한다.

입력

첫째 줄에 명령 수 $Q$ 가 주어진다. $1\le Q\le10\,000$ 이다.

다음 $Q$ 개 줄에 위 표의 형식으로 명령이 하나씩 주어진다. 명령과 인자는 공백을 사이에 두고 주어진다. 추가할 값 $x$ 의 범위는 $1\le x<10\,000$ 이다.

출력

출력이 필요한 명령의 결과를 한 줄에 하나씩 출력한다.

예제 코드

C++20

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main() {
    int q, i, x;
    stack<int> st;
    string op;

    cin >> q;

    for (i = 0; i < q; ++i) {
        cin >> op;

        if (op == "push") {
            cin >> x;

            st.push(x);
        }
        else if (op == "size") cout << st.size() << '\n';
        else if (st.empty()) cout << "EMPTY\n";
        else if (op == "top") cout << st.top() << '\n';
        else {
            cout << st.top() << '\n';
            st.pop();
        }
    }
}

Java 17

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in;
        int q, i;
        ArrayDeque<Integer> st;
        String op;

        in = new Scanner(System.in);
        q = in.nextInt();

        st = new ArrayDeque<>();
        for (i = 0; i < q; ++i) {
            op = in.next();

            if (op.equals("push")) st.push(in.nextInt());
            else if (op.equals("size")) System.out.println(st.size());
            else if (st.isEmpty()) System.out.println("EMPTY");
            else if (op.equals("top")) System.out.println(st.peek());
            else System.out.println(st.pop());
        }
    }
}

Python 3

q = int(input())
st = []

for _ in range(q):
    cmd = input().split()
    op = cmd[0]

    if op == "push":
        st.append(int(cmd[1]))
    elif op == "size":
        print(len(st))
    elif not st:
        print("EMPTY")
    elif op == "top":
        print(st[-1])
    else:
        print(st.pop())

1.1.3 Stack

개념

원소 추가

원소 삭제

언어별 사용법

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드