스택·큐·데크와 표기식 계산

핵심 구조 한눈에 보기

스택(Stack), 큐(Queue), 데크(Deque)는 모두 데이터를 넣고 꺼내는 순서를 제한하는 추상 자료형이다. 차이는 어느 끝에서 삽입·삭제하는가에 있다.

같은 입력을 넣었을 때 스택은 역순으로, 큐는 입력 순서대로 삭제한다.

스택

같은 순서 1·2·3을 넣어도 스택은 3부터, 큐는 1부터 꺼낸다.

스택은 가장 나중에 삽입한 원소를 가장 먼저 삭제하는 후입선출(Last-In, First-Out, LIFO) 구조다. 삽입과 삭제는 모두 top에서 수행한다.

예를 들어 빈 스택에 7 → 3 → 5 → 2 순서로 push하면 top은 2다. 이어서 두 번 pop하면 2, 5가 차례로 나오고 스택에는 7, 3이 남는다.

오버플로와 언더플로

고정 크기 배열로 만든 스택에서 top이 현재 원소의 인덱스를 가리키고 초기값이 -1이라고 하자.

• 공백 조건: top == -1
• 포화 조건: top == N - 1
• 오버플로(overflow): 포화 상태에서 push를 시도
• 언더플로(underflow): 공백 상태에서 pop을 시도

구현에 따라 top이 현재 원소가 아니라 다음 빈칸을 가리킬 수도 있다. 따라서 문제에 배열 크기와 top의 의미가 제시되면 그 규칙을 먼저 확인해야 한다.

스택의 push, pop, peek은 적절한 배열 또는 연결 구조에서 보통 O(1)이다. 함수 호출과 복귀, 괄호 검사, 실행 취소, 깊이 우선 처리, 표기식 변환과 계산처럼 가장 최근 상태를 먼저 사용하는 작업에 적합하다.

스택의 가능한 출력 순열은 마지막에 들어간 미삭제 원소가 먼저 나오는 조건을 매 시점 만족해야 한다. 다음 출력 원소 위에 다른 원소가 남아 있으면 그 출력은 불가능하다.

괄호 검사는 여는 괄호와 닫는 괄호의 개수뿐 아니라 중첩 순서와 종류를 확인한다. 닫는 괄호를 만났을 때 비어 있는 스택이나 다른 종류의 top은 즉시 오류다.

큐

일반적인 큐는 가장 먼저 삽입한 원소를 가장 먼저 삭제하는 선입선출(First-In, First-Out, FIFO) 구조다.

• enqueue(x): rear 쪽에 원소를 삽입한다.
• dequeue(): front 쪽 원소를 삭제하고 반환한다.
• peek() 또는 front(): 첫 원소를 삭제하지 않고 확인한다.

빈 큐에 A → B → C를 차례로 넣고 두 번 삭제하면 A, B가 나온다. 적절한 포인터를 유지하는 배열 큐나 연결 큐에서는 enqueue와 dequeue가 보통 O(1)이다.

선형 큐와 거짓 포화

배열로 만든 선형 큐에서 front와 rear가 한 방향으로만 증가하면, 앞에서 삭제해 생긴 빈칸이 있어도 rear가 배열 끝에 도달한 뒤 새 원소를 넣지 못할 수 있다. 실제로 빈칸이 남았지만 포화처럼 보이는 현상을 거짓 포화(false overflow)라고 한다.

원형 큐는 배열의 마지막 인덱스 다음을 첫 인덱스로 연결한 것처럼 취급하여 앞쪽 빈 공간을 다시 사용한다. 배열 크기를 N이라고 하면 다음 위치는 다음 식으로 계산한다.

next(i) = (i + 1) mod N

예를 들어 N = 5이고 현재 인덱스가 4이면 다음 인덱스는 (4 + 1) mod 5 = 0이다.

원형 큐의 공백·포화 조건

다음은 시험에서 자주 사용하는 한 칸을 비워 두는 방식이다.

• front: 첫 원소 바로 앞의 빈칸을 가리킴
• rear: 마지막 원소를 가리킴
• 초기 상태: front == rear
• 공백 조건: front == rear
• 포화 조건: (rear + 1) mod N == front
• 실제 저장 가능 원소 수: N - 1

삽입할 때는 먼저 rear를 다음 칸으로 이동한 뒤 저장하고, 삭제할 때는 front를 다음 칸으로 이동한 뒤 그 원소를 반환한다.

한 칸을 비우지 않고 count나 별도의 상태 플래그를 두어 N칸을 모두 사용하는 구현도 있다. 그러므로 원형 큐의 포화 조건과 실제 용량은 구현 규칙에 따라 달라진다. 단순히 front == rear만 보고 공백과 포화를 동시에 판단해서는 안 된다.

