스택(Stack)
스택은 입력과 출력이 한 방향으로 제한되어 있습니다.
다른 말로는 "LIFO(Last In First Out, 후입선출) : 가장 마지막에 들어간 것이 가장 먼저 나옴" 이라고도 합니다.
스택은 책상위에 동전을 쌓는다!라고 생각하셔도 됩니다.
동전을 5개 쌓아올렸고 다시 원래대로 돌리려면 가장 위에있는(Last In) 동전부터 다시 책상에 내려놓아야겠죠(First Out)?
스택은 언제 사용할까요?
함수의 콜스택, 문자열 역순 출력, 연산자 후위표기법에서 사용됩니다.
큐(Queue)
큐는 입력과 출력을 양쪽 끝으로 제한합니다(Front, Rear)
그렇기 때문에 스택과 반대로 "FIFO(First In First Out, 선입선출) : 가장 먼저 들어온 것이 가장 먼저 나옴" 입니다.
큐는 언제 사용될까요?
버퍼, BFS에서 사용됩니다!
선형 큐의 문제점
큐는 들어올 때 rear로 들어오지만, 나올 때는 front부터 빠지는 특성을 가지고 있습니다.
- 데이터 넣음 : enQueue()
- 데이터 뺌 : deQueue()
- 비어있는 지 확인 : isEmpty()
- 꽉차있는 지 확인 : isFull()
데이터를 넣고 뺄 때 해당 값의 위치를 기억해야 하는데, 이 위치를 기억하고 있는 게 front와 rear입니다.(스택에서 스택 포인터 역할)
- front : deQueue 할 위치 기억
- rear : enQueue 할 위치 기억
여기서 선형 큐의 문제점이 도출됩니다!
선형 큐에서 삽입 및 삭제를 반복하다 보면, rear가 맨 마지막 인덱스를 가리키고, 앞에는 비어 있을 수 있지만 이를 꽉 찼다고 인식합니다.
이는 실제 데이터 아래 그림처럼 삭제 때마다 데이터를 한 칸 앞으로 이동시키지 않고, 인덱스 단위로 큐의 연산을 진행했기 때문입니다.
원형 큐(Circular Queue)
이러한 문제점을 해결하고자 선형 큐 대신 원형 큐를 사용합니다!
원형 큐도 일차원 배열을 사용하지만 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 간주하며, 초기 공백 상태일 때 front와 rear는 0입니다. 공백, 포화 상태를 쉽게 구분하기 위해 인덱스는 0이 아닌 1부터 시작합니다.
enQueue를 하면 rear+1, deQueue를 하면 front+1을 해주고, rear + 1 == front이면 포화 상태를 의미합니다.
{ enQueue시 rear = (rear + 1) % (배열의 크기), deQueue 시 front = (front + 1) % (배열의 크기) }
이상으로 스택과 큐에 대해서 알아보았습니다.
앞선 포스팅에서 배웠듯 만약 크기의 제한이 없는 스택, 큐를 만들고 싶다면 연결리스트를 이용하면 될 것 같네요!
이 글은 Gyoogle님의 Tech Interview 자료를 공부하고 작성한 글임을 알려드립니다.