스택과 큐 - 기본 자료구조의 원리 - soo:bak

작성일 :

스택(Stack)이란?

접시를 쌓아 올리는 상황을 생각해보겠습니다. 새 접시는 맨 위에 올리고, 꺼낼 때도 맨 위에서 꺼냅니다.

스택(Stack) 은 LIFO(Last In, First Out) 원리를 따르는 자료구조입니다. 가장 나중에 들어온 데이터가 가장 먼저 나갑니다.

스택의 기본 연산

연산 설명 시간 복잡도
push(x) 스택의 맨 위에 x를 추가 O(1)
pop() 스택의 맨 위 데이터를 제거하고 반환 O(1)
top() (또는 peek()) 스택의 맨 위 데이터를 제거하지 않고 확인 O(1)
empty() 스택이 비어있는지 확인 O(1)
size() 스택에 있는 데이터의 개수 반환 O(1)


모든 연산이 O(1)에 수행됩니다. 스택은 맨 위(top)에서만 삽입과 삭제가 일어나기 때문입니다.


동작 예시

스택에 1, 2, 3을 순서대로 넣고 꺼내는 과정입니다:

1
2
3
4
5
6
7
8
9
10

초기 상태: []

push(1): [1]          ← 1이 맨 위
push(2): [1, 2]       ← 2가 맨 위
push(3): [1, 2, 3]    ← 3이 맨 위

top():   3 반환       (스택 변화 없음)
pop():   3 반환       [1, 2]  ← 3이 제거됨
pop():   2 반환       [1]     ← 2가 제거됨
push(4): [1, 4]       ← 4가 맨 위


시각적으로 표현하면:

1
2
3
4
5
6
7
8
9

push(1)   push(2)   push(3)   pop()     pop()
                    
   ┌─┐     ┌─┐       ┌─┐       ┌─┐       
   │3│ ← top        │ │       │ │       
   ├─┤     ├─┤       ├─┤       ├─┤       ┌─┐
   │2│     │2│ ← top │2│       │ │       │ │
   ├─┤     ├─┤       ├─┤       ├─┤       ├─┤
   │1│     │1│       │1│       │1│ ← top │1│ ← top
   └─┘     └─┘       └─┘       └─┘       └─┘


스택 구현 (C++)

STL stack 사용

C++ STL의 stack은 내부적으로 deque를 사용하여 구현되어 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <bits/stdc++.h>
using namespace std;

int main() {
  stack<int> st;

  // 데이터 추가
  st.push(1);
  st.push(2);
  st.push(3);

  // 맨 위 확인 및 제거
  cout << st.top() << "\n";  // 3
  st.pop();
  cout << st.top() << "\n";  // 2

  // 스택이 빌 때까지 출력
  while (!st.empty()) {
    cout << st.top() << " ";
    st.pop();
  }
  // 출력: 2 1

  return 0;
}


배열로 직접 구현

스택의 원리를 이해하기 위해 배열로 직접 구현해보겠습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Stack {
private:
  int arr[10000];  // 데이터 저장 배열
  int topIdx;      // 맨 위 인덱스

public:
  Stack() : topIdx(-1) {}  // 초기화: 비어있는 상태

  void push(int x) {
    arr[++topIdx] = x;  // topIdx를 증가시키고 데이터 저장
  }

  int pop() {
    return arr[topIdx--];  // 데이터 반환 후 topIdx 감소
  }

  int top() {
    return arr[topIdx];
  }

  bool empty() {
    return topIdx == -1;  // topIdx가 -1이면 비어있음
  }

  int size() {
    return topIdx + 1;
  }
};


topIdx가 -1이면 스택이 비어있는 상태입니다. push할 때마다 topIdx가 증가하고, pop할 때마다 감소합니다.


주의: 이 구현은 스택이 가득 찬 경우(overflow)나 비어있을 때 pop하는 경우(underflow)를 처리하지 않습니다. 실제 사용 시에는 이런 예외 처리가 필요합니다.


큐(Queue)란?

은행 대기줄을 생각해보겠습니다. 먼저 온 사람이 먼저 서비스를 받고, 나중에 온 사람은 앞 사람이 모두 끝날 때까지 기다려야 합니다.


큐(Queue)는 이처럼 FIFO(First In, First Out) 원리를 따르는 자료구조입니다. 가장 먼저 들어온 데이터가 가장 먼저 나갑니다.


스택이 “가장 최근 것부터” 처리한다면, 큐는 “가장 오래된 것부터” 처리합니다.


