[자료구조][C++] Stack, Queue, Deque

1. Stack

: LIFO(Last In First Out) 구조. 가장 최근에 스택에 삽입된 자료의 위치를 top이라 한다.

스택이 비어있을 때 stack.pop 시도 -> stack underflow 발생

스택의 크기가 비어있을 때 stack.push 시도 -> stack overflow 발생

데이터 삽입, 삭제의 시간 복잡도는 O(1)

데이터를 저장하는 버퍼를 1차원 배열 형태로 관리함 -> 메모리 추가로 할당할 경우 기존 메모리 영역의 2배만큼 메모리 추가로 할당하고 기존의 요소 복사

< 장단점 >

- 데이터 접근, 삽입, 삭제가 빠르다.

- top 위치 이외의 데이터에 접근할 수 없어서 탐색 불가능. 탐색하려면 모든 데이터 꺼내면서 진행해야 됨

#include <vector>

vector<int> v;
v.at(idx);			// idx번째 원소를 참조. v[idx]보다 느리지만, 범위를 점검하므로 안전하다
v[idx];				// idx번째 원소를 참조. 범위 점검 X -> v.at(idx)보다 빠름
v.front();			// 첫번째 원소를 참조
v.back();			// 마지막 원소를 참조
v.clear();			// 모든 원소를 제거하고 크기가 0인 벡터로 만든다. 단, 메모리는 남아있다(size는 0이지만 capacity는 그대로)
v.push_back(n);			// 마지막 원소 뒤에 원소 n 삽입
v.pop_back();			// 마지막 원소 제거
v.size();			// 원소의 갯수를 리턴
v.capacity();			// 할당된 공간의 크기(메모리)를 리턴한다.
v.insert(n, m);			// n번째 위치에 m의 값을 삽입. 삽입한 곳의 iterator를 반환
v.erase(iter);			// iter가 가리키는 원소를 제거. size만 줄고 capacity 그대로
v.empty();			// 비었으면 true (size == 0)

size와 capacity는 다르다. size는 원소의 개수, capacity는 할당된 메모리의 크기를 리턴한다.

---

2. Queue

: FIFO(First In First Out) 구조

선형 큐 : 선형 배열 사용해 구현. front와 rear 증가만 함 -> 실제로 front 앞쪽에 공간 있더라고 삽입할 수 없는 경우 발생

원형 큐 : 선형 큐의 단점 보완 -> 큐 회전하면서 데이터 삽입, 삭제

큐 empty 상태 : front == rear

큐 full 상태 : front == (rear+1) % MAX_QUEUE_SIZE

공백과 포화 상태 구분 위해 하나의 공간 남겨둔다.

queue에서 원소 삽입, 삭제의 시간복잡도는 O(1)이다.

< 장단점 > : stack과 동일

#include <queue>

queue <int> q;			// queue 선언
q.push(element);		// 데이터 추가
q.pop();			// front 데이터 삭제
q.front();			// front 데이터 반환
q.back();			// back 데이터 반환
q.size();
q.empty();
swap(q1, q2);			// 두 큐의 내용 바꾸기

파이썬에서는 pop연산이 데이터 반환과 동시에 삭제하는 반면, C++에서는 두 과정이 따로 분리되어 있다.

int value = queue.front();
queue.pop();

---

3. Deque

: Double-Ended Queue의 줄임말 --> 'Deque'

양쪽 끝에서 삽입, 삭제가 가능하며 가변적 크기를 가짐. 시간복잡도는 queue, stack과 마찬가지로 O(1)

chunk 이용해 관리. 메모리 영역 군데군데 흩어져 있으며, 컨테이너에서 내부적으로 바로 접근 가능하도록 인터페이스 제공함. 따라서 메모리 추가 할당 시 새로운 chunk 하나 만들기만 하면 된다

< 장단점 >

- 데이터의 삽입과 삭제가 빠름, 앞뒤 모두 삽입과 삭제 가능

- 가변적 크기

- index 통해 임의의 원소에 바로 접근 가능

- 새로운 원소 삽입 시 새로운 단위의 메모리 블록 할당해 삽입

- 중간에서의 삽입, 삭제가 어려움

 

#include <vector>

vector<int> v;
v.at(idx);			// idx번째 원소를 참조. v[idx]보다 느리지만, 범위를 점검하므로 안전하다
v[idx];				// idx번째 원소를 참조. 범위 점검 X -> v.at(idx)보다 빠름
v.front();			// 첫번째 원소를 참조
v.back();			// 마지막 원소를 참조
v.clear();			// 모든 원소를 제거. 원소만 제거하고 메모리는 남아있음(size만 줄고 capacity는 그대로)
v.push_back(n);			// 마지막 원소 뒤에 원소 n 삽입
v.pop_back();			// 마지막 원소 제거
v.size();			// 원소의 갯수를 리턴
v.capacity();			// 할당된 공간의 크기(메모리)를 리턴한다.
v.insert(n, m);			// n번째 위치에 m의 값을 삽입. 삽입한 곳의 iterator를 반환
v.erase(iter);			// iter가 가리키는 원소를 제거. size만 줄고 capacity 그대로
v.empty();			// 비었으면 true (size == 0)

---

< 참고자료 및 사진 출처>

[자료구조] 스택 Stack, 큐 Queue, 덱 Deque

 

[C++] vector container 정리 및 사용법

 

[C++][STL] Queue 기본 사용법 및 예제

 

[C++] deque container 정리 및 사용법