자료구조 정리 - 스택(Stack)과 큐(Queue) 그리고 덱(Deque)

스택 (Stack)

핵심 개념:

• LIFO (Last In First Out) - 후입선출
• 나중에 들어간 게 먼저 나옴
• 접시 쌓기, 뒤로가기 버튼 같은 구조

기본 연산:

• push(x): 맨 위에 추가 - O(1)
• pop(): 맨 위 제거하고 반환 - O(1)
• peek()/top(): 맨 위 값만 확인 - O(1)
• isEmpty(): 비어있는지 확인 - O(1)

구현 방식:

1. 배열 기반: 동적 배열 사용 (대부분 이렇게)
2. 연결리스트 기반: 헤드에서만 삽입/삭제

시간복잡도:

• 모든 연산: O(1)

스택의 구현 예시 (배열 기반)

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, x):
        self.items.append(x)  # O(1)
    
    def pop(self):
        return self.items.pop()  # O(1)
    
    def peek(self):
        return self.items[-1]  # O(1)
    
    def isEmpty(self):
        return len(self.items) == 0

# 사용
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 3
print(stack.pop())  # 2

 

스택의 실제 사용 예시

 

1. 함수 호출 (Call Stack)

def a():
    b()

def b():
    c()

def c():
    print("hello")

a()

# 스택:
# [a] → [a, b] → [a, b, c] → [a, b] → [a] → []

 

 

2. 괄호 검사

def isValid(s):
    stack = []
    pairs = {'(': ')', '{': '}', '[': ']'}
    
    for char in s:
        if char in pairs:  # 여는 괄호
            stack.append(char)
        else:  # 닫는 괄호
            if not stack or pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0

print(isValid("(){}[]"))  # True
print(isValid("(]"))      # False

 

 

3. 브라우저 뒤로가기

방문: A → B → C
스택: [A] → [A, B] → [A, B, C]

뒤로가기: C → B
스택: [A, B] → [A]

 

 

4. 수식 계산 (후위표기법)

중위: 3 + 4
후위: 3 4 +

스택으로 계산:
[3] → [3, 4] → pop 4, pop 3, 계산 → [7]

 

 

 

큐 (Queue)

핵심 개념:

• FIFO (First In First Out) - 선입선출
• 먼저 들어간 게 먼저 나옴
• 줄 서기, 프린터 대기열 같은 구조

기본 연산:

• enqueue(x): 뒤에 추가 - O(1)
• dequeue(): 앞에서 제거하고 반환 - O(1)
• front()/peek(): 맨 앞 값만 확인 - O(1)
• isEmpty(): 비어있는지 확인 - O(1)

시간복잡도:

• 모든 연산: O(1)

 

큐의 구현 방식

 

1. 배열 기반 (단순)

class Queue:
    def __init__(self):
        self.items = []
    
    def enqueue(self, x):
        self.items.append(x)  # O(1)
    
    def dequeue(self):
        return self.items.pop(0)  # O(n) ← 문제!

→ pop(0)은 O(n)이라서 비효율적!

 

 

 

2. 원형 큐 (Circular Queue)

class CircularQueue:
    def __init__(self, size):
        self.queue = [None] * size
        self.front = 0
        self.rear = 0
        self.size = size
    
    def enqueue(self, x):
        self.queue[self.rear] = x
        self.rear = (self.rear + 1) % self.size  # 원형으로
    
    def dequeue(self):
        val = self.queue[self.front]
        self.front = (self.front + 1) % self.size
        return val

→ 모든 연산이 O(1)!

 

 

 

3. 덱(Deque) 사용 - 실무에서 가장 많이 씀

from collections import deque

q = deque()
q.append(1)      # enqueue
q.append(2)
q.popleft()      # dequeue - O(1)!

 

 

큐의 실제 사용 예시

 

 

1. BFS (너비 우선 탐색)

def bfs(graph, start):
    queue = deque([start])
    visited = set([start])
    
    while queue:
        node = queue.popleft()
        print(node)
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

 

 

 

2. 프린터 대기열

print_queue = deque()
print_queue.append("문서1")
print_queue.append("문서2")
print_queue.append("문서3")

# 출력: 문서1 → 문서2 → 문서3 순서로

 

 

 

