Stack과 Queue는 동작 방식에서 아주 큰 차이를 보인다. 자세한 내용은 아래에서 알아보도록 하자.
참고로 Stack과 Queue는 대부분의 프로그래밍 언어에서 라이브러리를 지원하기 때문에 구현에 대해서는 자세히 다루지 않겠다.
Stack
Stack은 우리말로 "쌓다"라는 뜻을 가진다. 자료구조 Stack도 말그대로 데이터를 쌓는다는 개념이다.
벽돌을 위로 쌓는다고 생각해보자. 우리는 벽돌을 쌓을 때 기존에 쌓여있는 벽돌 위에 새로운 벽돌을 놓을 것이다.
만약 아래에 쌓여있는 벽돌 중 파손된 벽돌을 발견하였고 그것을 교체해야 한다면 어떻게 해야 할까?
당연하게도 파손된 벽돌을 꺼내기 위해 가장 위에 있는 벽돌부터 하나씩 빼내게 될 것이다.
벽돌의 예와 같이 자료구조 Stack은 LIFO(Last-In First-Out)의 원칙을 따른다. 즉, 가장 마지막에 들어온 데이터가 가장 먼저 나간다는 뜻이다.
아래의 그림은 Stack을 간략히 표현한 그림이다.
Stack 의 주요 연산
- Push : Stack에 데이터를 넣는 연산이다. Stack의 가장 꼭대기(Top)에 데이터가 삽입된다.
- Pop : Stack에서 데이터를 빼는 연산이다. Stack의 가장 꼭대기(Top)에 존재하는 데이터를 빼내게 된다.
Stack을 구현하는 것은 매우 간단하다. 배열 또는 리스트로 쉽게 구현이 가능한데 배열의 경우 배열 사이즈의 제약이 있다.
배열과 리스트 모두 Top 위치 정보를 별도의 변수에 저장하고 push, pop연산마다 Top 위치에 접근하여 연산을 한 후에 Top 위치를 갱신해주면 된다.
Queue
Queue는 한국말로 대기 줄이라는 뜻을 가진다. 자료구조 Queue도 말그대로 데이터를 줄 세운다는 개념이다.
위 그림과 같이 은행에 사람들이 줄을 서 있다고 생각해보자. 사람들이 은행에서 보는 업무가 모두 동일하다고 가정할 때 가장 늦게 들어온 사람은 맨 뒤에 서서 대기를 할 것이고 가장 먼저 들어온 사람은 제일 처음으로 은행 업무를 볼 것이다.
자료구조 Queue와 Stack의 차이점이 바로 Queue는 FIFO(First-In First-Out)의 원칙을 따른다는 것이다. 즉, 가장 먼저 들어온 데이터가 가장 먼저 나간다.
아래의 그림은 Queue을 간략히 표현한 그림이다.
Queue의 주요 연산
- Push : Queue에 데이터를 넣는 연산이다. Queue의 가장 뒤(Back)에 데이터가 삽입된다.
- Pop : Queue에서 데이터를 빼는 연산이다. Queue의 가장 앞(Front)에 존재하는 데이터를 빼내게 된다.
Stack과 마찬가지로 Queue를 구현하는 것 또한 매우 간단하다. 마찬가지로 배열 또는 리스트로 쉽게 구현이 가능한데 배열의 경우 배열 사이즈의 제약이 있다.
배열과 리스트 모두 데이터의 Front와 Back의 위치 정보를 별도의 변수에 저장한다.
push연산 시 Back의 위치에 접근하여 그 다음 위치에 데이터를 삽입하고 Back의 위치를 갱신해주면 된다. 유사하게 pop연산 시 Front의 위치에 접근하여 데이터를 꺼내고 그 다음 데이터의 위치로 Front의 위치를 갱신해주면 된다.
배열의 경우 pop, push연산을 자주 하다보면 저장공간의 낭비가 발생할 수 있다. 그 이유는 Front, Back의 위치는 연산을 할 수록 증가하기 때문이다.
따라서 Queue를 배열로 구현할 때 원형 배열 형태로 구현을 하게되고 이를 원형 큐라고 한다.
위 그림은 원형 큐의 예시이다. 원형(환형) 큐란 고정 크기 배열에서 Back이 마지막 인덱스를 초과할 때 인덱스 0이 빈 공간 (Front > 0)인 경우 Back의 위치를 0으로 지정하여 마치 배열이 원형인 것처럼 동작하게 구현하는 것이다. (Front가 마지막 인덱스를 초과하는 경우에도 동일하다.) 이를 통해 저장 공간의 낭비를 효과적으로 줄일 수 있다. 물론 원형 큐도 배열 사이즈의 제약이 있는 것은 마찬가지이다.
이렇게 Stack, Queue에 대하여 알아보았다. 다음 포스팅에서는 Stack과 Queue의 기능을 모두 할 수 있는 Deque에 대하여 알아볼 것이다.
