[자료구조] 큐 Queue & 스택 Stack & 우선순위큐 priority queue & 힙 Heap 이란?

Queue 큐 란?

queue는 선입선출 FIFO(First In Frist Out)의 자료구조이다 시간복잡도는 enqueue O(1), dequeue O(1) 입니다.

활용 예시 Cache 구현, 프로세스 관리, 너비우선탐색(BFS) 등이 있습니다.

FIFO (First In First Out) 이란?

queue는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조이다.

enqueue & dequeue

queue에서 데이터를 추가하는 것을 enqueue라고 한다.

queue에서 데이터를 추출하는 것을 dequeue라고 한다.

enqueue의 경우 queue의 맨뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1)이다. 

dequeue의 경우 맨 앞의 데이터를 삭제하면 완료되기 때문에 동일하게 O(1)의 시간복잡도를 갖는다.

구현 방식

• Array-Based queue: enqueue와 dequeue 과정에서 남는 메모리가 생긴다. 따라서 메모리의 낭비를 줄이기 위해 주로 Circular queue형식으로 구현한다.
• List-Based: 재할당이나 메모리 낭비의 걱정을 할 필요가 없어진다.

원형큐 (circular queue)

queue의 개념에서 조금 확장한 자료구조들로는 양쪽에서 enqueue와 dequeue가 가능한 deque(double-ended queue)와 시간 순서가 아닌 우선순위가 높은 순서로 dequeue할 수 있는 priority queue가 있다.

활용 예시로는 하나의 자원을 공유하는 프린터나, CPU task scheduling, Cache 구현, 너비우선탐색(BFS) 등이 있다.

 

Array-Base와 List-Base 차이

Array-Base	queue는 circular queue로 구현하는 것이 일반적이다. 이는 메모리를 효율적으로 사용하기 위함이다. 또한, enqueue가 계속 발생하면 fixed size를 넘어서게 되기 때문에, dynamic array와 같은 방법으로 Array의 size를 확장시켜야 한다. 그럼에도 enqueue의 시간복잡도는 (amortized) O(1)를 유지할 수 있다.
List-Base	singly-lilnked list로 구현한다. enqueue는 단순히 singly-lilnked에서 append를 하는 것으로 구현되고, 이 때 시간복잡도는 O(1)이다. dequeue는 맨 앞의 원소를 삭제하고 first head를 변경하면 되기 때문에이 연산도 O(1)의 시간이 걸린다.

요약하자면, 두 가지 종류의 자료구조로 queue를 구현을 하더라도 enqueue와 dequeue는 모두 O(1)의 시간복잡도를 갖는다.

Array-Base의 경우 전반적으로 performance가 더 좋지만, worst case의 경우에는 훨씬 더 느릴 수 있다(resize).

List-Base의 경우에는 enqueue를 할 때마다 memory allocation을 해야 하기 때문에 전반적인 runtime이 느릴 수 있다.

 

반응형

Stack 스택 이란?

 stack은 후입선출 LIFO(Last In First Out)의 자료구조이다.

시간복잡도는 push O(1), pop O(1) 이다.

활용 예시는 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), 깊이우선탐색(DFS) 등이 있다.

LIFO (Last In First Out)

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

push & pop

stack에서 데이터를 추가하는 것을 push라고 하고 데이터를 추출하는 것은 pop이라고 한다.

push의 경우 stack의 맨 뒤에 데이터를 추가하면 완료되기 때문에 시간복잡도는 O(1)이다.

이와 동일하게 pop의 경우도 맨 뒤의 데이터를 삭제하면 완료되기 때문에 O(1)의 시간복잡도를 갖는다.

push와 pop은 모두 stack의 top에 원소를 추가하거나 삭제하는 형식으로 형성된다. 

 

Stack 두 개를 이용하여 Queue 구현

queue의 enqueue()를 구현할 때 첫 번째 stack을 사용하고,

dequeue()를 구현할 때 두 번째 stack을 사용하면 queue를 구현할 수 있다.

 

편의상 enqueue()에 사용할 stack을 instack이라고 부르고 dequeue()에 사용할 stack을 outstack이라고 칭하겠다.

두 개의 stack으로 queue를 구현하는 방법은 다음과 같다.

1. enqueue() :: instack에 push()를 하여 데이터를 저장한다.
2. dequeue() ::
   1. 만약 outstack이 비어 있다면 instack.pop() 을 하고 outstack.push()를하여 instack에서 outstack으로 모든 데이터를 옮겨 넣는다. 이 결과로 가장 먼저 왔던 데이터는 outstack의 top에 위치하게 된다.
   2. outstack.pop()을 하면 가장 먼저 왔던 데이터가 가장 먼저 추출된다.(FIFO) 

class Queue(object):
    def __init__(self):
        self.instack=[]
        self.outstack=[]

    def enqueue(self,element):
        self.instack.append(element)

    def dequeue(self):
        if not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()

 

Queue 두 개를 이용하여 Stack 구현

