[CS - 자료구조] 큐 vs 스택 (Queue vs Stack)

Queue

 

• 개념
  • 시간 순서상 먼저 들어온 데이터가 먼저 추출되는 선입선출(FIFO, First In First Out) 방식으로 데이터를 저장하는 자료구조
  • 선형 (Linear) 자료구조
  • Queue Overflow : Queue의 용량보다 데이터를 더 추가하려는 경우 발생
  • Queue Underflow : Queue가 비었음에도 데이터를 삭제하려는 경우 발생
  • 단순 투 포인터로만 구현하게 되면, push/pop 연산 시 포인터가 증가만 하기 때문에 메모리 공간 낭비 발생 (계속 뒤쪽으로만 추가된다는 의미)
  • 코드

  struct Queue {
    // Property
    private var array: [Int]
    private var f: Int
    private var r: Int
    private var capacity: Int
    
    // Initializer
    init(_ capacity: Int) {
      self.capacity = capacity
      self.array = Array(repeating: 0, count: capacity)
      self.f = 0
      self.r = 0
    }
    
    // Method
    mutating func push(_ data: Int) {
      if self.r >= self.capacity {
        print("Overflow")
      } else {
        self.array[self.r] = data
        self.r += 1
      }
    }
    
    mutating func pop() {
      if self.r - self.f <= 0 {
        print("Underflow")
      } else {
        self.array[self.f] = 0
        self.f += 1
      }
    }
    
    func front() -> Int {
      return self.r - self.f <= 0 ? -1: self.array[self.f]
    }
    
    func size() -> Int {
      return self.r - self.f
    }
  }
  

• enqueue, dequeue
  • enqueue
    • queue에 데이터를 추가하는 것
    • 시간복잡도 : O(1) → 맨 끝 위치에 데이터를 한 번 추가하는 것이기 때문
  • dequeue
    • queue에서 데이터를 추출하는 것
    • 시간복잡도 : O(1) → 맨 끝 위치에 데이터를 한 번 추출하는 것이기 때문
• 구현 방식
  • Array-Based Queue
    • 1. 미리 할당된 메모리 크기 만큼의 Array를 선언하고
         [] [] [] [] [] [] []
      2. Array에 데이터를 넣고
         [1] [2] [3] [4] [] []
      3. enqueue, dequeue를 통해 Queue로 활용
         [] [] [3] [4] [5] []
    • Array라서 fixed-size의 메모리 내에서 데이터를 다루기 때문에, 남는 메모리 발생할 가능성이 있음
      [] [] [3] [4] [5] []
    • → 메모리 낭비 막기 위해 Circular Queue를 주로 사용
  • List-Based Queue
    • Linked List로 구현한 Queue
    • Array-Based에 비해 메모리 재할당, 낭비 걱정 X

 

• Circular Queue
  • Array-Based Queue에서 enqueue를 하다, 메모리를 초과하는 경우에 빈 공간에 데이터를 enqueue하는 방식
  • front, rear 변수 또는 포인터로 시작점, 끝점을 표시할 수 있다.
  • 1. 이런 모양의 Queue가 있다
    [] [] [4] [5] [] []
  • 2. enqueue(6), enqueue(7)을 한다
    [] [] [4] [5] [6] [7]
  • 3. enqueue(8)을 하면 앞 공간에 채워진다
    [8] [] [4] [5] [6] [7]
  • front, rear
  • 메모리를 효율적으로 사용할 수 있기 때문에 Array-Based Queue의 일반적인 방식이 됨

 

• 확장
  • deque (double-ended queue) : 양쪽에서 enqueue, dequeue가 가능한 구조
  • priority queue (우선순위 큐): FIFO 방식으로 데이터가 관리되는 게 아닌, 들어온 순서와 상관 없이 우선순위에 의해 데이터가 추출되는 자료구조

 

• 활용
  • (하나의 자원을 공유하는) 프린터, CPU task scheduling, Cache 구현, 너비우선탐색 (BFS)

 

• Q) Array-Based Queue와 List-Based Queue는 어떤 차이가 있나요?
  • Array-Based Ququeue
    • Circular Queue로 구현
    • 메모리 초과하는 경우 동적 배열의 resize로 확장시켜야 함
    • enqueue의 시간복잡도 : (amortized) O(1)
  • List-Based Queue
    • 보통 singly-linked list로 구현
    • Linked-List이기 때문에 enqueue, dequeue 모두 O(1)
  • 요약
    • 둘 다 enqueue, dequeue 시간복잡도가 O(1)
    • 하지만, Array-Based Queue의 퍼포먼스가 전반적으로 좋음.
    • 왜냐하면, List-Based Queue의 전반적인 런타임이 느리기 때문 (데이터 추가할 때마다 메모리 할당하기 때문에)
    • 간혹, worst case로 resize때 Array-Based Queue의 속도가 훨씬 느림

 

Stack

 

• 개념
  • 시간 순서상 제일 늦게 들어온 데이터가 먼저 추출되는 후입선출(LIFO, Last In First Out) 방식으로 데이터를 저장하는 자료구조
  • 선형 (Linear) 자료구조
  • Stack Overflow : 스택에는 정해진 크기가 있다. 다 찼음에도 데이터를 추가하려는 경우 Stack Overflow 발생
  • Stack Underflow : 스택이 비었음에도 데이터를 추출하려는 경우 Stack Underflow 발생
  • 코드

struct Stack {
	// Property
  var array: [Int]
  var len: Int
  var capacity: Int
  
  // Initializer
  init(_ capacity: Int) {
    self.capacity = capacity
    self.array = Array(repeating: 0, count: capacity)
    self.len = 0
  }
  
