안녕하세요 기린입니다 :)
이번 시간에는 스택과 큐를 배워보겠습니다. 스택(Stack)과 큐(Queue)는 컴퓨터 공학에서 가장 기본이 되는 자료구조입니다. 말 그대로 자료를 표현하고 처리하는 방법에 관한 것입니다. 예를 들자면 스택은 택배 상하차를 생각하시면 되고, 큐는 은행 창구를 생각하시면 됩니다.
먼저, 스택부터 확인해봅시다. 어렵지 않은 개념이니 천천히 생각해보시죠 :]
스택은 아래와 같이 출구가 하나밖에 없는 상태로 표현할 수 있습니다.
첫 번째 명령어 삽입(7)이 실행되면 7이 삽입됩니다.
다음 명령어 삽입(5)이 실행되면 위와 같습니다.
이후에 원소 4가 삽입됩니다.
이제 명령어 삭제()가 수행되는데, 삭제할 때는 항상 가장 최근에 들어간 원소가 나갑니다.
이후에 원소 6이 삽입됩니다.
결과적으로 모든 명령을 수행한 뒤의 결과는 위와 같습니다. 스택 구조는 정말 어렵지 않습니다. 알고리즘은 이러한 스택이나 큐를 이용해서 문제를 해결하는 방법이라고 할 수 있습니다.
#include <iostream>
#include <stack>
using namespace std;
int main(void) {
stack<int> s;
s.push(7);
s.push(5);
s.push(4);
s.pop();
s.push(6);
s.pop();
while(!s.empty()) {
cout << s.top() << ' ';
s.pop();
}
return 0;
}
위 소스는 스택의 대표적인 예제로 STL 라이브러리를 사용한 것입니다. 사실 스택은 직접 구현해볼 수도 있지만, 앞서 정렬 알고리즘을 이해하신 분들께는 쉬운 개념이라 생략하고, 바로 C++ STL Stack 라이브러리에 대해 다루어 본 것입니다.
다음은 스택(Stack)에 이어서 큐(Queue)에 대해 알아보도록 합시다. 큐 또한 대표적인 자료구조의 일종으로 먼저 들어온 것이 먼저 나가는(First in First Out, FIFO)를 가지고 있습니다. 편의점에서 일해보신 분들이라면 아실 텐데요, 선입선출 말 그대로 먼저 들어온 것이 먼저 나간다 라는 뜻이죠. 이러한 큐는 중간에 새치기가 불가능한 구조입니다.
위와 같이 큐가 준비되어있다고 생각해봅시다. 스택과는 다르게 통로의 양 옆이 뚫려 있어 왼쪽이 출구, 오른쪽이 입구라고 볼 수 있습니다. 세 번째 명령어까지 실행되어 큐에 7 5 4 가 들어간 모습입니다.
삭제 명령어가 실행되면, 위와 같이 가장 먼저 들어왔었던 7이 사라지게 됩니다.
이어서 6이 삽입되면 위와 같습니다.
마지막 삭제 명령이 실행되면 남은 원소는 4와 6이 되죠 :]
#include <iostream>
#include <queue>
using namespace std;
int main(void) {
queue<int> q;
q.push(7);
q.push(5);
q.push(4);
q.pop();
q.push(6);
q.pop();
while(!q.empty()) {
cout << q.front() << ' ';
q.pop();
}
return 0;
}
결과적으로 큐는 먼저 들어간 원소부터 하나씩 빠져나 4와 6이 출력되는 걸 볼 수 있습니다. 큐 나 스택은 각자 자체만으로는 큰 의미가 없고 하나의 자료구조로써 나중에 다양한 알고리즘을 설계할 때 그 토대가 되는 역할을 수행합니다. 큐 또한 구현 자체는 매우 간단하기 때문에 바로 C++ STL Queue 라이브러리를 활용해 예제를 만들었습니다.
자 그럼 즐거운 코딩하세요 :)
문의: ralla0405@gmail.com
