[자료구조] 큐(Queue) 개념 및 코드 구현

 

 

이번 포스팅에선 큐(Queue)의 개념과 코드 구현을 할 것이다.

만약 스택(Stack) 개념을 알지 못한다면 이전 포스팅을 보고 오자.

 

 

[이전 포스팅 URL: https://mengu.tistory.com/29]

[자료구조] 스택(Stack) 개념 및 코드 구현

 

 

들어가보자!

 

 

 

 

큐(Queue) 개념

---

큐(Queue)는 FIFO(First In First Out) 방식의 자료구조이다.

먼저 들어온 요소가 가장 먼저 나간다.

 

큐(Queue)의 제일 앞 요소를 front, 제일 뒷 요소를 rear라고 한다.

 

 

 

 

 

 

활용

스케쥴링을 할 때 쓰인다. 먼저 등록된 작업에 CPU를 배당하고, 해당 작업이 끝나면 다시 반복하여 CPU를 배당한다. 보통 작업들이 병렬적으로 처리되어도 괜찮을 때, 작업끼리 의존성이 없을 때 큐를 통해 스케쥴링 작업을 한다. 

* 스케쥴링이란 운영체제 프로세스를 관리하는 기법을 말함

 

 

기능

1. enqueue()

: 큐에 원소를 추가한다.

2. dequeue()

: 큐의 가장 앞 원소를 추출한다.

3. peek()

: 큐의 가장 앞 원소를 리턴한다.

4. isEmpty()

: 큐가 비어있는지 확인한다.

 

 

 

 

큐(Queue) 코드 구현

---

 

배열 구현

 

class Queue:

  def __init__(self):
    self.top = []
  
  def enqueue(self, a):
    self.top.append(a)
  
  def dequeue(self):
    dequeue_object = None
    if self.isEmpty:
      print('Queue is empty')
    else:
      dequeue_object = self.top[0]
      self.top = self.top[1:]
    return dequeue_object

  def peek(self):
    peek_object = None
    if self.isEmpty:
      print('Queue is empty')
    else:
      peek_object = self.top[0]
    return peek_object

  def isEmpty(self):
    is_Empty = False
    if len(self.top) > 0:
      is_Empty = False
    else:
      is_Empty = True
    return is_Empty

 

 

 

 

연결 리스트 구현

 

class Node:
  def __init__(self, data):
    self.data = data 
    self.next = None

class LinkedlistQueue:
  def __init__(self):
    self.front = None
    self.rear = None

  def enqueue(self, data):
    new_node = Node(data)
    if self.isEmpty():
      self.front = new_node
      self.rear = new_node
    else:
      self.rear.next = new_node
      self.rear = new_node
  
  def dequeue(self):
    dequeue_object = None
    if self.isEmpty():
      return print('Queue is empty')
    else:
      dequeue_object = self.front
      self.front = self.front.next
    
    if self.front is None:
      self.rear = None
    return dequeue_object

  def peek(self):
    peek_object = None
    if self.isEmpty():
      return print('Queue is empty')
    else:
      peek_object = self.front.data
    return peek_object

  def isEmpty(self):
    is_Empty = False
    if self.front is None:
      is_Empty = True
    else:
      is_Empty = False
    return is_Empty