queue 두 개를 사용하여 stack의 push와 pop을 구현하는 것에 초점을 맞춰서 문제를 해결하면 된다.

편의상 push()에 사용할 queue는 q1이라고 부르고 pop()에 사용할 queue를 q2라고 칭하겠다.

두 개의 queue로 stack을 구현하는 방법은 다음과 같다. 

1. push() :: q1으로 enqueue()를 하여 데이터를 저장한다.
2. pop() ::
   1. q1에 저장된 데이터의 개수가 1 이하로 남을 때까지 dequeue()를 한 후, 추출된 데이터를 q2에 enqueue() 한다. 결과적으로 가장 최근에 들어온 데이터를 제외한 모든 데이터는 q2로 옮겨진다.
   2. q1에 남아 있는 하나의 데이터를 dequeue()해서 가장 최근에 저장된 데이터를 반환한다(LIFO)
   3. 다음에 진행될 pop()을 위와 같은 알고리즘으로 진행하기 위해 q1과 q2의 이름을 swap 한다.

import queue

class Stack(object):
    def __init__(self):
        self.q1 = queue.Queue()
        self.q2 = queue.Queue()

    def push(self, element):
        self.q1.put(element)

    def pop(self):
        while self.q1.qsize() > 1:
            self.q2.put(self.q1.get())

        temp = self.q1
        self.q1 = self.q2
        self.q2 = temp

        return self.q2.get()

시간복잡도

push()	q1.enqueue()를 한번만 하면 되기 때문에  O(1)의 시간복잡도를 갖는다.
pop()	q1에 저장되어 있는 n개의 원소 중에 n-1개를 q2로 옮겨야하므로 O(n)이 된다.

 

Queue와 priority queue 비교 설명

Queue 자료구조는 시간 순서상 먼저 집어 넣은 데이터가 먼저 나오는 선입선출 FIFO(First In First Out) 구조로 저장하는 형식이다. 이와 다르게 우선순위 큐(priority queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

Queue의 operation 시간복잡도는 enqueue O(1), dequeue O(1)이고,

Priority queue는 push O(logn), pop(logn)이다.

우선순위 큐는 구현 방법과 operation의 시간복잡도를 이해하는 것이 중요하다.

우선순위 큐를 구현하라는 것은 Heap을 구현하면 된다.

Heap 자료구조는 이진완전트리를 활용하는 것이고, 대표적인 operation의 시간복잡도는 push O(logn), pop O(logn)이다.

이 두가지 특징을 중심으로 공부하면 된다. 또한 tree가 그려져 있는 상태에서 최대힙, 최소힙의 삽입과 삭제시에 어떻게 node가 삭제되고 연결이 변경되는지의 과정을 그려서 설명할 수 있다면 더 좋다.

Heap

Heap은 그 자체로 우선순위큐 (priority queue)의 구현과 일치한다.

Heap은 완전이진트리 구조이다. Heap이 되기 위한 조건은 다음과 같다.

• 각 node에 저장된 값은 child node들에 저장된 값보다 작거나 같다.(min heap)
  root node에 저장된 값이 가장 작은 값이 된다.

반응형

 

Heap 구현

트리는 보통 Linked list로 구현한다. 하지만 Heap은 tree임에도 불구하고 array를 기반으로 구현해야 한다.

그 이유는 새로운 node를 힙의 '마지막 위치'에 추가해야 하는데, 이 때 array기반으로 구현해야 이 과정이 수월해지기 때문이다.

• 구현의 편의를 위해 array의 0번 째 index는 사용하지 않는다.
• 완전이진트리의 특성을 활용하여 array의 index만으로 부모 자식간의 관계를 정의한다.
  • n번 째 node의 left child node = 2n
  • n번 째 node의 right child node = 2n + 1
  • n번 째 node의 parent node = n/2

Heap push - O(logn)

heap tree의 높이는 logN이다.

push()를 했을 때, swap하는 과정이 최대 logN번 반복되기 때문에 시간복잡도는 O(logn)이다.

아래 그림은 2가 push() 되고 min heap 조건에 맞춰 재구성되는 과정이다.

min heap

Heap pop - O(logn)

pop()을 했을 때, swap하는 과정이 최대 logN번 반복되기 때문에 시간복잡도는 O(logn)이다

• 각 node에 저장된 값은 child node들에 저장된 값보다 작거나  같다.(mix heap)
  root node에 저장된 값이 가장 큰 값이 된다. 

아래 그림은 2가 pop()되고 마지막 노드가 root node에 올라오고 Min heap 조건에 맞게 재구성한다.

 

---

참고

https://lamarr.dev/images/algorithm/queue.jpg

https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcS3EliS7H7AdMinqJ17goQtOBS7C27nRjK9cA&usqp=CAU 

https://i.stack.imgur.com/LQJBQ.png

https://leetcode.com/media/original_images/225_stack_using_queues_pushB.png

https://i.imgur.com/1mghTRv.png

https://www.techiedelight.com/wp-content/uploads/2016/11/Pop-min-heap.png

https://www.nossi.dev/