큐의 일상생활 예시:

  • 프린터 대기열: 먼저 요청한 문서가 먼저 출력됩니다.
  • 콜센터 대기: 먼저 전화한 사람이 먼저 상담을 받습니다.
  • 운영체제의 작업 스케줄링: CPU가 여러 작업을 순서대로 처리합니다.


큐의 기본 연산

연산 설명 시간 복잡도
push(x) (enqueue) 큐의 뒤쪽에 x를 추가 O(1)
pop() (dequeue) 큐의 앞쪽 데이터를 제거하고 반환 O(1)
front() 큐의 맨 앞 데이터를 확인 O(1)
back() 큐의 맨 뒤 데이터를 확인 O(1)
empty() 큐가 비어있는지 확인 O(1)
size() 큐에 있는 데이터의 개수 반환 O(1)


스택과 마찬가지로 모든 연산이 O(1)에 수행됩니다.


동작 예시

큐에 1, 2, 3을 순서대로 넣고 꺼내는 과정입니다:

1
2
3
4
5
6
7
8
9
10

초기 상태: []

push(1): [1]          ← front이자 back
push(2): [1, 2]       ← front: 1, back: 2
push(3): [1, 2, 3]    ← front: 1, back: 3

front(): 1 반환       (큐 변화 없음)
pop():   1 반환       [2, 3]  ← 1이 제거됨
pop():   2 반환       [3]     ← 2가 제거됨
push(4): [3, 4]       ← front: 3, back: 4


시각적으로 표현하면:

1
2
3
4
5
6
7
8
9

push(1)   push(2)   push(3)   pop()     pop()     push(4)

  ┌───────────────────────────────────────────────────────┐
  │                         큐                            │
  └───────────────────────────────────────────────────────┘
  
front→ [1]        [1, 2]    [1, 2, 3]  [2, 3]    [3]       [3, 4] ←back
                                        ↑         ↑         ↑
                                        front     front     front


스택과의 차이점: 스택은 한쪽 끝(top)에서만 삽입/삭제가 일어나지만, 큐는 한쪽(back)에서 삽입하고 다른 쪽(front)에서 삭제합니다.


큐 구현 (C++)

STL queue 사용

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <bits/stdc++.h>
using namespace std;

int main() {
  queue<int> q;

  // 데이터 추가
  q.push(1);
  q.push(2);
  q.push(3);

  // 맨 앞과 맨 뒤 확인
  cout << q.front() << "\n";  // 1
  cout << q.back() << "\n";   // 3

  // 맨 앞 제거
  q.pop();
  cout << q.front() << "\n";  // 2

  // 큐가 빌 때까지 출력
  while (!q.empty()) {
    cout << q.front() << " ";
    q.pop();
  }
  // 출력: 2 3

  return 0;
}


주의: STL queue의 pop()은 값을 반환하지 않습니다. 값을 확인하려면 먼저 front()를 호출해야 합니다.


덱(Deque)

덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조입니다. 스택과 큐의 기능을 모두 가지고 있어서, 필요에 따라 스택처럼 또는 큐처럼 사용할 수 있습니다.


연산 설명 시간 복잡도
push_front(x) 앞에 x 삽입 O(1)
push_back(x) 뒤에 x 삽입 O(1)
pop_front() 앞에서 제거 O(1)
pop_back() 뒤에서 제거 O(1)
front() 맨 앞 확인 O(1)
back() 맨 뒤 확인 O(1) 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <bits/stdc++.h>
using namespace std;

int main() {
  deque<int> dq;

  dq.push_back(1);   // [1]
  dq.push_front(2);  // [2, 1]
  dq.push_back(3);   // [2, 1, 3]

  cout << dq.front() << "\n";  // 2
  cout << dq.back() << "\n";   // 3

  dq.pop_front();  // [1, 3]
  dq.pop_back();   // [1]

  cout << dq.front() << "\n";  // 1

  return 0;
}


덱은 슬라이딩 윈도우 최댓값/최솟값 문제에서 자주 사용됩니다.


스택과 큐의 비교

특성 스택 큐
원리 LIFO (후입선출) FIFO (선입선출)
삽입/삭제 위치 한쪽 끝(top)에서만 양쪽 끝(front/back)에서
접근 가능한 요소 맨 위(top)만 맨 앞(front), 맨 뒤(back)
대표 활용 DFS, 괄호 검사, 실행 취소 BFS, 작업 스케줄링


스택 활용 예제: 괄호 검사

스택의 대표적인 활용 예제로, 괄호의 짝이 올바른지 검사하는 함수입니다.


