알고리즘 스택, 큐

알고리즘에서 가장 많이 활용이 되는 자료구조가 스택과 큐가 아닐까 싶습니다. 그냥 다른 수업을 들을 때도(메모리의 스택구조라던가, 데이터통신에서 큐잉이론이라던가) 정말 자주 나오는 주제인데요. 오늘은 알고리즘 측면에서 stack 라이브러리에 사용에 대해 이야기 해보겠습니다. 

 

일단 stack 은 접시 쌓기라고 생각하시면 됩니다. 접시를 쌓는다고 생각할때 위로 쌓이잖아요? 그리고 접시가 필요해서 하나 들고갈때는 가장 아래거를 들고 가나요? 아니죠. 가장 위에 있는 접시, 즉 가장 최근에 놔둔 접시를 가져갑니다. 이처럼 스택은 가장 최근에 들어온 게 가장 먼저 나가는 구조입니다. 아래 그림을 보면 조금 더 쉽게 이해가 되실 겁니다.

 

 스택을 삽입(Push) 하는 과정입니다. 4를 먼저 넣었기 때문에 4가 제일 밑에 놓여집니다. 다음은 하나를 꺼내보겠습니다. 가장 최근에 들어온 게 나가기 때문에 다음과 같습니다.

그 다음 

스택을 이런식으로 사용이 됩니다. 그럼 구현을 한 번 해보겠습니다. 자료구조 시간에는 이러한 스택을 직접 제작합니다. 하지만 알고리즘에서는 활용하는 정도라고 생각하시면 되겠습니다.

---

스택의 개념을 이해하셨다면 큐의 개념도 비교적 쉽게 이해하실 수 있습니다 .큐는 은행창구와 같은 개념입니다. 먼저 온 사람이 먼저 은행 서비스를 이용하는거처럼 먼저 들어온 원소가 먼저 나가는 구조입니다. 중간에 새치기는 할 수 없습니다. (사회적으로도 좋지 않습니다.) 큐는 굉장히 많이 활용이 되는 자료구조입니다. 그림을 보면 좀 더 쉽게 이해하실 수 있으실 겁니다.

배열이 큐에 삽입되는 과정

큐는 스택과 달리 양쪽이 뚫린 파이프 모양이라고 생각하시면 됩니다. Pop을 해보겠습니다. 큐이기 때문에 가장 먼저 들어온 원소가 가장 빨리 나가겠죠?

다음 원소를 꺼내면 

 

네. 간단한 큐의 동작을 알아보았습니다. 그럼 C++의 STL 로 구현을 해보겠습니다.

 

 

---

이렇게 큐와 스택에 대해 배워보았습니다. 

 

스택 - 먼저 들어온 게 마지막에 나감

큐 - 먼저 들어온 게 먼저 나감