06 - Stack & Queue

 

스택(Stack) — 쌓이는 구조, 후입선출(LIFO)

 

스택이란 자료 구조는 "빨래통"을 떠올리시면 됩니다.

데이터를 한 곳에서만 넣었다 뺄 수 있습니다.

가장 밑에 있는 빨래를 뺄 수 있나요? 아뇨 가장 위에서만 빨래를 빼거나 넣을 수 있습니다

그러면 가장 처음에 넣은 빨래는? 가장 늦게 나오겠죠 가장 마지막에 넣은 빨래는?

가장 빨리 나옵니다

 

이런 자료 구조를 Last In First Out 이라고 해서 LIFO 라고 부릅니다.

 

즉, 가장 최근에 넣은 걸 먼저 뽑고 예전에 넣은 걸 늦게 뽑고 싶다면 Stack 을 써야 합니다.

 

 

그렇다면 이런 자료구조는 왜? 필요할까

 

바로, 넣은 순서를 쌓아두고 있기 때문입니다.

그 순서가 필요한 경우가 있습니다. 예를 들어 컴퓨터의 되돌리기(Ctrl + Z) 기능을 아시나요?

직전에 했던 행동을 되돌리고 싶을 때 사용하는 기능인데,

이를 위해서는 내가 했던 행동들을 순서대로 기억해야 하므로 스택을 사용합니다.

 

스택 이라는 자료 구조에서 제공하는 기능은 다음과 같습니다

push(data) : 맨 앞에 데이터 넣기

pop() : 맨 앞의 데이터 뽑기

peek() : 맨 앞의 데이터 보기

isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기

 

스택은 뭘로 구현하면 좋을까요? 데이터 넣고 뽑는 걸 자주하는 자료 구조입니다 

이전시간에 배웠던 링크드 리스트와 유사하게 구현할 수 있습니다

 

push, pop, peek, is_empty를 코드상으로 구현해봤다.

스택문제 - 탑

탑의 높이를 마치 레이저로 쏴서 제일 높이 쌓은 숫자부터 출력하는 문제이다.

 

큐(Queue) — 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조. (FIFO)

 

큐란 자료 구조는 "놀이기구"를 떠올리시면 됩니다. 놀이기구는 한 줄로 섰다가,

한 줄로 나옵니다! 데이터를 한쪽 끝으로 넣고, 반대쪽에서 빠져 나옵니다.

 

이런 자료 구조를 First In First Out 이라고 해서 FIFO 라고 부릅니다.

 

이런 자료구조가 왜 필요할까요? 순서대로 처리되어야 하는 일에 필요하기 때문입니다

주문이 들어왔을 때 먼저 들어온 순서대로 처리해야 할 때, 혹은 먼저 해야 하는 일들을 저장하고 싶을 때 큐를 사용합니다.

 

큐라는 자료 구조에서 제공하는 기능은 다음과 같습니다

 

enqueue(data) : 맨 뒤에 데이터 추가하기

 

dequeue() : 맨 앞의 데이터 뽑기

 

peek() : 맨 앞의 데이터 보기

 

isEmpty(): 큐가 비었는지 안 비었는지 여부 반환해주기

 

과연 큐는 뭘로 구현하면 좋을까요? 데이터 넣고 뽑는 걸 자주하는 자료 구조입니다

스택과 마찬가지로 링크드 리스트와 유사하게 구현할 수 있습니다 아래 코드를 기반으로 한 번 같이 구현해보겠습니다

이 때, 스택과 다르게 큐는 끝과 시작의 노드를 전부 가지고 있어야 하므로, self.head 와 self.tail 을 가지고 시작합니다

enqueue,dequeue,peek,isEmpty,dequeue를 구현해보았다.

enqueue - 데이터 삽입

만약 현재 큐가 아래와 같다고 해봅시다. queue = [4] → [2] 큐에 3을 enqueue 하면 어떻게 되어야 할까요?

놀이기구니까 제일 뒤에 있는 데이터가 3이 되어야 합니다. 즉, [4] → [2] → [3] 가 되어야 합니다

dequeue - 데이터 삭제

이제 dequeue 이라는 함수를 구현해보겠습니다.

만약 현재 큐가 아래와 같다고 해봅시다. head tail [3] → [4] → [5] 큐에 dequeue을 하면 어떻게 되어야 할까요?

제일 앞에 있는 데이터인 [3]이 빠져야 합니다. 즉, 다음과 같이 되어야 합니다.

head tail [4] → [5] 즉, [4] 가 되어야 합니다 그러기 위해서는 head 에 [4] 를 지정하고, [3] 을 반환해주면 됩니다.

즉, 현재 head 의 값을 다른 변수에 저장해 둔 다음, head 가 지칭하는 노드를 현재 head 의 다음값으로 지정합니다.

그리고 아까 저장해둔 head 를 반환해주면 됩니다