[자료구조] 큐와 덱

1. 큐(Queue)

 (1) 큐의 개념과 동작 원리

  - 선입선출(FIFO)의 자료구조

  - 삽입은 큐의 후단에서 삭제는 전단에서 이루어짐

  - 예시 : 서비스 센터, 은행, 공항등에서의 대기열, 프린터/컴퓨터의 작업 리스트, 실시간 비디오 스트리밍에서 버퍼링,

              통신에서 데이터 패킷들의 모델링 등에 이용

  [ 큐ADT ]

   - Queue() 비어있는 새로운 큐를 만듬

   - isEmpty() 비어있으면 True, 아니면 False 반환

   - enqueue(x) x를 큐의 맨 뒤에 추가함

   - dequeue() 큐의 맨 앞에 있는 항목을 꺼내 반환함

   - peek() 큐의 맨 앞에 있는 항목을 삭제하지 않고 반환함

   - size() 큐의 모든 항목들의 개수를 반환함

   - clear() 큐를 공백상태로 만듬

 (2) 원형 큐

  - 선형 큐의 비효율성 개선을 위해 개발됨

  * 선형 큐의 비효율성 : 산입 연산 복잡도 = O(1)이지만 삭제 연산 복잡도 O(n)임

  - 원형 큐의 효율성 : 배열을 원형으로 사용, 전단과 후단을 위한 2개의 변수로 이음, 회전(시계방향) 방법

  - 공백 상태 front == rear

  - 포화 상태 front % M == (rear +1) % M

   > 공백 상태와 포화 상태를 구별하기 위해 입력이 들어올 시 한칸을 비우고 다음 칸에 저장

   > 구현 시 리스트의 크기를 미리 정해야 하며, 그래야 포화 상태가 존재함

// 원형 큐로 구현 MAX_SIZE = 10 class C_Queue :     def __init__(self) :         self.front = 0         self.rear = 0         self.item = [None] * MAX_SIZE     def isEmpty(self) : return self.front == self.rear     def isFull(self) : return self.rear == MAX_SIZE     def clear(self) : self.front = self.rear     def enqueue (self, item) :         if not self.isFull() :             self.rear = (self.rear+1)%MAX_SIZE             self.item[self.rear] = item     def dequeue (self) :         if not self.isEmpty() :             self.front = (self.front+1)%MAX_SIZE             return self.item[self.front]     def peek(self) :         if not self.isEmpty() :             return self.item[(self.front+1)%MAX_SIZE]     def size(self) :         return (self.rear-self.front+MAX_SIZE)%MAX_SIZE     def display(self) :         out = []         if self.front < self.rear :             out = self.item[self.front+1:self.rear+1]         else :             out = self.item[self.front+1:MAX_SIZE]+self.item[0:self.rear+1]         print("[f=%s, r=%d] ==> " %(self.front, self.rear), out) q=C_Queue() for i in range(8) : q.enqueue(i) q.display() for i in range(5) : q.dequeue() q.display() for i in range(8,14) : q.enqueue(i) q.display()

 (3) 큐의 응용

   - 미로 탈출 방법으로 너비 우선 탐색 사용

    > 큐에 가능한 다음 위치를 순서대로 저장

    > 막다른 길을 만나면 가장 먼저 저장된 위치를 다시 시도

    > 입구에서 가장 가까운 위치 먼저 탐색

// 너비 우선 탐색의 미로 탈출 MAX_SIZE = 10 class C_Queue :     def __init__(self) :         self.front = 0         self.rear = 0         self.item = [None] * MAX_SIZE     def isEmpty(self) : return self.front == self.rear     def isFull(self) : return self.rear == MAX_SIZE     def clear(self) : self.front = self.rear     def enqueue (self, item) :         if not self.isFull() :             self.rear = (self.rear+1)%MAX_SIZE             self.item[self.rear] = item     def dequeue (self) :         if not self.isEmpty() :             self.front = (self.front+1)%MAX_SIZE             return self.item[self.front]     def peek(self) :         if not self.isEmpty() :             return self.item[(self.front+1)%MAX_SIZE]     def size(self) :         return (self.rear-self.front+MAX_SIZE)%MAX_SIZE     def display(self) :         out = []         if self.front < self.rear :             out = self.item[self.front+1:self.rear+1]         else :             out = self.item[self.front+1:MAX_SIZE]+self.item[0:self.rear+1]         print("[f=%s, r=%d] ==> " %(self.front, self.rear), out) q=C_Queue() for i in range(8) : q.enqueue(i) q.display() for i in range(5) : q.dequeue() q.display() for i in range(8,14) : q.enqueue(i) q.display() def vaild(x, y) :     if x<0 or y<0 or x>=MAX_SIZE or y>=MAX_SIZE :         return False     else :         return map[y][x] == '0' or map[y][x] == 'x'      def BFS() :     que = C_Queue()     que.enqueue((0,1))     print('BFS : ')     while not que.isEmpty() :         here = que.dequeue()         print(here, end= '->')         x, y = here         if(map[y][x] == 'x') : return True         else :             map[y][x] = '.'             if vaild(x, y-1) : que.enqueue((x,y-1))             if vaild(x, y+1) : que.enqueue((x,y+1))             if vaild(x-1, y) : que.enqueue((x-1,y))             if vaild(x+1, y) : que.enqueue((x+1,y))     return False map = [['1','1','1','1','1','1'],        ['e','0','0','0','0','1'],        ['1','0','1','0','1','1'],        ['1','1','1','0','0','x'],        ['1','1','1','0','1','1'],        ['1','1','1','1','1','1']] result = BFS() print(result)

