Skip to main content

Queue & Stack

큐 (Queue)​

큐는 먼저 저장한 데이터가 먼저 출력되는 선입선출 (First In First Out) 형식으로 데이터를 저장하는 자료구조이다. 큐는 줄 서기와 비슷한 개념으로, 은행에서 고객이 줄을 서서 기다리면, 먼저 온 고객이 서비스를 받게 되는 맥락과 같은 개념이다.

주요 연산​

  1. Enqueue (인큐, 삽입)
    • 큐에 데이터를 추가하는 작업. 새로운 데이터가 큐의 뒤쪽에 추가된다.
    • 시간복잡도: O(1)
  2. Dequeue (디큐, 삭제)
    • 큐에서 데이터를 제거하는 작업. 가장 앞에 있는 데이터가 제거된다.
    • 시간복잡도: O(1) / Array로 구현시 O(N)
  3. Peek (피크, 조회)
    • 큐의 가장 앞에 있는 데이터를 조회하는 작업. 데이터를 제거하지는 않는다.
    • 시간복잡도: O(1)
  4. isEmpty (비어있는지 확인)
    • 큐가 비어있는지 여부를 확인하는 작업.
    • 시간복잡도: O(1)

특징​

  • 장점
    • 데이터의 삽입, 삭제가 빠르다.
    • 데이터를 입력 순서에 따라 처리해야 하는 작업에 적합하다.
  • 단점
    • 많은 큐 구현에서는 초기화 시 고정된 크기를 설정해야 한다. 큐가 가득 차면 더 이상 데이터를 삽입할 수 없기 때문에, 이를 해결하기 위해서는 큐의 크기를 늘리거나 데이터를 제거해야 한다. 크기를 동적으로 조정하는 큐(예: Python의 deque)도 있지만, 이러한 경우에도 크기 변경 시 성능 저하가 발생할 수 있다.
    • 순차적으로 데이터를 삽입하고 삭제하는 데 적합하지만, 특정 위치의 데이터를 직접 접근하거나 수정하는 작업은 비효율적이다.
  • 사용 사례
    • 작업 대기열
      • 여러 작업이 들어오면 가장 먼저 들어온 작업이 가장 먼저 수행되어야 하는 상황에서 큐를 활용할 수 있다.
    • 너비 우선 탐색(BFS)
      • 그래프에서 너비 우선 탐색을 수행할 때 큐를 사용하여 노드를 탐색 순서대로 저장하고 탐색할 수 있다.
    • 캐시(Cache) 구현
      • 캐시에 데이터를 저장하고 가져올 때에도 큐를 사용하여 가장 최근에 사용된 데이터를 저장하고 오래된 데이터를 제거할 수 있다.

구현​

from collections import deque

# Queue 생성
queue = deque()

# Queue에 데이터 삽입
queue.append('A')
queue.append('B')
queue.append('C')

# Queue에서 데이터 제거 (선입선출)
first_element = queue.popleft()
print(f'Removed Element: {first_element}')  # 출력: Removed Element: A

# Queue 상태 출력
print(f'Queue: {list(queue)}')  # 출력: Queue: ['B', 'C']
  • deque는 Python의 collections 모듈에서 제공하는 양방향 큐로, 큐의 구현에 적합하다. append() 메서드로 데이터를 추가하고, popleft() 메서드로 데이터를 제거할 수 있다.

시간복잡도​

연산시간 복잡도
삽입(Enqueue)O(1)
삭제(Dequeue)O(1)
접근(Acess)O(n)
탐색(Search)O(n)

스택 (Stack)​

스택은 시간 순서상 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 LIFO(Last In First Out) 형식으로 데이터를 저장하는 자료구조이다.

주요 연산​

  • Push (푸시)
    • 스택에 데이터를 추가하는 연산. 새로운 데이터가 스택의 맨 위에 쌓이게 된다.
    • 시간복잡도: O(1)
  • Pop (팝)
    • 스택에서 가장 위에 있는 데이터를 제거하는 연산. 가장 최근에 추가된 데이터가 제거된다.
    • 시간복잡도: O(1)
  • Top (탑)
    • 스택의 가장 위에 있는 데이터를 조회하는 연산이지만, 제거하지는 않는다.
    • 시간복잡도: O(1)

특징​

  • 장점
    • 데이터의 삽입, 삭제가 빠르다.
    • 후입선출 방식으로 최근에 추가된 데이터에 쉽게 접근할 수 있다.
  • 단점
    • 고정 크기 스택에서는 크기를 초과하는 데이터를 삽입하려고 할 때 스택 오버플로우(Overflow)가 발생할 수 있다. 동적 크기의 스택도 크기 증가 시 메모리 재할당이 필요하여 성능이 저하될 수 있다.
    • 스택은 후입선출(LIFO) 원칙에 따라 동작하기 때문에, 스택에 저장된 데이터 중간에 접근하거나 수정하는 것이 불가능하다.
  • 사용 사례
    • 함수 호출과 반환
      • 함수가 호출될 때마다 호출 스택에 현재 상태를 저장하고, 함수가 반환되면 해당 상태를 스택에서 제거하는데 스택이 사용된다.
    • 뒤로 가기 (Undo) 기능
      • 편집기나 그래픽 소프트웨어에서 사용자의 작업을 스택에 기록하여 되돌리기(undo)를 구현할 때 활용된다.
    • 깊이 우선 탐색
      • DFS(깊이 우선 탐색) 알고리즘에서 스택을 활용하여 재귀 호출을 대체할 수 있다.
    • 역순 출력
      • 데이터를 역순으로 출력하거나 처리해야 하는 경우 스택을 사용할 수 있다.

구현​

# Stack 생성
stack = []

# Stack에 데이터 삽입
stack.append('A')
stack.append('B')
stack.append('C')

# Stack에서 데이터 제거 (후입선출)
last_element = stack.pop()
print(f'Removed Element: {last_element}')  # 출력: Removed Element: C

# Stack 상태 출력
print(f'Stack: {stack}')  # 출력: Stack: ['A', 'B']
  • 스택은 파이썬의 리스트를 사용하여 간단히 구현할 수 있다. append() 메서드로 데이터를 추가하고, pop() 메서드로 데이터를 제거한다.

시간복잡도​

연산시간 복잡도
삽입(Push)O(1)
삭제(Pop)O(1)
접근(Access)O(n)
탐색(Search)O(n)