[SW 정글 12일차] 스택과 큐 알아보기

오늘은 스택과 큐에 대해 정리해보려고 한다.

스택과 큐가 대충 어떠한 성격의 자료구조인지는 알고 있었지만 세세하게 알아본 적은 없었다.

기본적인 자료구조인 만큼 내가 공부한 내용을 정리하며 개념을 제대로 잡고자 한다.

 

 

1. 스택 (stack)

스택은 데이터를 임시로 저장하는 자료구조로 후입선출(LIFO)방식이다.

후입선출(LIFO)은 먼저 들어온 데이터가 나중에 나간다는 의미이다.

이렇게 말로만 설명하면 감이 잘 안올텐데 프링글스를 생각해보자.

단, 깨진 짜잘짜잘한 조각들은 생각하지 않고

프링글스를 만들 때는 과자칩을 하나하나 통에 넣을 것이다.

이렇게 하나, 둘 쌓인 과자칩은 우리가 가게에서 사게 될 것이고 우리는 프링글스를 위에서부터 하나씩 꺼내서 먹을 것이다.

위에서부터 꺼내 먹게 되면 들어온 순서가 가장 늦은 과자칩이 먼저 꺼내지게 되는 것을 그림에서 확인 할 수 있다.

이것이 스택의 특징인 LIFO이다.

 

여기서 스택(프링글스 통)에 데이터(과자칩)을 넣는 작업을 푸시(push)라고 하고 스택(프링글스 통)에서 데이터(과자칩)을 꺼내는 작업을 팝(pop)이라고 한다.

 

스택을 구현한다면 스택에 사용할 수 있는 여러 기능을 적용해볼 수 있다.

- 푸시(push): 스택에 데이터를 추가하는 작업

- 팝(pop): 스택의 꼭대기에서 데이터를 꺼내서 그 값을 반환하는 작업

- 피크(peek): 스택의 꼭대기에 있는 데이터를 조회하는 작업

- 클리어(clear): 스택에 있는 모든 데이터를 삭제하는 작업

- 파인드(find): 찾고자하는 값이 스택에 있는지 조회해보고 존재한다면 해당 인덱스를 반환하는 작업

- 카운트(count): 스택에 쌓여있는 데이터 개수를 반환하는 작업

- 덤프(dump): 스택에 쌓여있는 모든 데이터를 출력하는 작업

 

파이썬을 사용하는 나로서 이러한 스택과 기능들을 직접 구현하는 것이 아닌 파이썬에서 기본적으로 제공해주는 리스트만으로도 스택으로 사용할 수 있고 외장모듈로 collections에 있는 deque클래스를 사용해서 스택을 구현할 수 있다.

 

 

 

2. 큐(queue)

큐는 스택과 마찬가지로 데이터를 임시로 저장하는 자료구조 중 하나이다.

스택과 다른 점은 선입선출(FIFO)구조라는 것이다.

먼저 들어온 데이터가 먼저 나간다는 의미인데 이러한 큐의 구조를 알아보기 위해 터널을 생각하면 좋을 것 같다.

1차선 도로라고 생각하고 차들은 하나씩 터널에 순서대로 들어오게 될 것이다.

터널 안에는 들어온 순서대로 차들이 나가기 전까지 줄지어 있을 것이고 이제 순서대로 나갈 일만 남았다.

위 그림을 보면 먼저 들어온 차가 먼저나게 되는 것을 볼 수 있고 우리는 이를 자료구조에서 FIFO라고 부르는 것이다.

 

여기서 큐(터널)에 데이터(자동차)를 넣는 작업을 인큐(enqueue)라고 하고 큐(터널)에서 데이터(자동차)를 꺼내는 작업을 디큐(deque)라고 한다.

 

큐를 구현한다면 큐에 사용할 수 있는 여러 기능을 적용해볼 수 있다.

- 인큐(enque): 큐에 데이터를 추가하는 작업

