Stack(스택)과 Queue(큐)

Stack

---

 

Stack이란?

---

단어 그대로 생각해보자. stack을 동사로 사용하면 '쌓다', '(쌓아서) 채우다'라는 뜻을 가지고 있다. 그렇다. 너무 당연하게도 스택은 데이터를 쌓아 올린 구조다.

흔히들 스택을 '바닥이 막힌 상자'로 비유하곤 한다. 우리가 바닥이 막힌 상자 위에 물건들을 하나씩 쌓아 올린다고 생각해보자. 이제 그 물건들을 다시 꺼낼 때에는 맨 위에 올라와있는 물건부터 역순으로 꺼내야 할 것이다. 바닥이 막혀있으니 맨 아래에서부터 꺼낼 수 없고, 중간에서 꺼내면 무너져 내리기 때문이다.

조금 전문적인 말을 통해 설명하자면, 스택은 LIFO(Last In First Out, 후입 선출) 구조를 가지고 있다. 즉, 나중에 들어온 데이터가 먼저 빠져나가는 자료구조다.

 

예시

---

위 그림은 스택 구조를 간단하게 표현한 것이다. 데이터들을 감싸고 있는 커다란 상자를 스택 자료구조라고 생각해보자. 우리는 이 스택 안에 캡틴 아메리카, 아이언맨, 토르, 헐크를 순서대로 집어넣었다. 이제 이 데이터를 다시 꺼낸다고 생각해보자. 스택에서는 입구가 하나뿐이다. 때문에 가장 나중에 들어간 헐크부터 역순으로 나올 수 있다. 이것이 앞서 설명한 LIFO의 개념이다.

스택에서는 입구와 출구가 한 곳뿐이다. 이 부분을 HEAD라고 한다. 스택 자료 구조에 데이터를 넣는 것은 일반적으로 push 연산이라고 하며, 반대로 마지막 삽입한 데이터를 빼는 것을 일반적으로 pop 연산이라고 한다. peek 연산도 존재하는데 이는 마지막 데이터를 스택에서 꺼내지 않고 값을 확인만 하는 것이다.

 

사례

---

• 웹 브라우저의 뒤로 가기
• undo(실행 취소) 명령

Queue

---

 

Queue란?

---

스택과 마찬가지로 단어의 뜻 먼저 살펴보도록 하자. Queue는 '줄', '줄을 서서 기다리다'라는 뜻을 가지고 있는 단어다. 단어 뜻만 봐도 감이 오듯, 큐는 데이터들이 줄 서있는 상태의 자료구조를 의미한다.

우리가 마트 계산대 앞에서 줄을 서있을 때를 생각해보자. 먼저 줄을 서 맨 앞에 있는 사람이 먼저 계산하는 것이 당연할 것이다. 물론 아닌 경우도 있지만 그건 그 사람의 도덕관념을 탓하도록 하자. 줄에 늦게 선 사람은 가장 늦게 계산하게 된다. 가장 먼저 온 사람은 가장 빨리, 가장 늦게 온 사람은 가장 늦게. 즉, 먼저 들어온 순서대로.

이를 조금 전문적으로 이야기해보자면, 큐는 FIFO(First In First Out, 선입선출) 구조를 가지고 있다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조다.

 

예시

---

위 그림은 큐를 구조를 간단하게 표현한 것이다. 데이터를 감싸고 있는 큰 상자를 큐 자료구조라고 생각해보자. 스택과는 다르게 앞, 뒤가 뚫려있다. 이 말은 데이터의 삽입과 삭제가 두 부분에서 이루어진다는 뜻이다. 캡틴 아메리카, 아이언맨, 토르, 헐크 순서대로 데이터를 넣었다면 꺼낼 때에도 캡틴 아메리카, 아이언맨, 토르, 헐크 순서대로 꺼낸다. 이것이 FIFO의 개념이다.

큐에서 데이터가 나가는 곳은 가장 앞 먼저 들어온 데이터 부분이다. 이 부분을 FRONT라고 부른다. 이 부분에서 이루어지는 연산은 데이터를 삭제하는 dequeue다. 데이터가 들어오는 부분은 큐의 가장 마지막 꼬리 부분 REAR다. 이곳에서는 데이터가 들어오는 enqueue 연산이 이루어진다.

 

사례

---

• 티켓팅 대기열
• 게임 대기열

 

스택과 큐 비교

---

 

참고

---

https://jud00.tistory.com/entry/자료구조-스택Stack과-큐Queue에-대해서-알아보자

[자료구조] 스택(Stack)과 큐(Queue)에 대해서 알아보자!

https://brightwon.tistory.com/8

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