[자료구조] - 스택, 큐, 덱

• 스택(Stack)이란?

스택은 후입선출(Last-In-First-Out / LIFO) 구조이다.

예를 들어, 책상에 책을 쌓는 것과, 책을 꺼낼 때 위에서부터 꺼내는 형식을 생각하면 이해하기가 쉽다.

 

스택의 기본 함수

- 스택이름.push(삽입할 값) : 스택에 새로운 값을 쌓아 올리는 연산(삽입)

- 스택이름.pop() : 스택의 가장 위의 값을 삭제하는 연산

- 스택이름.top() : 스택의 가장 위의 값을 반환(빈 스택이면 오류)

- 스택이름.size() : 스택에 들어있는 원소의 개수를 반환

- 스택이름.empty() : 스택이 비어 있는지를 확인하는 연산

                           비어 있으면 true(1), 값이 하나라도 있으면 false(0)

 

• 큐(Queue)란?

스택과 비슷하게 삽입, 삭제의 위치가 제한되어 있지만, 큐는 뒤에서 삽입이 가능하고, 삭제는 앞에서부터 하는 선입선출(First-In-First-Out /FIFO)의 구조이다.

선입선출의 예로는 줄서기를 생각하면 이해하기가 쉽다.

주로 순서를 보장하기 위한 처리가 필요할 때 사용된다. 큐에 저장된 요소들은 순서대로 존재하고, 앞에 있을 수록 오래 기다리고 있다는 것을 의미하게 된다.

 

큐의 기본 함수

- 큐이름.push(삽입할 값) : 큐의 뒤(rear)에 값을 삽입하는 연산

- 큐이름.pop() : 큐의 가장 앞(front)의 값을 삭제하는 연산

- 큐이름.front() : 큐의 가장 앞(front)의 값을 반환

- 큐이름.back() : 큐의 가장 뒤(rear)의 값을 반환

- 큐이름.size() : 큐에 들어있는 원소의 개수를 반환

- 큐이름.empty() : 큐가 비어 있는지를 확인하는 연산

                        비어 있으면 true(1), 값이 하나라도 있으면 false(0)

 

• 덱(Deque)이란?

덱의 경우, 큐와 비슷하지만, front와 end에서 삭제와 삽입이 모두 가능하다는 점에서 차별점을 가진다.

큐 두 개중 하나를 좌우로 뒤집어서 붙인 구조라고 할 수 있다. 

크기가 가변적이고, 중간 요소가 삽입, 삭제될 때, 요소들을 앞/뒤로 밀 수 있어서 vector보다는 좋은 성능을 가지고 있다고 할 수 있다.

덱의 예시로는 낚시줄에 구슬을 꿰매는 것을 생각하면 이해하기가 쉽다.

 

덱의 기본 함수

- 덱이름.push_front(삽입할 값) : 덱의 앞(front)에 값을 삽입하는 연산

- 덱이름.push_back(삽입할 값) : 덱의 뒤(rear)에 값을 삽입하는 연산

- 덱이름.pop_front() : 덱의 가장 앞(front)의 값을 삭제하는 연산

- 덱이름.pop_back() : 덱의 가장 뒤(rear)의 값을 삭제하는 연산

- 덱이름.front() : 덱의 가장 앞(front)의 값을 반환

- 덱이름.back() : 덱의 가장 뒤(rear)의 값을 반환

- 덱이름.size() : 덱에 들어있는 원소의 개수를 반환

- 덱이름.empty() : 덱이 비어 있는지를 확인하는 연산

                        비어 있으면 true(1), 값이 하나라도 있으면 false(0)