[데이터베이스] 자료구조 - 스택(Stack), 큐(Queue), 데크(Deque)의 개념 및 처리 방법 비교

지난 시간에는 선형 구조의 저장방법인 리스트에 대해서 알아보았는데 오늘은 같은 선형구조로 분류는 되지만 다른 방식으로 기억장치에 저장하는 스택(Stack), 큐(Queue), 그리고 데크(Deque)에 대해 포스팅을 해보겠습니다.

 

리스트에 관한 내용은 아래의 링크를 참고 부탁드립니다.

2022.10.22 - [Intelligence Technology] - [데이터베이스] 자료구조의 개념 및 리스트(List)의 특징(선형 구조)

[데이터베이스] 자료구조의 개념 및 리스트(List)의 특징(선형 구조)

 

우선 스택은 리스트 구조에서 한쪽 끝으로만 자료가 삽입 또는 삭제가 되는 구조를 의미합니다.

<스택(Stack) 구조>

탑(Top)은 Stack 공간에서 가장 마지막으로 삽입된 자료가 저장되어 있는 위치를 가리킵니다. 스택 포인터라고도 부릅니다. 그리고 바텀(Bottom)은 제일 먼저 입력이 된 값의 위치를 나타냅니다. 삽입은 Push, 삭제는 Pop으로 부릅니다. 

 

스택에 저장된 값들 사이에 자료를 추가하려면 마지막에 입력을 했던 자료부터 순서대로 뺀 다음 원하는 위치가 왔을 때 추가하려는 자료를 입력하고 다시 순서대로 값을 채워야 합니다. 나중에 입력된 값들이 제일 먼저 삭제되는 이런 방식을 후입 선출(LIFO: Last In First Out)이라고 부릅니다.

 

 

만약 삽입 과정에서 스택(Stack)이 할당받은 메모리의 크기가 M(마지막 주소가 M)이라고 할 때 Top을 가리키는 포인터가 M보다 커지면 기억장치보다 큰 자료를 더 이상 저장할 수 없는 Overflow stack현상이 발생합니다. 아마 코딩을 하시게 되면 다음과 같은 문법이 많이 참고가 될 것입니다.

top = top + 1                //탑 포인터를 1 증가 시킴

if top > M                      //탑 포인터가 전체 메모리보다 크면 오버플로우

   overflow

else                               //아니면 top포인터 위치에 값 입력

   S(top) = 입력값

 

반대의 경우도 있습니다.

자료를 Pop 하려는데 Top을 가리키는 포인터가 0이면 아무 자료도 없는 상태입니다. 만약 여기서 Pop을 시키려고 하면 더 이상 삭제할 자료가 없어 Underflow가 발생하게 됩니다.

if top = 0

 underflow

else 

 값 <- S(top)

 top = top - 1

---

Stack에 대한 예시를 좀 보면

A, C, B, D로 스택에 입력을 할 예정일 때 출력한 결과가 될 수 없는 경우는 어떤 것인지 확인해 보겠습니다.

우선 보기는 다음과 같습니다.

1. C, B, A, D

2. C, D, B, A

3. B, C, D, A

4. B, A, D, C

 

1번 보기부터 살펴보겠습니다.

<1번 보기 결과 도출 과정>

2번 보기

<2번 보기 결과 도출 과정>

3번 보기

<3번 보기 결과 도출 과정>

4번의 보기는 나올 수가 없습니다.

---

그렇다면 이런 자료 저장 방식은 어디에서 활용을 할까요?

다들 ctrl + z (이전 단계로 돌아가기) 많이 사용해보셨을 겁니다. 스택은 인터럽트 등의 장애에서 복귀를 위해서 많이 사용합니다. 그리고 계산을 위해서도 값들을 입력하는 방식으로 많이 사용을 합니다.

 

다음은 큐(Queue)와 데크(Deque)입니다.

큐는 선형 리스트의 입구에서는 삽입이 되고 반대편의 출구로는 삭제가 되는 자료구조입니다. 스택의 후입 선출(LIFO)과는 반대로 큐는 선입선출(FIFO: First In First Out)의 방식이며 시작과 끝을 표시하는 두 개의 포인터를 가집니다.

<큐(Queue) 구조>

프런트(Front) 포인터는 가장 먼저 삽입된 자료가 기억되는 공간을 가리킵니다. 삭제 작업을 할 때 사용이 되며 리어(Rear) 포인터는 가장 마지막에 삽입된 자료가 저장된 위치를 기억하는 포인터입니다. 삽입을 할 때 사용이 됩니다. 큐는 지하철이나 버스에서 줄 서있는 상태를 생각하시면 됩니다. 먼저 줄을 선 사람이 먼저 탑승하는 구조입니다. 

 

데크(Deque)는 삽입과 삭제가 양쪽에서 모두 가능한 구조를 의미합니다. 

<데크(Deque) 구조>

스택(Stack)과 큐(Queue)의 장점만 따서 만든 구조입니다. 데크에는 입력 제한과 출력 제한이 있는데 입력 제한은 입력이 한족에서만 발생하고 출력은 양쪽에서 일어나는 것을 말하고 출력 제한은 양쪽에서 입력이 발생하지만 출력은 한 곳에서만 이루어지는 것을 의미합니다.

 

이상으로 선형 자료구조인 스택(Stack), 큐(Queue), 데크(Deque)에 대한 포스팅을 마치겠습니다.

 

오늘도 똑구의 꿀팁 블로그를 방문해 주셔서 감사합니다.