[자료구조][C++] Stack 과 Queue 그리고 STL에서의 사용

배열에서 좀 더 발전하여 새로운 기능을 제공하는 stack 과 queue에 대해서 알아보자.

기초적인 내용이지만 많은 알고리즘 문제에서 활용하는 만큼 문제의 힌트를 얻어가면 좋다.

Stack

삽입과 삭제의 연산이 한쪽에서 이뤄지는 자료구조이다.

LIFO( Last In First Out )의 특징을 가지고 있다.

push를 하게 되면 stack의 top을 가리키는 포인터가 가장 마지막에 들어온 value를 가리키게 된다.

pop 연산 시 가장 마지막에 들어온 값을 stack에서 빼내어 return한다.

그리고 그 다음 값을 top 포인터가 가리키게 된다.

stack 자료구조는 깊이 우선 탐색 (DFS), 백트래킹 등의 알고리즘에서 유용하게 사용된다.

(재귀함수 알고리즘과 일맥상통)

// 내부적으로는 deque, list, vector로 구성, 근데 추가로 기능 지원
// default는 deque 구성

// STL에서 stack include 하기
#include <stack>

// stack 선언 및 기능
stack<int> s;

// 1. stack이 비어있는지 확인
s.empty()

// 2. stack 원소 갯수 반환
s.size()

// 3. stack push
s.push(val)

// 4. stack pop
s.pop()

// 5. 가장 마지막에 입력된 원소 반환
s.top()

Queue

stack과 달리 queue는 FIFO( First In First Out )의 특징을 가진다.

(편의점에서 물품 정리를 떠올리자)

그래서 삽입과 삭제가 양쪽 방향에서 이뤄진다.

큐는 너비 우선 탐색 (BFS) 에서 주로 사용한다.

// 내부적으로는 deque, list로 구현, 근데 추가로 기능 지원 (vector는 불가능!)
// default는 deque 구현

// STL에서 queue include 하기
#include <queue>

// queue 선언 및 기능
queue<int> q;

// 1. queue가 비어있는지 확인
q.empty()

// 2. queue 원소 갯수 반환
q.size()

// 3. queue push (enqueue)
q.push(val)

// 4. queue pop (dequeue)
q.pop()

// 5. 가장 처음에 입력된 원소 반환
q.front()

// 6. 가장 마지막에 입력된 원소 반환
q.back()

마지막으로 시간복잡도의 경우

stack 과 queue 둘다 아래와 같다.