2. 덱(Deque)

 (1) 덱의 개념과 동작 원리

  - deque = double-ended queue 

  - 스택이나 큐보다 입출력이 자유로운 자료 구조

  - 전단이나 후단에서 모두 삽입 삭제 가능

  - 그러나 중간에 넣거나 빼지는 못함(List와 차이점)

  [ 덱 ADT ]

   - Deque() 비어있는 새로운 덱를 만듬

   - isEmpty() 비어있으면 True, 아니면 False 반환

   - addFront(x) x를 덱의 맨 앞에 추가함

   - deleteFront() 덱의 맨 앞에 있는 항목을 꺼내 반환함

   - getFront() 덱의 맨 앞에 있는 항목을 삭제하지 않고 반환함

  - addRear(x) x를 덱의 맨 뒤에 추가함

  -  deleteRear() 덱의 맨 뒤에 있는 항목을 꺼내 반환함

   - getRear() 덱의 맨 뒤에 있는 항목을 삭제하지 않고 반환함

   - isFull() 가득 차 있으면 True, 아니면 False 반환

   - size() 덱의 모든 항목들의 개수를 반환함

   - clear() 덱를 공백상태로 만듬

 (2) 덱의 구현

  - 원형 덱을 사용함

  - 큐와 데이터는 동일하고 연산은 유사

  - 원형 큐를 기반으로 원형 덱의 연산 : Front의 경우 시계방향, Rear는 반시계 방향

class Deque :     def __init__(self) :         self.front = 0         self.rear = 0         self.item = [None] * MAX_SIZE     def isEmpty(self) : return self.front == self.rear     def isFull(self) : return self.rear == MAX_SIZE     def clear(self) : self.front = self.rear     def addFront (self, item) :         if not self.isFull() :             self.rear = (self.rear+1)%MAX_SIZE             self.item[self.rear] = item     def deleteFront (self) :         if not self.isEmpty() :             self.front = (self.front+1)%MAX_SIZE             return self.item[self.front]     def getFront(self) :         if not self.isEmpty() :             return self.item[(self.front+1)%MAX_SIZE]     def addRear (self, item) :         if not self.isFull() :             self.item[self.front] = item             self.front = self.front -1             if self.front <0 : self.front = MAX_SIZE-1     def deleteRear (self) :         if not self.isEmpty() :             item = self.item[self.rear]             self.rear = self.rear -1             if self.rear < 0 : self.rear = MAX_SIZE -1             return item     def getRear(self) :         return self.item[self.rear]          def size(self) :         return (self.rear-self.front+MAX_SIZE)%MAX_SIZE     def display(self) :         out = []         if self.front < self.rear :             out = self.item[self.front+1:self.rear+1]         else :             out = self.item[self.front+1:MAX_SIZE]+self.item[0:self.rear+1]         print("[f=%s, r=%d] ==> " %(self.front, self.rear), out) d=Deque() for i in range(9) :     if i%2 ==0: d.addRear(i)     else : d.addFront(i) d.display() for i in range(2) : d.deleteFront() for i in range(3) : d.deleteRear() d.display() for i in range(9,14) : d.addFront(i) d.display()

3. 우선순위 큐

 (1) 우선순위 큐의 개념과 동작 원리

  - 우선순위의 개념을 큐에 도입된 자료 구조

  - 모든 데이터가 우선순위를 가짐

  - 입력 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력 (정렬이 추가됨)

  - 가장 일반적인 큐

  - 응용분야 : 도로에서 자동차 우선순위, 네트워크 트레픽 제어, OS의 작업 스케쥴링

  [ 우선순위 큐 ADT ]

   - Pri-que() 비어있는 새로운 덱를 만듬

   - isEmpty() 비어있으면 True, 아니면 False 반환

   - enqueue(x) 우선 순위를 가진 항목 x를 추가함

   - dequeue() 가장 우선순위가 높은 항목을 꺼내서 반환함

   - peek() 가장 우선순위가 높은 요소를 삭제하지 않고 반환함

   - size() 큐의 모든 항목들의 개수를 반환함

   - clear() 큐를 공백상태로 만듬

   - isFull() 가득 차 있으면 True, 아니면 False 반환

 (2) 우선순위 큐의 구현

  > 예로 입력된 x값의 크기별로 우선순위가 높다고 가정하고 ADT 구현

