스택과 큐

스택과 큐

이번에는 스택과 큐에 대해서 알아보도록 하겠다.

스택

스택은 FILO(First In Last Out) 구조의 자료구조로 책 더미를 생각하면 편하다.

스택에서 데이터 삽입하는 것을 PUSH, 데이터를 빼는 것을 POP이라고 한다. 먼저 들어간 것이 가장 아래에 쌓이기 때문에 가장 나중에 들어간 것이 먼저 나오게 된다.

큐

스택과는 달리 FIFO(First In First Out) 구조의 자료구조로 우리가 흔히 생각하는 줄 서기를 생각하면 편하다.

큐에서 데이터 삽입을 Enqueue, 데이터 빼는 것을 Dequeue라고 하는데 스택과는 다르게 먼저 들어간 것이 먼저 나온다.

스택과 큐의 구현

스택과 큐는 배열과 연결리스트 두 가지 전부 다 구현이 가능하다. 실질적으로 스택에서의 push와 pop, 큐에서의 enqueue와 dequeue 기능만 구현이 되어있으면 되기 때문이다.

배열에서의 스택과 큐 구현

스택

원하는 크기의 배열을 선언한 뒤 해당 배열에 데이터가 들어있는 가장 끝을 top으로 둔다. 처음 배열을 선언하면 데이터 값이 아무것도 없을테니 0번지를 top으로 둔다. 이후 데이터를 push 때마다 top의 값을 +1씩하여 값을 넣고 데이터를 pop할때마다 top 번지에 있는 데이터를 반환하고 top을 -1씩해주면 스택같이 사용할 수 있다.

큐

스택과 동일하게 원하는 크기의 배열을 선언한다. 이 경우 조금 다른게 큐의 경우 먼저 들어온게 먼저 나가야하고 일반적으로 이런 큐를 배열로 선언한다는건 데이터를 무한정 크기로 잡을 게 아니라면 원형 큐로 쓰고 있을 가능성이 높다.

그림에서는 크기가 5인 배열을 상정하고 그렸는데 HEAD가 끝에 다다를경우 배열 크기만큼 모듈러 연산을 하여 HEAD를 0으로 돌리며 TAIL의 경우도 마찬가지로 모듈러 연산을 통해 끝으로 돌린다. 만약 Dequeue시 TAIL이 HEAD와 같다면 큐가 비어있는 것이고 Enqueue시에 TAIL 직전에 HEAD가 있다면 큐가 꽉찬 것이다.

연결리스트에서의 스택과 큐 구현

스택

배열에 비해서는 용량의 제한이 적다. 왜냐하면 필요한대로 할당해서 붙이면 되기 때문이다. 단, 끝의 위치는 갖고 있어야하기에 다음과 같은 형태로 PUSH와 POP이 이루어진다.

큐

큐 역시 배열에 비해서는 용량의 제한이 적다. 스택과 마찬가지로 필요한대로 할당하여 끝에 붙이면 되기 때문이다. 단, head를 반환한 뒤에 이전 head의 바로 뒤의 노드를 head로 선정해야하므로 그 다음노드의 주소를 갖고 있어야한다. 따라서 head에서 tail쪽으로 link가 나가는 형태이다. 그렇기 때문에 다음과 같은 형태로 Enqueue와 Dequeue가 이루어진다.