[자료구조] : 큐(선형), 힙

- 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조(FIFO, First In First Out)

- Enqueue : 큐에 데이터를 넣는 기능

- Dequeue : 큐에서 데이터를 꺼내는 기능

 

# 파이썬에서의 큐

import queue

 

# 1. 일반적인 큐(FIFO)

data_queue = queue.Queue()

data_queue.put('FIFO Q')

data_queue.put(1)

print(data_queue.qsize())

print(data_queue.get())

print(data_queue.qsize())

 

# 2. LIFO(Last In First Out)

data_queue = queue.LifoQueue()

data_queue.put('LIFO Q')

data_queue.put(2)

print(data_queue.qsize())

print(data_queue.get())

print(data_queue.qsize())

 

# 3. Priority Queue : 우선순위 번호가 낮을수록 우선순위가 높다

data_queue = queue.PriorityQueue()

data_queue.put((10, "Korea"))

data_queue.put((5, "Priority Queue"))

data_queue.put((15, "China"))

print(data_queue.get()[1])

print(data_queue.get()[1])

 

# 우선순위큐_구현(리스트) -> 시간복잡도 : O(n^2) => 비효율적

import sys
# 우선순위 큐 구현하기
# Overflow, Underflow에 대한 예외는 고려되지 않았다.
# myPQ.push(x)
# myPQ.pop()
# myPQ.top()
 
def push(x):
  global cursor
  data[cursor] = x
  cursor += 1 
 
def pop():
  global cursor, data
  # 1.우선순위가 가장 높은 원소를 찾는다.
  myMax    = int(1e9)*(-1)
  myMaxIdx = -1 
  for i in range(cursor):
    if data[i] > myMax:
      myMax    = data[i]
      myMaxIdx = i 
  # 2.그 원소를 제거하고, 뒤의 원소를 앞으로 당긴다.
  for i in range(myMaxIdx, cursor):
    data[i] = data[i+1]
  cursor-=1
  
def top():
  global cursor, data
  # 1.우선순위가 가장 높은 원소를 찾는다.
  myMax    = int(1e9)*(-1) 
  for i in range(cursor):
    if data[i] > myMax:
      myMax = data[i]
  return myMax
 
if __name__ == "__main__":
  input = sys.stdin.readline
  data   = [0]*100
  cursor = 0 
  
  push(1)
  push(8)
  push(7)
  push(5)
  
  print(top()) 
  pop()
  print(top()) 

 

# 우선순위큐_트리적용(힙) 시간복잡도 : O(logn)

# 힙 개념

부모의 값이 항상 자식보다 작은 완전 이진 트리 : 부모일수록 우선순위가 높다.

# 완전 이진트리 패턴

# 노드 개수가 n개일 때 높이는 logn이다

노드의 개수	높이	규칙
1	1	2^1-1
2	2
3	2	2^2-1
4	3
5	3
6	3
7	3	2^3-1
8	4
9	4
. . .
15	4	2^4-1

https://www.cs.usfca.edu/~galles/visualization/Heap.html

Heap Visualization

