자료구조 및 실습 - [7] 큐 Queue, 데크 Deque (파이썬으로 큐,데크 구현) (1)

큐 ADT

큐 ADT는 임의의 개체들을 저장하는 하나의 추상자료형이다. 삽입과 삭제는 선입선출 (First In First Out, FIFO)순서를 따른다. 삽입은 큐의 뒤(rear)에서, 삭제는 큐의 앞(front)이라 불리는 위치에서 수행된다.

---

큐 ADT 메서드

큐의 메서드는 다음과 같다.

#주요 큐 메서드
enqueue(element) : 큐의 뒤에 원소를 삽입
element dequeue() : 큐의 앞에서 원소를 삭제하여 반환

#보조 큐 메서드
element front() : 큐의 앞에 있는 원소를 (삭제하지 않고) 반환
integer size() : 큐에 저장된 원소의 수를 반환
boolean isEmpty() : 큐가 비어있는지 여부를 반환
iterator elements() : 큐 원소 전체를 반환

#예외
EmptyQueueException() : 비어 있는 큐에 대해 삭제 또는 front를 수행 시도할 경우 발령
fullQueueException(): 만원 큐에 대해 삽입을 수행 시도할 경우 발령

초기화

큐 초기화 의사코드

삽입

큐 삽입 의사코드

삭제

큐 삭제 의사코드

 

큐 ADT 구현

큐도 배열과 연결리스트를 이용해 구현할 수 있다. 이번에도 연결리스트를 통해 구현해보겠다.

물론 파이썬에서 리스트를 활용하면 손쉽게 흉내낼 수 있다. 

 

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

class queue:
  def __init__(self):
    self.front = None
    self.rear = None
    self.qsize = 0

  def isEmpty(self):
    return self.front == None
  
  def printfront(self):
    if self.isEmpty():
      print("EmptyQueueException")
    else:
      print(self.front.data)
    
  def quesize(self):
    print(self.qsize)
  
  def queprint(self):
    if self.isEmpty():
      print("EmptyQueueException")
    else:
      target = self.front
      for i in range(self.qsize):
        if i == self.qsize-1:
          print(target.data)
        else:
          print(target.data, end =" ")
          target = target.next
  
  def enqueue(self, data):
    newnode = Node(data)
    self.qsize+=1
    if self.isEmpty():
      self.front = newnode
      self.rear = newnode
    else:
      self.rear.next = newnode
      self.rear = newnode
    print("Success Enqueue : ",newnode.data)

  def dequeue(self):
    if self.isEmpty():
      print("EmptyQueueException")
    else:
      self.qsize-=1
      elem = self.front.data
      p = self.front
      self.front = self.front.next
      if self.front == None:
        self.rear = None
      del(p)
      print("Success Dequeue : ",elem)

>>> a = queue()
>>> print(a.isEmpty())
True

>>> a.enqueue('1')
Sucess Enqueue :  1

>>> a.enqueue('2')
Sucess Enqueue :  2

>>> print(a.isEmpty())
False

>>> a.quesize()
2

>>> a.printfront()
1

>>> a.queprint()
1 2

>>> a.quesize()
2

>>> a.dequeue()
Sucess Dequeue :  1

>>> a.queprint()
2

---

데크 ADT 

데크도 동일하게 임의의 개체들을 저장하는 하나의 추상자료형이다. 데크는 스택과 큐가 합쳐진 방식으로 작동한다. 

삽입과 삭제 앞(front)과 뒤(rear)에서 모두 이루어 질 수 있다.

데크 ADT 메서드

데크의 메서드는 다음과 같다.

#주요 데크 메서드
push(e): front 위치에 원소를 삽입
element pop(): front 위치의 원소를 삭제하여 반환
inject(e): rear 위치에 원소를 삽입
element eject(): rear 위치의 원소를 삭제하여 반환

#보조 데크 메서드
element front(): front 위치의 원소를 반환
element rear(): rear 위치의 원소를 반환
integer size(): 데크에 저장된 원소의 수를 반환
boolean isEmpty(): 데크가 비어 있는지 여부를 반환

#예외
EmptyQueueException() : 비어 있는 큐에 대해 삭제 또는 front를 수행 시도할 경우 발령
fullQueueException(): 만원 큐에 대해 삽입을 수행 시도할 경우 발령

초기화

데크 초기화 의사코드

삽입

데크 삽입(뒤) 의사코드

데크 삽입(앞) 의사코드

삭제

데크 삭제(앞) 의사코드

 

데크 삭제(뒤) 의사코드

---

데크 ADT 구현

파이썬에서 데크는

from collections import deque

를 통해 손쉽게 이용이 가능하다. 하지만 주요 메서드와 보조메서드를 이중연결리스트를 통해 구현해보겠다.

 

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

class deque:
  def __init__(self):
    self.front = None
    self.rear = None
    self.dqsize = 0
  
  def isEmpty(self):
    return self.front == None
  
  def printsize(self):
    print(self.dqsize)
  
  def printdeque(self):
    if self.isEmpty():
      print("EmptyQueueException")
    else:
      target = self.front
      for i in range(self.dqsize):
        if i == self.dqsize-1:
          print(target.data)
        else:
          print(target.data, end =" ")
          target = target.next
  
  def add_rear(self, data): #inject
    newnode = Node(data)
    if self.isEmpty():
      self.front = newnode
      self.rear = newnode

    else:
      newnode.prev = self.rear
      self.rear.next =newnode
      self.rear = newnode
    self.dqsize +=1
    print("Successly add rear :",data)

  def add_front(self, data): #push
    newnode = Node(data)
    if self.isEmpty():
      self.front = newnode
      self.rear = newnode

    else:
      newnode.next = self.front
      self.front.prev =newnode
      self.front = newnode
    self.dqsize +=1
    print("Successly add front :",data)

  def delete_front(self):#pop
    if self.isEmpty():
      print("EmptyQueueException")
    else:
      e = self.front.data
      p = self.front
      self.front = self.front.next
      if self.front == None:
        self.rear = None
      else:
        self.front.prev = None
      del(p)
      self.dqsize -=1
      print("Successly delete front :",e)

  def delete_rear(self): #eject
    if self.isEmpty():
      print("EmptyQueueException")
    else:
      e = self.front.data
      p = self.rear
      self.rear = self.rear.prev
      if self.rear == None:
        self.front = None
      else:
        self.rear.next = None
      del(p)
      self.dqsize -=1
      print("Successly delete rear :",e)

>>> a = deque()
>>> print(a.isEmpty())
True

>>> a.add_rear('a')
Successly add rear : a

>>> a.add_rear('b')
Successly add rear : b

>>> a.printdeque()
a b

>>> a.add_front('B')
Successly add front : B

>>> a.add_front('A')
Successly add front : A

>>> a.printdeque()
A B a b

>>> a.printsize()
4

>>> a.delete_front()
Successly delete front : A

>>> a.delete_rear()
Successly delete rear : B

>>> a.printdeque()
B a

작업이 잘 진행되는지 확인하기 위해 약간의 출력문을 더했다. 메서드가 잘 작동하는 것을 확인할 수 있다.