  // Method
  mutating func push(_ data: Int) {
    if len >= capacity {
      print("Overflow")
    } else {
      self.array[self.len] = data
      self.len += 1
    }
  }
  
  mutating func pop() {
    if self.len <= 0 {
      print("Underflow")
    } else {
      self.array[self.len - 1] = 0
      self.len -= 1
    }
  }
  
  func top() -> Int {
    return self.len <= 0 ? -1: self.array[len - 1]
  }
}

 

• push, pop
  • push
    • stack에 데이터를 추가하는 것
    • 시간복잡도 O(1) → 맨 끝 위치에 데이터를 한 번 추가하는 것이기 때문
  • pop
    • stack에서 데이터를 추출하는 것
    • 시간복잡도 O(1) → 맨 끝 위치에서 데이터를 한 번 추출하는 것이기 때문

 

• 활용
  • 괄호 유효성 검사, 페이지 뒤로가기, 깊이우선탐색 (DFS), call stack, 후위 표기법 연산

 

Stack 두 개를 이용해 Queue를 구현해보기

 

• enqueue
  • push와 동일
  • **O(1)**의 시간복잡도

 

• dequeue
  • pop으로 시간상 처음 추가한 데이터인 1을 추출하고 싶다
    1. instack, outstack을 만들고, instack에 데이터를 채운다
       [1] [2] [3] [4] [] [] [] [] [] [] [] []
    2. 비어있는 outstack에, instack에서 각 데이터에 대해 push, pop을 해준다
       [1] [2] [3] [] [] [] → [1] [2] [] [] [] [] → … → [] [] [] [] [] []
       [4] [] [] [] [] []         [4] [3] [] [] [] []             [4] [3] [2] [1] [] []
    3. outstack에서 pop을 하면 1이 나온다
  • amortized O(1)의 시간복잡도
    • 이유 : outstack을 처음 채울 때만 O(n)이고, 그 후 pop을 하는 경우에는 O(1)이기 때문

 

Queue 두 개를 이용해 Stack을 구현해보기

 

• push
  • enqueue와 동일
  • O(1)의 시간복잡도

 

• pop
  • dequeue로 시간상 제일 최근에 추가한 데이터인 4를 추출하고 싶다
    1. 두 개의 큐를 각각 q1, q2라고 하자 (순서대로 q1, q2)
       [1] [2] [3] [4] [] [] [] [] [] [] [] []
    2. q1에서 4만 남을 때까지 dequeue, enqueue하여 q2에 채운다
       [] [2] [3] [4] [] [] → [] [] [3] [4] [] [] → … → [] [] [] [4] [] []
       [1] [] [] [] [] []          [1] [2] [] [] [] []               [1] [2] [3] [] [] []
    3. q1에서 dequeue를 하면 4가 나온다
    4. 다음 작업을 위해 q1, q2의 이름을 바꾼다 (swap)
  • O(n)의 시간복잡도
    • 이유 매번 데이터를 n번 옮겨야 하기 때문

 

큐 vs 우선순위 큐 (Queue vs Priority Queue)

 

우선순위 큐 (Priority Queue)

• 개념
  • 데이터가 추가된 시간 순서에 따라 먼저 추출되는 큐와 달리, 우선순위에 의해 데이터가 추출되는 자료구조
  • 우선순위 큐는 힙(Heap)을 이용하여 구현한다

 

힙 (Heap)

• 개념
  • 우선순위 큐를 구현하기 위해 고안된 완전 이진트리 형태의 자료구조
• 종류
  • 최대 힙(max heap)
    • 각 node에 저장된 값은 child node의 값보다 크거나 같다
    • → root node의 값이 제일 큼
  • 최소 힙(min heap)
    • 각 node에 저장된 값은 child node의 값보다 작거나 같다
    • → root node의 값이 제일 작음
• 구현
  • 힙은 완전 이진’트리’ 형태. 트리는 보통 Linked-List로 구현
    • → 각 node들이 child node에 대한 address가 필요해서 인듯
  • 하지만, 힙은 Array로 구현. 왜냐하면, 새로운 node가 물리적 연속성, 순차성을 확보해서 마지막 위치에 추가되어야 하기 때문
    • → 구현이 훨씬 수월해진다
  • 그렇게 되면, array의 index 만으로 node의 부모-자식 관계 정의 가능 (완전 이진트리 특성 활용)
    • n번째 node의 left child node : 2n
    • n번째 node의 right child node : 2n+1
    • n번째 child node의 parent node : n/2

 

• Heap push 과정 (max heap이라 가정)
  • 1. 우선 맨 마지막 node에 추가
    2. 부모 node와 비교해서 본인이 더 큰 값이면, 부모와 자리 바꿈 (swap)
    3. 본인이 부모와 비교해서 더 작거나 같은 값일 때까지 2)번 반복
  • → O(logn)의 시간복잡도
    • 트리의 길이가 logn이기 때문

 

• Heap pop 과정
  • 1. root node 추출(우선순위 큐 특성상 우선순위가 제일 높은 root node가 추출 (크기가 제일 큼))
    2. 맨 마지막 node를 기존 root node 위치에 넣는다
    3. 자식 node와 비교해서 본인이 더 작은 값이면, 자식과 자리 바꿈 (node) (만약, 자식 node 둘 다 본인보다 크면, 그중 더 큰 값과 자리 바꿈)
    4. 본인이 자식과 비교해서 더 크거나 같은 값일 때까지 3)번 반복
  • → O(logn)의 시간복잡도
    • 트리의 길이가 logn이기 때문