class PriorityQueue:
  
  data_list = [0 for _ in range(100)]
  len = 1 #원소의 맨끝을 가리킨다.
 
  def push(self, data):    
    self.data_list[self.len] = data
    self.len += 1
    idx = self.len - 1
    while idx > 1: # root 보다 클 때
      # idx : 마지막 들어간 요소의 idx
      # idx//2 : 부모 요소의 idx
      if self.data_list[idx] < self.data_list[idx//2]:
        self.data_list[idx], self.data_list[idx//2] = self.data_list[idx//2], self.data_list[idx]
      else:
        break
      idx = idx//2 #내가 부모자리로 올라감
  def pop(self):
    self.data_list[1] = self.data_list[self.len-1]
    self.data_list[self.len-1] = 0
    self.len -= 1 
    idx = 1
    while True:
      # 1. 자식들 중에서 우선순위가 높은 친구를 알아내야함.
      # 2. 나와 그 우선순위가 높은 친구를 비교해서 자리를 바꾸어야함.
 
      pIdx = -1 # 우선 순위가 높은 친구의 노드 번호
      # (A) 자식이 모두 없는 경우
      if idx*2 >= self.len:
        break
      # (B) 왼쪽 자식만 존재하는 경우 1 ~ len 범위에 속해야된다.   
      elif idx*2 >= 1 and idx*2 < self.len and idx*2+1 >= self.len:
        pIdx = idx*2
      # (C) 왼쪽, 오른쪽 자식이 모두 존재하는 경우
      else:
        if self.data_list[idx*2] < self.data_list[idx*2+1]:
          pIdx = idx*2
        else:
          pIdx = idx*2+1
 
      if self.data_list[idx] > self.data_list[pIdx]:
        self.data_list[idx], self.data_list[pIdx] = self.data_list[pIdx], self.data_list[idx]
        idx = pIdx
      else:
        break
 
 
  def top(self):
    return self.data_list[1]
 
 
if __name__ == "__main__":
  pq = PriorityQueue()
  pq.push(3)
  pq.push(1)
  pq.push(2)
  
 
  print(pq.top())
  pq.pop()  
  print(pq.top())
  pq.pop()  
  print(pq.top())

 

 

# 예제) 리스트 변수로 큐를 다루는 enqueue, dequeue 기능 구현

queue_list = list()

def enqueue(data):

    queue_list.append(data)

 

def dequeue():

    data = queue_list[0]

    del queue_list[0]

    return data

 

for index in range(10):

    enqueue(index)

 

print(len(queue_list))

print(dequeue())

print(dequeue())

 

#선형큐 코드

class Queue:
  
  data = [0 for _ in range(100)]
  f, r = 0, 0
  capacity = 0
  
  def create(self, y):
    self.capacity = y
    self.f = 0
    self.r = 0
  
  def push(self, y):
    if self.r - self.f >= self.capacity:
      print('Queue Overflow')
    else:
      self.data[self.r] = y
      self.r += 1
  def pop(self):
    if self.r - self.f <= 0:
      print('Queue Underflow')
    else:
      self.data[self.f] = 0
      self.f += 1
  def front(self):
    if self.r - self.f <= 0:
      return -1
    else:
      return self.data[self.f]
  def size(self):
    return self.r - self.f
  
  
 
 
 
if __name__ == "__main__":
  qq = Queue()
  qq.create(4)
  qq.push(1)
  qq.push(2)
  qq.push(3)
  qq.push(4)
  qq.push(5)
  print(qq.size())
  print(qq.front())
  qq.pop()
  print(qq.size())
  print(qq.front())

 

#원형큐 코드

## template
class Queue:
  CONST_MAX = 10
  data = [0 for _ in range(CONST_MAX)]
  f, r = 0, 0
  capacity = 0
  numElement = 0
  
  def create(self, y):
    self.capacity = y
    self.f = 0
    self.r = 0
    self.numElement = 0
  
  def push(self, y):
    if self.numElement >= self.capacity:
      print('Queue Overflow')
    else:
      self.data[self.r] = y
      '''
      self.r += 1
      if self.r >= self.CONST_MAX:
        self.r = 0
      '''
      self.r = (self.r+1) % self.CONST_MAX # 위의 주석과 같다.
      self.numElement+=1
  def pop(self):
    if self.numElement <= 0:
      print('Queue Underflow')
    else:
      self.data[self.f] = 0
      '''
      self.f += 1
      if self.f >= self.CONST_MAX:
        self.f = 0
      '''
      self.f = (self.f + 1) % self.CONST_MAX
      self.numElement -= 1
  def front(self):
    if self.numElement <= 0:
      return -1
    else:
      return self.data[self.f]
  def size(self):
    return self.numElement
  
  
if __name__ == "__main__":
  qq = Queue()
  qq.create(4)
  for i in range(100):
    qq.push(i)
    qq.push(i+1)
    qq.push(i+2)
    qq.push(i+3)
    
    qq.pop()
    qq.pop()
    qq.pop()
    qq.pop()
    
  qq.push(1)
  qq.push(2)
  print(qq.front())
  qq.pop()
  print(qq.front())