3. 프로세스 스케줄링

CPU가 프로세스를 순서대로 처리
큐: [P1, P2, P3] → P1 실행 → [P2, P3]

 

 

스택 vs 큐 비교

 

이름	스택	큐
순서	LIFO (후입선출)	FIFO (선입선출)
삽입	push (맨 위)	enqueue (맨 뒤)
삭제	pop (맨 위)	dequeue (맨 앞)
용도	뒤로가기, 괄호검사, DFS	대기열, BFS, 스케줄링
구현	배열/연결리스트	원형큐/덱

 

 

덱 (Deque) - 언어별 제공

Python

 

 

python

from collections import deque

dq = deque()

# 양쪽 삽입
dq.append(1)       # 오른쪽 추가 - O(1)
dq.appendleft(2)   # 왼쪽 추가 - O(1)

# 양쪽 제거
dq.pop()           # 오른쪽 제거 - O(1)
dq.popleft()       # 왼쪽 제거 - O(1)

# 다른 연산
dq[0]              # 인덱스 접근 - O(n) ← 느림!
len(dq)            # 길이 - O(1)

# 스택처럼 사용
dq.append(x)
dq.pop()

# 큐처럼 사용
dq.append(x)
dq.popleft()

 

내부 구조:

• 이중 연결 리스트 기반
• 블록 단위로 메모리 할당 (효율적)

Java

 

// Deque 인터페이스 (권장)
Deque<Integer> dq = new ArrayDeque<>();

// 양쪽 삽입
dq.addLast(1);     // 오른쪽 추가 = offer, add
dq.addFirst(2);    // 왼쪽 추가 = offerFirst

// 양쪽 제거
dq.removeLast();   // 오른쪽 제거 = pollLast
dq.removeFirst();  // 왼쪽 제거 = poll, remove

// 조회
dq.peekFirst();    // 왼쪽 확인
dq.peekLast();     // 오른쪽 확인

// 스택처럼
dq.push(x);        // addFirst
dq.pop();          // removeFirst

// 큐처럼
dq.offer(x);       // addLast
dq.poll();         // removeFirst

 

 

구현체:

1. ArrayDeque
   • 원형 배열 기반
   • 모든 연산 O(1)
   • 동적 크기 조절
2. LinkedList
   • 이중 연결 리스트
   • Deque 인터페이스 구현
   • 메모리 오버헤드 큼

C++

 

#include <deque>

std::deque<int> dq;

// 양쪽 삽입
dq.push_back(1);    // 오른쪽 추가 - O(1)
dq.push_front(2);   // 왼쪽 추가 - O(1)

// 양쪽 제거
dq.pop_back();      // 오른쪽 제거 - O(1)
dq.pop_front();     // 왼쪽 제거 - O(1)

// 인덱스 접근
dq[0];              // O(1) ← Python과 다름!
dq.at(0);           // 범위 체크 포함

// 조회
dq.front();         // 맨 앞
dq.back();          // 맨 뒤

내부 구조:

• 여러 개의 고정 크기 배열 (청크)
• 청크들을 배열로 관리
• 인덱스 접근도 O(1)!

JavaScript

// 기본 배열을 deque처럼 사용

const dq = [];

// 양쪽 삽입
dq.push(1);        // 오른쪽 추가 - O(1)
dq.unshift(2);     // 왼쪽 추가 - O(n) ← 느림!

// 양쪽 제거
dq.pop();          // 오른쪽 제거 - O(1)
dq.shift();        // 왼쪽 제거 - O(n) ← 느림!

// 주의: shift/unshift는 O(n)이라 비효율적
// 진짜 deque가 필요하면 라이브러리 사용

 

 

언어별 덱 비교

 

언어	클래스/모듈	구현	인덱스 접근	권장도
Python	collections.deque	이중 연결 리스트	O(n)	⭐⭐⭐⭐⭐
Java	ArrayDeque	원형 배열	✗	⭐⭐⭐⭐⭐
Java	LinkedList	이중 연결 리스트	O(n)	⭐⭐
C++	std::deque	청크 배열	O(1)	⭐⭐⭐⭐⭐
JS	Array	동적 배열	O(1)	⭐⭐ (shift/unshift 느림)