C++: 스택(Stack) & 큐(Queue)

Posted Mar 18, 2026 Updated Mar 18, 2026

14 min read

스택(Stack)

들어간 순서의 반대대로 나오는(Last In First Out, LIFO) 자료구조로, 쌓는 행위 또는 쌓인 더미를 뜻하는 영단어 stack에서 유래했다.
- A, B, C 순서대로 삽입된다면, 나올 때는 C, B, A 순으로 삭제된다.
- Vector에서 push_back()/back()/pop_back()만 이용한다면 Stack과 동일하다. 다만 스택은 백터처럼 무작위 접근/수정/삭제가 불가능하다.

stack 라이브러리를 포함시켜 사용할 수 있고, 다음 함수들을 사용해 스택을 조작한다:

push(x): 스택에 자료를 추가한다.
pop(): 마지막으로 넣은 자료를 삭제한다,
top(): 마지막으로 넣은 자료를 얻는다.
empty(): 스택이 비어있는지 확인한다.

  
  #include <iostream>
  #include <stack>	//스택 라이브러리
  using namespace std;

  int main() {
      //스택 선언
      //stack<자료형> 이름
      stack<int> S;

      //스택 값 삽입
      cout << "스택에 삽입합니다: ";
      for (int i = 0; i < 5; i++) {
          cout << i << " ";
          S.push(i);//스택 삽입 함수
      } 

      cout << "\n\n스택이 비었는지 확인합니다: " << S.empty(); //스택 비었는지 확인하는 함수

      //스택 맨 위 출력후 제거
      cout << "\n\n스택에서 삭제합니다: ";
      for (int i = 0; i < 5; i++) {
          cout << S.top() << " ";	//스택 맨위 Getter
          S.pop(); //스택 삭제 함수
      }

      cout << "\n\n스택이 비었는지 확인합니다: " << S.empty(); //스택 비었는지 확인하는 함수
  }

큐(Queue)

스택과 유사하지만, 순서가 달리 삽입 순서에 맞추어 나오는(First In First Out, FIFO) 자료구조다. 프랑스어 단어 꼬리/줄(queue)에서 유래했다.
- A B C 순서로 삽입된다면, A B C 순서 그대로 삭제된다.

다음 함수들을 사용해 스택을 조작한다. 사용법은 스택과 유사하다:

push(x): 큐 맨뒤에 자료를 추가한다.
pop(): 제일 먼저 넣었던 자료를 삭제한다, 즉 맨 앞 자료를 삭제한다.
front(): 제일 먼저 넣었던 자료(맨 앞 자료)를 얻는다.
back(): 마지막으로 넣었던 자료를 얻는다. 스택의 top()과 같은 역할이다.
- 스택에선 top의 반대인 bottom을 지원하진 않는다. 하나의 입구를 구현하려는 스택, 그리고 줄세우기를 구현하려는 큐의 목적 차이 때문이라 할 수 있다.
- 그래도 FIFO를 위해 사용하는 큐 특성상 쓸 일이 많지는 않을것이고, 사용해야 한다면 다른 자료구조가 더 적합할 수도 있다.
empty(): 스택이 비어있는지 확인한다.

  
  #include <iostream>
  #include <queue>	//큐 라이브러리
  using namespace std;

  int main() {
      //큐 선언
      //queue<자료형> 이름
      queue<int> S;

      //큐 값 삽입
      cout << "큐에 삽입합니다: ";
      for (int i = 0; i < 5; i++) {
          cout << i << " ";
          S.push(i);//큐 삽입 함수
      } 

      cout << "\n\n큐가 비었는지 확인합니다: " << S.empty(); //큐 비었는지 확인하는 함수
      cout << "\n\n큐 맨 뒷값: " << S.back(); //FIFO 구조지만, 값을 읽는건 앞뒤 다 지원한다.

      //큐 맨 위 출력후 제거
      cout << "\n\n큐에서 삭제합니다: ";
      for (int i = 0; i < 5; i++) {
          cout << S.front() << " ";	//큐 맨앞 Getter
          S.pop(); //큐 삭제 함수
      }

      cout << "\n\n큐가 비었는지 확인합니다: " << S.empty(); //큐 비었는지 확인하는 함수
  }

큐 내부적으론 들어온 순서에 따라 정렬되지만, 개별 자료의 우선순위를 할당하고 그에 따라 내부적으로 정렬, FIFO구조를 변형시킬 수 있는 우선순위 큐(Priority queue)도 존재한다. 운영체제의 프로세스 관리, 게임 대기열에서 우선순위 반영등 순서 외에 반영될 요소들이 있을 때 사용한다.

왜 벡터 대신 쓰는가?
- 벡터는 모든 인덱스에 대한 접근을 가지지만, 경우에 따라서는 자료의 의도와 맞지 않는 동작을 구현할 수도 있다. 순서에 올바른 순서로 자료에 접근하게 함으로써, 의도와 목적성을 명확히 표현하고 실수를 예방한다.
- 또한 벡터의 Insert()/erase()와는 다르게, 위에 언급된 모든 접근법은 O(1)의 시간 복잡도를 가진다. 스택과 큐에 맞는 동작 순서를 필요로 하면서 더 빠른 동작을 보장하고자 한다면 스택과 큐가 유리할 것이다.

덱(Deque, double-ended queue)

스택과 큐의 원형으로, 벡터와 유사한 컨테이너이다.
- 스택과 큐는 디큐에서 한쪽을 막아놓은 컨테이너 어댑터이다. 즉 내부적으로는 디큐로 작동한다.

O(1)의 시간복잡도를 가지는 스택과 큐에서 쓰던 기능들을 마찬가지로 지원한다.