문제: 주어진 문자열에서 (), [], {}의 짝이 모두 올바르게 맞는지 확인합니다.


아이디어: 여는 괄호가 나오면 스택에 넣고, 닫는 괄호가 나오면 스택에서 꺼내 짝이 맞는지 확인합니다.

1
2
3
4
5
6
7
8
9
10

입력: "({[]})"

'(' → push → ['(']
'{' → push → ['(', '{']
'[' → push → ['(', '{', '[']
']' → pop → '[' ✓ → ['(', '{']
'}' → pop → '{' ✓ → ['(']
')' → pop → '(' ✓ → []

스택이 비었으므로 올바른 괄호입니다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <bits/stdc++.h>
using namespace std;

bool isValid(string s) {
  stack<char> st;

  for (char c : s) {
    // 여는 괄호는 스택에 push
    if (c == '(' || c == '[' || c == '{') {
      st.push(c);
    } else {
      // 닫는 괄호인데 스택이 비어있으면 짝이 없음
      if (st.empty())
        return false;

      char top = st.top();
      st.pop();

      // 짝이 맞는지 확인
      if (c == ')' && top != '(')
        return false;
      if (c == ']' && top != '[')
        return false;
      if (c == '}' && top != '{')
        return false;
    }
  }

  // 모든 괄호를 처리한 후 스택이 비어있어야 함
  return st.empty();
}

int main() {
  cout << isValid("({[]})") << "\n";  // 1 (true)
  cout << isValid("({[}])") << "\n";  // 0 (false)
  cout << isValid("((())") << "\n";   // 0 (false) - 여는 괄호가 남음

  return 0;
}


왜 스택을 사용하는가?

괄호는 가장 최근에 열린 것이 가장 먼저 닫혀야 합니다. 이것이 바로 LIFO 원리입니다. 예를 들어, ({[]})에서 [가 가장 나중에 열렸으므로 가장 먼저 ]로 닫혀야 합니다.


큐 활용 예제: BFS

큐는 너비 우선 탐색(BFS)에서 핵심적인 역할을 합니다.


아이디어: 현재 위치에서 갈 수 있는 모든 곳을 큐에 넣고, 큐에서 하나씩 꺼내며 탐색합니다. 먼저 발견된 곳이 먼저 탐색되므로, 시작점에서 가까운 곳부터 탐색하게 됩니다.

1
2
3
4
5

미로에서 최단 경로 찾기:

시작점 (0,0)을 큐에 넣음 → [(0,0)]
(0,0)을 꺼내고, 갈 수 있는 (0,1), (1,0)을 큐에 넣음 → [(0,1), (1,0)]
(0,1)을 꺼내고, 갈 수 있는 곳을 큐에 넣음 → ...


왜 큐를 사용하는가?

BFS는 시작점에서 가까운 곳부터 방문해야 합니다. 큐의 FIFO 원리 덕분에, 먼저 발견된 노드(가까운 노드)가 먼저 처리됩니다.

참고 : 그래프 탐색 - DFS와 BFS - soo:bak


실전 팁

1. STL 사용 시 주의사항

1
2
3
4
5
6

// ❌ 잘못된 사용: pop()은 값을 반환하지 않음
int x = st.pop();  // 컴파일 에러

// ✅ 올바른 사용
int x = st.top();
st.pop();


2. 빈 스택/큐에서 pop() 호출

1
2
3
4
5
6
7

stack<int> st;
st.pop();  // 런타임 에러 (undefined behavior)

// ✅ 먼저 empty() 확인
if (!st.empty()) {
  st.pop();
}


3. 스택 vs 재귀

DFS는 스택 대신 재귀로 구현할 수 있습니다. 재귀 호출 자체가 함수 호출 스택을 사용하기 때문입니다. 다만, 재귀 깊이가 깊어지면 스택 오버플로우가 발생할 수 있으므로, 이 경우에는 명시적으로 스택을 사용하는 것이 안전합니다.


마무리

스택과 큐는 가장 기본적인 자료구조이지만, 많은 알고리즘의 기반이 됩니다.


자료구조 원리 대표 활용
스택 LIFO (후입선출) DFS, 괄호 검사, 실행 취소
큐 FIFO (선입선출) BFS, 작업 스케줄링
덱 양방향 삽입/삭제 슬라이딩 윈도우


“가장 최근 것부터 처리”해야 하면 스택, “먼저 온 것부터 처리”해야 하면 큐를 선택합니다.


관련 문제

이 블로그의 다른 글