스택 (Stack) & 큐 (Queue) & 덱 (Deque)

1. 스택 (Stack) ?

• 한 방향에서만 데이터를 뽑아낼 수 있는 선형 구조인 LIFO 형태의 자료구조이다.
• LIFO - Last In First Out의 줄임말이며, 말 그대로 마지막에 들어온 데이터가 첫 번째로 빠져나간다는 의미이다.
• 화물차안에 짐을 넣을 때를 생각해보자. 가장 먼저 넣은 짐은 가장 나중에 빠지고, 가장 늦게 넣은 짐은 가장 먼저 빠지는 원리이다.

 

 

1-1. Stack의 연산

• Top : 연산이 아닌 Stack의 최상위층 인덱스라고 보면 된다.
• push : Stack내에 데이터를 삽입할 때 사용한다.
• pop : Stack내에서 맨 꼭대기인 Top부분에 위치한 데이터를 꺼낼 때 사용한다.
• peek : pop과의 차이점은 peek은 데이터를 조회만 할 뿐 꺼내지는 않는다.
• empty : Stack이 비어 있는지 확인하는 연산이다. Top을 통해서 Stack내 데이터가 존재하는지 확인한다.

 

1-2. Stack의 특징

• Stack의 중간에 위치한 데이터는 위에서 부터 차례대로 빼지 않는 이상 조회할 방법이 없다.
• Top을 통해 데이터의 갯수와 현재 Stack내 위치를 알 수 있다.
• Last In First Out인 후입선출의 방법을 이용한다.
• Stack이 비어 있을 때 pop을 통해 데이터를 뽑아 내려고 한다면 언더플로우(Underflow)가 발생하며, Stack이 가득 차 있을 때, push를 통해 데이터를 집어 넣으려고 한다면 오버플로우(Overflow)가 발생한다 (배열을 기초로 만든 스택에 한해서).

 

Code

 

2. 큐 (Queue) ?

• 스택과는 다르게 데이터를 집어넣은 순서대로 빠져나오는 FIFO 구조를 가지고 있다.
• FIFO - First In First Out의 줄임말로 첫 번째로 들어간 것이 첫 번째로 빠져나오는 의미이다.
• 놀이기구를 탈 때 서있는 줄을 생각해보자. 먼저 기다린 사람이 놀이기구를 먼저 타고 빠져나온 후에 다음 사람이 놀이기구를 타러 들어가는 것이다.
• 큐는 데이터가 입력 순서대로 처리해야 될 필요가 있는 상황에서 이용된다. (ex. 프린터 출력, 프로세스 관리)

출처 : https://monsieursongsong.tistory.com/5

 

2-1. Queue의 연산

• front : 큐의 맨 앞 부분 인덱스를 나타낸다. 이 부분은 데이터를 꺼낼 위치이다.
• rear : 큐의 맨 뒷 부분 인덱스를 나타낸다. 이 부분은 데이터를 넣을 위치이다.
• enqueue (put) : 데이터를 rear 위치에 삽입하는 역할이다.
• dequeue (get) : front 위치에서 데이터를 꺼내는 역할이다.
• peek : 스택과 마찬가지로 데이터를 꺼내지 않고 조회만 한다.

 

2-2. Queue의 종류

2-2-1. 선형 큐

• 데이터는 A B C D E를 차례대로 넣는다고 가정한다.
• 이름 그대로 데이터를 큐의 위치에 순서대로 삽입한다.
• 선형 큐의 경우, rear가 마지막에 도달한다면 큐의 앞부분 공간이 비어 있어도 데이터를 삽입할 수 없다.

2-2-2. 환형 큐

• 마찬가지로 데이터는 A B C D E를 차례대로 넣는다고 가정한다.
• 선형 큐의 단점인 rear가 마지막에 도달하면 데이터를 삽입할 수 없는 부분을 보완한 것이다.
• rear가 끝에 도달한 후 데이터가 들어오면 rear는 큐의 맨 앞부분으로 이동하여 데이터를 삽입한다.

 

Code

 

3. 덱 (Deque) ?

• 덱 (Deque) 은 Double-Ended Queue의 줄임말로, 간단하게 생각하면 양쪽에서 삽입과 삭제를 할 수 있는 큐이다.
  • 어떻게 보면 스택과 큐를 합쳐놓은 것으로 생각해도 된다.

 

Reference

• https://opensourcedev.tistory.com/3
• https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D
• https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)