- 디큐(deque): 큐의 맨 앞에서 데이터를 꺼내서 그 값을 반환하는 작업

- 피크(peek): 큐의 맨 앞에 있는 데이터를 조회하는 작업

- 클리어(clear): 큐에 있는 모든 데이터를 삭제하는 작업

- 파인드(find): 찾고자하는 값이 큐에 있는지 조회해보고 존재한다면 해당 인덱스를 반환하는 작업

- 카운트(count): 스택에 쌓여있는 데이터 개수를 반환하는 작업

- 덤프(dump): 스택에 쌓여있는 모든 데이터를 출력하는 작업

 

큐 자료구조를 사용하고자 한다면 스택에서 언급한 collections모듈에 있는 deque클래스를 사용하면 된다.

물론, 기본 리스트를 사용하여 deque할 때에는 pop(0), enque할 때에는 append()를 사용하면 되지만

deque클래스에서 제공하는 popleft()가 기본 리스트에 pop(0)을 하는 것보다 시간복잡도면에서 효율이 좋기 때문에 나는 deque클래스를 많이 사용한다.

 

그러면 여기서 궁금한 점이 생길 것이다.

deque는 스택을 구현할 때 사용한다고 했는데 큐를 구현할 때도 사용한다고 했다.

 

도대체 deque는 무엇일까?

deque는 덱이라고 불리며 양방향 대기열 구조를 가지고 있다.

큐는 한 쪽에서 Enque가 이루어지고 반대편에서 deque가 이루어진다.

그리고 스택은 같은 쪽에서 push와 pop이 이루어진다.

하지만 덱(deque)는 맨 앞과 맨 끝 양쪽에서 Enque(push)와 deque(pop)이 가능하다는 것이다.

어떻게 보면 큐와 스택을 합친 상태라고 생각할 수도 있다.

 

---

오늘부터 다시 몸에 피로도가 쌓인 느낌이 들면서 피곤함이 느껴진다.

집중도 잘 안되고 이전에는 나태함의 유혹이 오면 단호하게 거절했지만 요즘은 한번 쯤은 괜찮지 않을까하는 고민이 생긴다.

하지만 절대 나의 단기적인 목표를 이룰 때까지 나태함의 유혹에 넘어가지 않을 것이다.

오늘 한 것은 어제 공부한 이분탐색을 바탕으로 알고리즘 문제를 풀었는데 너무 어려웠다.

이분탐색 자체가 어려운 것이 아니라 문제를 보고 내가 어떠한 값을 찾고 싶은지, 그 값을 찾으면 정답을 어떻게 끄집어 낼지가 어려운 것이다.

지금 어렵다고 미루다 보면 그 때도 어려운 것은 마찬가지이니까 조금 더 시간을 투자해서 정복하고 싶다.

일단은 내가 조금 더 자신있는 스택, 큐, 우선순위 큐를 빠르게 해보고 이분탐색에 시간을 많이 투자해야겠다.

 

그리고 오늘은 뿌듯한 순간이 있었다.

여기서 가끔씩 나에게 질문을 던져주는 사람들이 있는데 그 사람들에게 나의 답변이 적절했는지 만족했는지를 확신할 수 없었고 뭔가 부족함을 느꼈다.

하지만, 오늘 옆에 있던 팀원이 어떠한 문제에 대한 이해가 안되어 나에게 질문을 주셨고 최대한 이해하기 쉽도록 설명을 했다.

그러고 나서 나에게 "덕분에 이해했어요"라는 말을 던져주었다.

뭔가 뿌듯하기도 하고 기쁘기도 하고 색다른 발전을 한 기분이였다.

앞으로도 나에게 답변을 얻어간 사람들이 만족할 수 있도록 해주고 싶다는 목표가 생겼다.

---

<참고 자료>

자료구조와 함께 배우는 알고리즘 입문 파이썬 편 (저자 Bohyoh Shibata, 옮김 강민)