[자료구조] 스택(Stack)과 큐(Queue) 이해하기

스택(Stack)과 큐(Queue)는 서로 닮았지만 다른 자료구조입니다.

비교를 통해 두 자료구조를 알아보겠습니다.

---

스택의 개념

'쌓다' 라는 의미를 가지고 있는 스택(Stack)은 그 의미와 같이 데이터를 차곡차곡 쌓아올린 형태로 자료를 구성합니다.

책상 위에 쌓아둔 책이나 주방에 쌓아둔 접시를 예로 들 수 있는데요.

 

스택은 후입선출(Last-in First-out)의 자료구조입니다.

앞자만 따서 LIFO 구조라고 하며, 마지막에 들어온 것이 먼저 나간다라는 뜻입니다.

입구와 출구가 같은 자료구조라고 할 수 있겠습니다.

 

입구와 출구가 하나밖에 없으니 데이터의 삽입과 삭제가 한 방향에서만 이루어집니다.

스택에서는 흔히 데이터의 삽입 연산을 push, 삭제 연산을 pop 이라 칭합니다.

삽입과 삭제가 일어나는 위치는 top이라고 합니다.

 

스택(Stack) 그림

스택의 활용

스택 구조가 활용된 예시입니다.

 

- 안드로이드의 액티비티

- 프로그램에서의 시스템 스택

 

안드로이드 어플리케이션의 액티비티가 스택을 설명하기 좋은 예시입니다.

 

사용자가 버튼을 클릭하여 새로운 화면이 열리는 것을 push에, 뒤로 가기를 눌러 현재 화면이 사라지고 다시 이전 화면으로 돌아가는 것을 pop에 비유할 수 있습니다.

 

사용자가 현재 보고 있는 화면은 top이라고 할 수 있겠습니다.

 

---

큐의 개념

큐(Queue)는 스택과 비슷하지만 다른 자료구조입니다.

 

큐는 선입선출(First-in First-out)의 구조를 가지고 있습니다.

역시 앞자를 따서 FIFO 구조라고 하며, 먼저 들어온 것이 먼저 나간다라는 뜻입니다.

공연장에서 입장을 기다리는 관객들을 예시로 들 수 있습니다.

 

큐에서는 데이터의 삽입과 삭제 연산을 주로 enQueue와 deQueue라 칭합니다.

FIFO 구조를 실현하기 위해 큐는 스택과 다르게 입구와 출구가 각각 나뉘어져 있습니다.

 

이 때 출구는 머리(front)로 정해 삭제 연산만 수행하고, 입구는 꼬리(rear)로 정해 삽입 연산만 수행합니다.

 

큐(Queue) 그림

 

큐의 활용

큐는 입력된 순서대로 작업을 수행해야 할 때 활용할 수 있습니다.

예시로 게임 대전 매칭 시스템을 들 수 있습니다.

 

게임 플레이를 원하는 유저들이 플레이 버튼을 클릭하면(enQueue) 다른 유저와 대전하길 기다리다가, 매칭이 성사되면 게임이 시작되는(deQueue) 시스템을 그림으로 표현해 보았습니다.

 

 

스택과 큐에서의 삽입과 삭제 연산을 표로 비교하면 다음과 같습니다.

스택과 큐의 삽입/삭제 연산 비교