코딩테스트에서는 굉장히 중요한 자료구조지만, 면접에서 단독으로 물어보는 경우는 많지 않다.
스택 Stack
스택은 마지막에 들어온 데이터를 먼저 내보내는 후입선출(LIFO)의 자료구조다. 새로운 원소를 스택의 가장 위에 삽입(push)하고, 가장 위의 원소를 삭제(pop)한다.
장점 : top을 통해 접근하기 때문에 데이터 접근, 삽입, 삭제가 빠르다.
단점 : top 위치 외의 데이터에 접근할 수 없어 탐색이 불가능하다.
활용 예시 : 웹 브라우저 방문기록(뒤로가기), 깊이 우선 탐색(DFS)
✅ 연산과 시간복잡도
top 포인터 1개로 삽입/ 삭제 전부 처리하고, 모든 연산은 $O(1)$ 시간복잡도를 갖는다.
push() : 새로운 원소 삽입
pop() : 마지막 원소 삭제
top() : 마지막 원소 확인
empty() : 스택이 비어있는지 확인
✅ 스택 구현 방법
배열이나 링크드 리스트로 구현할 수 있다. list-base는 push 할 때마다 메모리 할당이 일어나 전반적인 runtime이 느려 array-base 구현이 전반적으로 성능이 더 좋다. 하지만 Resize가 빈번히 발생하는 경우에는 array-base 구현이 훨씬 더 느릴 수 있다.
배열로 구현할 경우 마지막 스택의 인덱스를 기억하고 있으면 삽입과 삭제가 O(1)의 시간복잡도를 갖는다. 가득찬 경우 dynamic array와 같은 방법으로 배열의 크기를 확장해야 한다.
링크드 리스트로 구현할 경우 push는 단순히 마지막 노드에 append를 하는 것으로 구현하고 pop은 마지막 원소를 삭제하고 top을 변경하면 된다.
✅ 스택 두 개 이용해 큐 구현하기
큐의 enqueue()를 구현할 때 첫 번째 스택을 사용하고, dequeue()를 구현할 때 두 번째 스택을 사용하면 큐를 구현할 수 있다.
편의상 enqueue()에 사용할 스택을 instack이라고 부르고 dequeue()에 사용할 스택을 outstack이라고 칭한다.
enqueue() : instack에 push()를 하여 데이터를 저장
dequeue() :
1) outstack이 비어 있다면 instack에서 outstack으로 모든 데이터를 옮겨 넣고 outstack의 top을 추출
enqueue(3) → enqueue(5) → dequeue()→ enqueue(1)→ dequeue() 를 예시로 할 때, 큐는 [3, 5] 를 출력해야 한다
instack에 차례로 원소를 추가한다.
outstack이 비어있으므로 instack의 모든 원소를 outstack으로 옮긴다. (instack.pop() -> outstack.push())
그리고 oustack의 top 위치의 원소를 추출한다.
instack에 원소를 추가한다.
outstack이 비어있지 않으므로 top 원소를 추출한다.
그 때의 시간복잡도
enqueue() : instack.push()를 한 번만 하면 되기 때문에 시간복잡도 $O(1)$
dequeue() : amortized $O(1)$
outstack이 비어있는 경우 instack에 있는 n개의 데이터를 instack.pop()을 한 이후에 outstack.push()를 해줘야 한다. 따라서 총 $2n$ 번의 연산이 실행되어야 하므로 $O(n)$의 시간복잡도를 갖는다.
outstack이 비어있지 않는 경우에는 outstack.pop()만 해주면 된다. $O(1)$
큐 Queue
큐는 처음 들어온 데이터를 먼저 내보내는 선입선출(FIFO) 자료구조다. 새로운 원소를 큐의 뒤에 삽입(enqueue)하고, 가장 앞에 있는 원소를 삭제(dequeue)한다.
장점 : 데이터 접근, 삽입, 삭제가 빠르다.
단점 : 중간 데이터에 접근할 수 없어 탐색이 불가능하다.
활용 예시 : 프린터 출력 대기열, 프로세스 관리, 너비 우선 탐색(BFS)
✅ 연산과 시간복잡도
삽입할 때는 rear 포인터를 옮기고, 삭제할 때는 front 포인터를 옮기며 처리한다. front==rear 일 때 큐가 비어있을 때다. 모든 연산은 $O(1)$ 시간복잡도를 갖는다.
enqueue() : 새로운 원소 삽입
dequeue() : 첫 원소 삭제
empty() : 큐가 비어있는지 확인
✅ 큐 구현 방법
배열, 링크드 리스트로 구현할 수 있다. list-base는 enqueue 할 때마다 메모리 할당이 일어나 전반적인 runtime이 느려 array-base 구현이 전반적으로 성능이 더 좋다. 하지만 Resize가 빈번히 발생하는 경우에는 array-base 구현이 훨씬 더 느릴 수 있다.
배열로 구현할 경우 메모리를 효율적으로 사용하기 위해 원형 큐로 구현하는 것이 일반적이고, 가득찬 경우 dynamic array와 같은 방법으로 배열의 크기를 확장시킨다. 그럼에도 enqueue의 시간복잡도는 (amortized)O(1)을 유지할 수 있다.
링크드 리스트의 경우 enqueue는 단순히 마지막 노드에 append를 하는 것으로 구현되고 dequeue는 맨 앞의 원소를 삭제하고 first head를 변경하면 된다. 따라서 두 연산 모두 O(1)의 시간이 걸린다.
👆원형 큐란?
선형 큐의 경우 삽입과 삭제를 반복하면 한 번 데이터를 삽입/삭제한 위치를 재사용하지 않는 문제가 발생한다. 이 문제를 해결할 수 있는 앞과 뒤가 연결된 원형 구조를 갖는 큐를 원형 큐라고 한다.
✅ 큐 두 개로 스택 구현하기
스택의 push()와 pop()을 위해 큐를 하나씩 사용해 구현할 수 있다.
편의상 push()에 사용할 큐는 q1이라고 부르고 pop()에 사용할 큐를 q2라고 칭한다.
push() : q1에 enqueue()를 하여 데이터를 저장
pop()
q1에 저장된 데이터를 1개 제외하고 q2에 옮긴다.
q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다.
