자료구조 - 큐(Queue)

- 큐(Queue) 구조

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조
  • FIFO(First-In, First-Out) 또는 LILO(Last-In, Last-Out) 방식으로 스택과 꺼내는 순서가 반대

• Enqueue: 큐에 데이터를 넣는 기능
• Dequeue: 큐에서 데이터를 꺼내는 기능
• 시연 : https://visualgo.net/en/list

VisuAlgo - Linked List (Single, Doubly), Stack, Queue, Deque

 

- 파이썬으로 Queue 구현

• queue 라이브러리에서 다양한 큐 구조로 Queue(), LifoQueue(), PriorityQueue() 제공
  • Queue(): 가장 일반적인 큐 자료구조

  import queue
  
  data_queue = queue.Queue()
  data_queue.put(a)
  data_queue.put(b)
  
  data_queue.qsize()     // 2
  data_queue.get()    // a
  data_queue.get()    // b
  data_queue.qsize()    // 0    

  • LifoQueue(): 나중에 입력된 데이터가 먼저 출력되는 구조(스택 구조)

  import queue
  
  data_queue = queue.LifoQueue()
  data_queue.put(a)
  data_queue.put(b)
  
  data_queue.qsize()     // 2
  data_queue.get()    // b
  data_queue.get()    // a
  data_queue.qsize()    // 0    

  • PriorityQueue(): 데이터마다 우선순위를 넣어서 우선순위가 높은 순으로 데이터 출력

  import queue
  
  data_queue = queue.PriorityQueue()
  data_queue.put((10, 'ABC'))
  data_queue.put((5, 1))
  data_queue.put((15, 'ZYX'))
  
  data_queue.qsize()     // 3
  data_queue.get()    // (5, 1)
  data_queue.get()    // (10, 'ABC')        

• 리스트 변수로 큐를 다루는 enqueue, dequeue 기능 구현

queue_list = list()

def enqueue(data):
    queue_list.append(data)

def dequeue():
    data = queue_list[0]
    del queue_list[0]
    return data           

 

- 자바스크립트로 Queue 구현

• Queue

class Queue {
  constructor() {
    this.queue = [];
  }
  enqueue(data) {
    this.queue.push(data);
  }
  dequeue() {
    return this.queue.shift();
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.dequeue(); // 1