스택 & 큐

스택과 큐의 차이는 기술 면접에서 등장하는 단골 질문이라고 합니다. 비전공자인 저는 프로젝트 중 컴퓨터사이언스에 접근할 기회가 거의 없었습니다. 때문에 스택과 큐를 코딩으로 만들 줄은 알았지만 그 단점과 보완의 방식에 대한 지식을 이번에 새롭게 알게 되었습니다.

1. 스택(stack)

스택은 자료구조에서 무언가 쌓는 의미를 갖는 자료구조입니다. 순서대로 쌓인 스택의 맨 첫번째 데이터를 꺼내려면 맨 마지막에 쌓은 데이터부터 차례로 꺼내야합니다. 이를 일반적으로 LIFO ( Last In First Out ) 이라고 부릅니다. 스택에서 사용되는 함수로는 push()와 pop()이 있습니다. push() 는 자료를 넣을 때, pop()은 자료를 삭제할 때 사용됩니다. 앞에서 스택은 LIFO 방식으로 사용되기 때문에 push()를 하게되면 맨 마지막 index에 입력되고, pop()을 하게되면 맨 마지막 index의 데이터가 삭제됩니다.

이러한 성격때문에 스택 방식은 먼저 들어온 작업이 마지막에 이루어지는 구조를 이룹니다. 때문에 우선순위에 관련된 문제가 생길 수 있으며 데이터가 새로 계속해서 들어오게되면 맨 처음 들어온 데이터가 오랫동안 잔류하는 경우가 생깁니다.

2. 큐(que)

큐는 처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO ( First In First Out ) 의 구조로 되어있습니다. 입출력이 양방향에서 이루어지며 Front 는 가장 먼저 입력된 데이터의 index이고, Rear는 가장 나중에 입력된 데이터의 index 입니다. 데이터 의 입력을 Enqueue, 삭제를 Dequeue라고 합니다.

큐는 데이터를 모두 입력 후 하나씩 삭제를 하게 되면 Rear는 그대로 있고 Front가 움직입니다. Front가 점점 뒤로 가면서 결국 Rear와 만나게 됩니다. 그렇게 되면 마지막에는 Front 위치의 앞에는 비어있는 공간이 있지만 Rear가 움직일 수 있는 공간이 없기 때문에 오버플로우 현상을 발생기킵니다. 더이상 데이터가 들어갈 공간이 없다고 인식하는 것입니다. 때문에 데이터 삭제를 명령한 후 뒤에 있는 데이터들을 앞으로 옮겨와야 합니다. 이러한 방식은 소수의 데이터에서는 괜찮을 수 있을지 몰라도 데이터의 양이 많아지면 연산에 많은 시간이 걸리게 됩니다. 때문에 나온 원형 큐가 있습니다. 지금까지 데이터의 큐의 형태를 선형으로 봤다면 원형으로 생각하고 순환이 이루어지게 합니다. 배열의 Rear가 다음 index로 넘어갈 때 ’( index + 1 ) % ( 배열의 사이즈 )’를 이용하여 배열의 마지막 index에서 맨 처음 index로 넘어가게 할 수 있습니다.

* 연결리스트
앞에서 설명한 스택과 큐에는 한계가 있습니다. 배열의 크기를 처음에 정해주고 배열의 크기를 넘어서면 에러가 발생합니다. 이는 배열을 사용하지 않는 열결리스트를 사용함으로 보완할 수 있습니다. 앞선 큐에서는 Front와 Rear가 index였지만 연결리스트에서는 Node입니다. 새로 추가할 데이터를 Node에 넣은 후 Rear에 이 Node를 넣어줍니다. 이 방식으로 스택과 큐를 구현하면 메모리가 허용하는한 많은 데이터를 저장할 수 있습니다.