MAX_SIZE = 100 class Prique :     def __init__(self) :         self.item = []     def isEmpty(self) : return len(self.item) == 0     def isFull(self) : return len(self.item) == MAX_SIZE     def clear(self) : self.item = []     def enqueue (self, i) :         if not self.isFull() :             self.item.append(i)     def findMaxIndex(self) :         if self.isEmpty() : return None         else :             h = 0             for k in range(1, self.size()) :                 if self.item[k] > self.item[h] : h = k             return h     def dequeue (self) :         h = self.findMaxIndex()         if h is not None :             return self.item.pop(h)     def peek(self) :         h = self.findMaxIndex()         if h is not None :             return self.item[h]     def size(self) :         return len(self.item) q=Prique() q.enqueue(34) q.enqueue(24) q.enqueue(44) q.enqueue(54) q.enqueue(14) q.enqueue(4) print(q.item) while not q.isEmpty() :     print(q.dequeue())

  - 정렬되지 않은 리스트 사용 시 enqueue : O(1), findMaxIndex : O(n), dequeue : O(n)

  - 정렬된 리스트 사용 시 enqueue : O(n), dequeue/Peek : O(1)

  - 힙트리 사용 시 enqueue, dequeue : O(longn), peek : O(1)

  - 우선순위 큐의 사례 : 허프만 코딩 트리(빈도가 작은 두 노드를 선택)

                                   Kruskal의 MST 알고리즘(MST에 포함되지 않은 간선 중 최소 가중치 간선을 선택)

                                   Dijkstra의 최단거리 알고리즘(최단거리가 찾아지지 않은 정점들 중 가장 거리가 가까운 정점 선택)

                                   인공지능 A*의 알고리즘(상태 공간 트리에서 가장 가능성이 높은 경로를 먼저 선택)

 (3) 우선순위 큐의 응용

  - 전략적 미로 탐색 : 출구의 위치를 알고 있다고 가정, 가능한 가까운 방향을 먼저 선택

  - 최대 우선순위 항목 선택, 튜플 이용

import math MAX_SIZE = 100 (ox, oy) = (5,4) class Prique :     def __init__(self) :         self.item = []     def isEmpty(self) : return len(self.item) == 0     def isFull(self) : return len(self.item) == MAX_SIZE     def clear(self) : self.item = []     def enqueue (self, i) :         if not self.isFull() :             self.item.append(i)     def findMaxIndex(self) :         if self.isEmpty() : return None         else :             h = 0             for k in range(1, self.size()) :                 if self.item[k][2] > self.item[h][2] : h = k             return h     def dequeue (self) :         h = self.findMaxIndex()         if h is not None :             return self.item.pop(h)     def peek(self) :         h = self.findMaxIndex()         if h is not None :             return self.item[h]     def size(self) :         return len(self.item) def dist(x,y) :     (dx, dy) = (ox - x, oy - y)     return math.sqrt(dx*dx+dy*dy) def vaild(x, y) :     if x<0 or y<0 or x>=MAX_SIZE or y>=MAX_SIZE :         return False     else :         return map[y][x] == '0' or map[y][x] == 'x'      def PS() :     q = Prique()     q.enqueue((0,1, -dist(0,1)))     print('PS : ')     while not q.isEmpty() :         here = q.dequeue()         print(here[0:2], end= '->')         x, y,_ = here         if(map[y][x] == 'x') : return True         else :             map[y][x] = '.'             if vaild(x, y-1) : q.enqueue((x,y-1,-dist(x,y-1)))             if vaild(x, y+1) : q.enqueue((x,y+1,-dist(x,y+1)))             if vaild(x-1, y) : q.enqueue((x-1,y,-dist(x-1,y)))             if vaild(x+1, y) : q.enqueue((x+1,y,-dist(x+1,y)))         print('PQ : ',q.item)     return False map = [['1','1','1','1','1','1'],        ['e','0','0','0','0','1'],        ['1','0','1','0','1','1'],        ['1','1','1','0','0','x'],        ['1','1','1','0','1','1'],        ['1','1','1','1','1','1']] result = PS() print(result)