FIFO 구조의 데이터를 차례로 스택에 넣고 다시 꺼내면 순서가 뒤집힌다. 여러 자료구조를 거치는 문제는 각 단계의 앞·뒤와 top을 구분해 추적한다.

데크

데크(Double-Ended Queue, Deque)는 front와 rear 양쪽 끝에서 삽입과 삭제가 가능한 구조다. 일반 큐처럼 사용하면 뒤에 넣고 앞에서 빼는 FIFO가 되고, 한쪽 끝만 사용하면 스택처럼 LIFO로 동작할 수 있다.

데크와 우선순위 큐는 같은 개념이 아니다. 데크는 연산 가능한 끝의 위치로 규칙을 정하고, 우선순위 큐는 원소의 우선순위에 따라 삭제 순서를 정한다.

중위·전위·후위 표기

산술식 표기법은 연산자가 피연산자에 대해 어느 위치에 놓이는지로 구분한다.

두 자리 이상의 수나 여러 글자 식별자가 포함되면 토큰을 공백으로 구분해야 한다. 예를 들어 12 3 +는 12와 3을 더하는 후위식이다.

우선순위로 식의 구조 정하기

일반적인 산술식에서는 다음 순서를 적용한다.

1. 괄호 안의 식
2. 곱셈·나눗셈·나머지: *, /, %
3. 덧셈·뺄셈: +, -

같은 우선순위의 이항 연산자는 별도 지시가 없으면 보통 왼쪽부터 결합한다. 문제에서 다른 우선순위나 결합 방향을 제시하면 그 규칙을 따른다.

중위식의 연산 구조를 먼저 확정한 뒤 다음 순서로 읽으면 전위식과 후위식을 만들 수 있다.

• 전위식: 연산자 → 왼쪽 피연산자 또는 부분식 → 오른쪽 피연산자 또는 부분식
• 후위식: 왼쪽 피연산자 또는 부분식 → 오른쪽 피연산자 또는 부분식 → 연산자

A - B / C에서는 나눗셈이 먼저이므로 전체 식은 A - (B / C)다. 따라서 후위식을 A B - C /로 쓰면 원래 식과 다른 (A - B) / C가 된다.

중위식을 후위식으로 변환하는 절차

연산자 스택을 사용하는 기본 절차는 다음과 같다.

1. 피연산자는 즉시 출력한다.
2. 여는 괄호 (는 스택에 넣는다.
3. 닫는 괄호 )를 만나면 (가 나올 때까지 연산자를 꺼내 출력하고 (는 버린다.
4. 연산자를 만나면 스택 위의 연산자가 더 높은 우선순위이거나, 같은 우선순위의 왼쪽 결합 연산자이면 먼저 꺼내 출력한다. 그다음 현재 연산자를 넣는다.
5. 입력을 모두 읽으면 스택에 남은 연산자를 차례로 꺼내 출력한다.

A * (B + C)의 변환 과정은 다음과 같다. 연산자 스택의 오른쪽이 top이다.

후위식 계산

후위식은 왼쪽에서 오른쪽으로 읽으며 피연산자를 스택에 넣는다. 이항 연산자를 만나면 두 값을 꺼내 계산 결과를 다시 넣는다.

1. right = pop() — 오른쪽 피연산자
2. left = pop() — 왼쪽 피연산자
3. push(left 연산자 right)

뺄셈과 나눗셈은 피연산자 순서를 바꾸면 결과가 달라지므로 특히 주의한다.

후위식 8 2 3 * +의 계산 과정은 다음과 같다.

입력을 모두 처리했을 때 스택에 값이 정확히 하나 남아야 정상적인 식이다. 위 식의 결과는 14다. 예를 들어 8 2 /에서 먼저 꺼낸 2가 오른쪽 피연산자이므로 계산은 8 / 2다.

후위식은 이항 연산 직전에 스택 값이 두 개 이상 필요하다. 입력 종료 때 값 하나가 남는 조건만 검사하지 말고 각 연산의 피연산자 부족도 검사한다.

전위식 계산

전위식은 오른쪽에서 왼쪽으로 읽으면 스택으로 계산할 수 있다.

1. 피연산자를 만나면 스택에 넣는다.
2. 연산자를 만나면 먼저 꺼낸 값을 왼쪽 피연산자, 다음 값을 오른쪽 피연산자로 사용한다.
3. 계산 결과를 다시 넣는다.

전위식 + 8 * 2 3은 8 + (2 × 3)이므로 결과는 14다.

연산 비용과 선택 기준

스택·큐·데크에서 특정 값을 찾는 작업은 일반적으로 O(n)이다. 끝 연산이 O(1)이라는 사실과 임의 검색도 O(1)이라는 주장은 다르다.