오늘은 자료구조의 가장 기본이 되는 스택과 큐에 대해서 알아보도록 하겠습니다!
목차
0. 스택
스택(Stack)이란 이름 그대로 순서대로 쌓인 무언가를 의미합니다.
우리가 뭘 쌓을 때 아래 요소를 뺀다고 생각하는 일은 전혀 없잖아요? 그냥 아래서부터 위로 쭉쭉 쌓습니다.
그래서 아래 요소를 뺄 수가 없게 되는 것이죠..
이 말은 스택에서 무언가를 빼고 싶다면 놓은 순서 반대로 빼야한다는 말이 됩니다!
이걸 유식하게 말하면 LIFO(Last In First Out) 특징을 가진다고 말할 수 있습니다.
가장 마지막에 들어온 친구가 가장 먼저 나가게 되는 것이죠.
스택의 변화는 모두 Top이라는 위치에서 실행됩니다.
스택 안에 요소를 넣는 작업을 Push, 요소를 빼는 작업을 Pop이라고 부르죠.
두 작업은 모두 O(1)이 걸립니다.
그냥 직관적으로 봐도 맨 위에 놓고 빼니까 말이죠!!
스택을 가장 흔하게 사용하는 곳은 바로 실행취소입니다.
내가 방금 한 작업은 스택의 맨 위에 쌓이게 되고, ctrl+z를 누르면 스택이 하나 없어져서 이전 상태로 돌아가게 되는 것이죠!
또한 알고리즘의 DFS(깊이 우선 탐색)에서도 사용하고, 재귀함수를 사용할 때 쌓이는 콜스택에서도 스택이 사용됩니다!
또 하나의 중요한 특징은 스택에는 크기가 정해져 있다는 것입니다.
만약 정해진 스택의 크기 이상으로 무언가를 넣으려고 한다면 그 유명한 StackOverflow가 발생하게 되고, 빈 스택에서 무언가를 빼내려고 한다면 StackUnderflow가 발생하게 됩니다.
1. 큐
큐는 이름 그대로 순서대로 이어져있는 줄을 의미합니다.
매표소를 생각해봅시다.
내가 앞에 줄을 서 있었는데, 누군가 새치기하면 화가 나겠죠?
큐에서는 이런 행위가 절대로 용인되지 않습니다.
먼저 들어온 사람이 먼저 표를 사고 다 사면 그 사람이 나가고 다음 사람이 표를 살 수 있는 구조인 것이죠.
이 특성을 유식하게 말하면 FIFO(First In First Out)이라고 할 수 있습니다.
가장 처음 들어온 친구가 가장 먼저 나간다는 뜻이죠.
큐의 변화는 양쪽 끝에서 일어납니다.
큐 안에 요소를 넣는 작업을 Enqueue, 요소를 빼는 작업을 Dequeue라고 부릅니다.
그리고 두 작업 모두 O(1) 시간이 걸립니다.
표사고 나간다고 해서 다른 사람들이 서로 위치를 바꾸거나 하지 않으니까요! 앞으로 조금씩 이동하는 것은 무시합시다;;;
가장 흔하게 들 수 있는 큐의 예시가 바로 매표소 구현입니다.
또한 알고리즘의 BFS(너비 우선 탐색) 구현에도 사용되고, 프로세스 스케줄링에서도 사용합니다. 내가 먼저 실행한 작업이 당연히 먼저 실행되야 하는게 논리적으로 맞으니까요!
스택과 똑같이 큐에는 크기가 정해져 있습니다.
만약 정해진 큐의 크기 이상으로 무언가를 넣으려고 한다면 QueueOverflow가 발생하게 되고, 빈 스택에서 무언가를 빼내려고 한다면 QueueUnderflow가 발생하게 됩니다.
스택과의 조금 다른 특징이라면 큐는 원형으로 많이 사용합니다.
사람 사는 세상이라면 아까 말했던 것처럼 표를 사고 누가 나가면 앞으로 조금씩 나가는 정도는 간단한 일이지만, 메모리에서는 앞으로 이동하는 것이 조금 어려울 수 있겠죠? (1부터 10까지 저장소를 정해놨는데, 10까지 다 저장하면..? 11에 저장 못해서 오류가 나겠죠?)
그렇기 때문에 정해진 크기만큼의 큐가 있다면, 큐의 끝에 데이터를 저장하고 나면 다시 맨 앞으로 자동으로 되돌아가서 새로운 데이터를 저장하는 방식을 많이 사용합니다.
이렇게 원형 큐를 구현할 때 맨 앞과 맨 뒤를 쉽게 구분하기 위해서 추가적인 Reserved 공간이 필요하다는 것을 알아두면 좋습니다!
아래 예시를 살펴봅시다. front는 0에서 시작하고, rear는 max-1인 4에서 시작합니다. (공백상태)
이제 요소 5개가 순서대로 다 들어가서 꽉 찼다고 생각합시다. 그러면 rear는 한바퀴 돌아서 다시 4에 위치하게 됩니다.
뭔가 이상합니다. 공백일 때도 front가 0이고 rear가 4였는데, 꽉 차도 front가 0이고 rear가 4가 됩니다.
이걸 쉽게 구분하기 위해서 1칸을 비워두게 되는 것입니다!
최근댓글