스택과 큐 그리고 덱

2 min read

자료구조 스택 큐 덱

스택과 큐 그리고 덱은 모두 선형 데이터 구조이지만, 각각의 특성과 사용사례 등이 다르다.
이 글에서는 스택과 큐, 덱의 특성을 자세히 살펴보고,
세 자료구조를 비교하여 각각의 장단점과 적합한 사용 사례를 알아보겠다.

스택 (Stack)

스택은 후입선출(LIFO, Last In First Out) 원칙을 따르는 선형 자료구조이다.
스택에서는 마지막에 추가된 요소가 가장 먼저 제거된다.

스택의 주요 연산

  1. Push: 스택의 맨 위에 요소 추가
  2. Pop: 스택의 맨 위에서 요소 제거 및 해당 요소 반환
  3. Peek 또는 Top: 스택의 맨 위에 있는 요소를 제거하지 않고 반환
  4. IsEmpty: 스택이 비어 있는지 확인

스택의 특징

  • 후입선출(LIFO) 구조
    • 가장 마지막에 삽입된 요소가 가장 먼저 제거
  • 용도
    • 함수 호출 시 함수의 반환 주소 저장 및 알고리즘에서 재귀 대신 반복을 사용할 때 상태 저장 등에 사용
  • 구현
    • 배열이나 연결 리스트를 사용하여 구현 가능
    • 구현하는 자료구조의 종류에 따라 크기가 변경 여부 결정

큐 (Queue)

큐는 선입선출(FIFO, First In First Out) 원칙을 따르는 선형 자료구조이다.
큐에서는 가장 먼저 추가된 요소가 가장 먼저 제거된다.

큐의 주요 연산:

  1. Enqueue: 큐의 끝에 요소 추가
  2. Dequeue: 큐의 시작 부분에서 요소 제거 및 해당 요소 반환
  3. Front: 큐의 시작 부분에 있는 요소를 제거하지 않고 반환

큐의 특징

  • 선입선출(FIFO) 구조
    • 가장 먼저 삽입된 요소가 가장 먼저 제거
  • 용도
    • 운영체제의 작업 스케줄링, 네트워크 요청의 처리 순서 혹은 실시간 시스템에서 이벤트 처리 순서 관리, BFS(너비 우선 탐색) 알고리즘 등에 사용
  • 구현
    • 배열이나 연결 리스트를 사용하여 구현 가능
    • 구현하는 자료구조의 종류에 따라 크기가 변경 여부 결정

큐의 종류

  • 선형 큐(Linear Queue)
    • 가장 기본적인 큐로, 요소들이 선형으로 정렬.
    • 배열이나 연결 리스트로 구현 가능
  • 환형 큐(Circular Queue)
    • 선형 큐의 끝과 시작이 연결된 형태
    • 배열을 사용하여 메모리를 효율적으로 사용
  • 우선순위 큐(Priority Queue)
    • 각 요소가 우선순위를 가지고 있으며, 우선순위가 가장 높은 요소가 먼저 제거
    • 힙(heap)으로 구현
  • 덱(Deque, Double-Ended Queue)
    • 양쪽 끝에서 삽입과 삭제가 가능한 큐

덱 (Deque)

덱(Deque, Double-Ended Queue)은 선입선출(FIFO) 또는 후입선출(LIFO) 방식으로
작동할 수 있는 선형 자료구조이다.
덱에서는 양쪽 끝에서 삽입과 삭제가 가능하다.

덱의 주요 연산:

  1. AddFirst: 덱의 앞쪽에 요소 추가
  2. AddLast: 덱의 뒤쪽에 요소 추가
  3. RemoveFirst: 덱의 앞쪽에서 요소 제거 후 반환
  4. RemoveLast: 덱의 뒤쪽에서 요소 제거 후 반환
  5. PeekFirst: 덱의 앞쪽에 있는 요소를 제거하지 않고 조회
  6. PeekLast: 덱의 뒤쪽에 있는 요소를 제거하지 않고 조회

덱의 특징

  • 양방향 구조
    • 양쪽 끝에서 요소의 삽입과 삭제가 가능 (스택과 큐의 기능 모두 포함)
  • 용도
    • 스택 또는 큐로 사용 가능하므로, 다양한 시나리오에 적용
  • 구현
    • 배열이나 연결 리스트를 사용하여 구현 가능
    • 구현하는 자료구조의 종류에 따라 크기가 변경 여부 결정

참고 문헌