스택과 큐 — LIFO와 FIFO

스택과 큐는 데이터를 넣고 빼는 순서에 규칙을 둔 선형 자료구조다. 정처기 필기에서는 연산을 몇 번 수행한 뒤 남는 값이나 출력 순서를 추적하는 문제, 스택으로 만들 수 있는 출력 순열, 원형 큐의 포화·공백 조건이 반복해서 나온다.

스택 (Stack) — LIFO

한쪽 끝(top)에서만 삽입과 삭제가 일어나는 구조다. 마지막에 넣은 것이 먼저 나온다(LIFO, Last-In First-Out).

• 연산: push(삽입), pop(삭제), peek 또는 top(맨 위 확인)
• 1, 2, 3을 차례로 push한 뒤 pop을 반복하면 3, 2, 1 순서로 나온다.
• 응용: 함수 호출(콜 스택)과 재귀, 괄호 짝 검사, 수식의 후위 표기 변환, 웹 브라우저의 뒤로 가기, 인터럽트 처리 시 복귀 주소 저장

큐 (Queue) — FIFO

뒤(rear)로 넣고 앞(front)에서 빼는 구조다. 먼저 넣은 것이 먼저 나온다(FIFO, First-In First-Out).

• 연산: enqueue(삽입), dequeue(삭제)
• 스택은 top 하나만 움직이지만, 큐는 front와 rear 두 포인터가 움직인다.
• 응용: 프로세스 준비 큐(CPU 스케줄링), 프린터 대기열, BFS 탐색, 입출력 버퍼

원형 큐와 덱

배열로 만든 선형 큐는 dequeue를 반복하면 앞쪽 칸이 버려져, 자리가 남는데도 rear가 끝에 닿아 못 넣는 상황이 생긴다. 배열의 끝과 처음을 이어 붙여 이 낭비를 없앤 것이 원형 큐다.

• 크기 n인 배열에서 포인터는 (i + 1) mod n으로 한 칸씩 돈다.
• 공백 조건: front == rear
• 포화 조건: (rear + 1) mod n == front
• 공백과 포화를 구분하려고 한 칸을 항상 비워 두므로, 실제로 저장할 수 있는 것은 n-1개다.

덱(Deque)은 양쪽 끝 모두에서 삽입·삭제가 가능한 구조로, 제한을 어떻게 두느냐에 따라 스택처럼도 큐처럼도 쓸 수 있다.

시험에 자주 나오는 포인트

• 연산 추적: push A → push B → pop → push C → pop → pop의 출력은 B, C, A다. top의 위치를 그리며 따라가면 틀리지 않는다.
• 스택 출력 가능 순열: 1, 2, 3을 순서대로 push할 때 3, 1, 2는 만들 수 없다. 3이 먼저 나왔다면 스택에는 위에서부터 2, 1 순서로 쌓여 있어, 다음에 나올 수 있는 것은 2뿐이기 때문이다.
• 원형 큐의 포화 조건 (rear + 1) mod n == front는 공식 그대로 출제된다. 공백 조건과 짝으로 외운다.
• 약어 뒤집기 함정: “스택은 FIFO 구조다”는 틀린 진술이다. 스택은 LIFO, 큐는 FIFO.