push_front(x): 맨앞에 값을 삽입한다.
push_back(x): 맨뒤에 값을 삽입한다.
pop_front(): 맨 앞의 값을 제거한다.
pop_back(): 맨 뒤의 값을 제거한다.
empty(): 비어있는지 확인한다.
벡터처럼 랜덤 접근과 반복자를 지원한다.

  
  #include <iostream>
  #include <deque>	//덱 라이브러리
  using namespace std;

  int main() {
      //덱 선언
      //deque<자료형> 이름
      deque<int> S;

      cout << "덱 앞에 삽입합니다: ";	//덱 앞에서 삽입
      for (int i = 0; i < 5; i++) {
          cout << i << " ";
          S.push_front(i);//덱 앞쪽 삽입 함수
      }

      cout << "\n덱이 비었는지 확인합니다: " << S.empty(); //덱 비었는지 확인

      cout << "\n덱 값들을 출력합니다: ";	//반복자를 이용한 덱 순회 출력
      for (auto i = S.begin(); i != S.end(); i++) {
          cout << *i << " ";
      }

      cout << "\n\n덱 뒤에 삽입합니다: ";	//덱 뒤에서 삽입
      for (int i = 0; i < 5; i++) {
          cout << i << " ";
          S.push_back(i);//덱 뒤쪽 삽입 함수
      }

      cout << "\n덱 값들을 출력합니다: ";	//랜덤 접근을 이용한 덱 순회 출력
      for (int i = 0; i < S.size(); i++) {
          cout << S[i] << " ";
      }

      //덱 뒤쪽 출력후 제거
      cout << "\n\n3개 원소를 덱 뒤에서 삭제합니다: ";
      for (int i = 0; i < 3; i++) {
          cout << S.back() << " ";	//덱 맨위 Getter
          S.pop_back(); //덱 뒤쪽 삭제 함수
      }

      cout << "\n덱 값들을 출력합니다: ";
      for (auto i = S.begin(); i != S.end(); i++) {
          cout << *i << " ";
      }

      //덱 앞쪽 출력후 제거
      cout << "\n\n2개 원소를 덱 앞에서 삭제합니다: ";
      for (int i = 0; i < 2; i++) {
          cout << S.front() << " ";	//덱 맨앞 Getter
          S.pop_front(); //덱 앞쪽 삭제 함수
      }

      cout << "\n덱 값들을 출력합니다: ";
      for (auto i = S.begin(); i != S.end(); i++) {
          cout << *i << " ";
      }
  }

벡터와 기본적인 사용법이 비슷하다. 그럼에도 내부 구조와 시간복잡도에서 약간의 차이가 있다. 용도에 맞게 사용하되, Deque를 사용할 정도면 우선 스택과 큐를 사용하는걸 고려해보자.

차이	Vector	Deque
원소의 저장	연속된 메모리에 저장	연속될 필요 없음
캐쉬 친화성	유리	불리
전방 삽입/삭제	불리(메모리 이동 필요)	유리(재구성 특별히 필요 없음)
컨테이너 용량	확장시에 O(n)	확장 필요 없어 O(1)

활용
- 기초적인 자료구조로 스택과 큐 모두 다양하게 활용된다.
- 많은 프로그램에서 쓰이는 Undo/Redo 사용된 기능을 저장하는 스택 2개를 이용하여 구현할 수 있다.
- 게임에 흔히 사용되는 입력의 순차 처리, 네트워크 패킷 버퍼, 매칭 대기열등 순서대로 처리가 중요한 영역에 큐를 사용할 수 있다.
- 웹 브라우저의 뒤로가기/앞으로 가기도 Undo/Redo와 유사하게 구현할 수 있으며, 웹서버에서 비동기 통신을 위한 버퍼로 메세지 큐(Massage Queue)를 구현한다.
- 컴퓨터 시스템 내부에서도 다양하게 활용된다.
  - 함수 호출 스택
    - 메모리의 스택 세그먼트가 스택으로 이름지어진 이유도 스택 자료구조 때문이다.
      1. 먼저 호출된 함수가 먼저 스택 프레임에 쌓인다.
      2. 다른 함수 호출, 재귀호출등 다른 함수를 도중에 부를 때 스택프레임 위에 추가로 쌓인다.
      3. 마지막으로 호출된 함수가 먼저 처리되고 스택프레임에서 제거되면, 스택 구조에 의해 그 전에 호출됬던 함수로 돌아간다.
  - 현대에는 보편화된 다중코어 환경에서 중요한 멀티스레딩(Multi Threading)/병렬 프로그래밍(Parallel Programming)에서 운영체제가 프로세스 스케줄링에 Ready Queue 사용한다.
    - 여러개의 프로세스가 생성된다.
    - 가용한 CPU 스레드를 확인한다.
    - 먼저 등록된(혹은 우선순위를 가지는, Priority queue 경우에 해당한다.) 프로세스를 할당한다.
    - 프로세스가 종료되면 스레드에 할당된 프로세스를 해제한다.
    - 위 과정을 프로세스가 존재하고 비어있는 스레드가 있으면 반복한다.
  - 다른 자료구조인 그래프를 탐색하는데 있어, 깊이 우선 탐색(Depth First Search, DFS)는 스택을 이용해 구현하고, 너비 우선 탐색(Breadth First Search)는 큐를 이용해 구현할 수 있다.

C++, Algorithm

This post is licensed under CC BY 4.0 by the author.

스택(Stack)

큐(Queue)

왜 벡터 대신 쓰는가?

덱(Deque, double-ended queue)

활용

Trending Tags