큐(Queue) level 1

1) 큐(Queue)

  - 한쪽 끝에서 삽입이 이루어지고(인큐, Enqueue) 다른 한쪽에선 삭제 연산(디큐, Dequeue)만 이뤄지는 선형의 자료 구조

  - 선입선출(FIFO, First In, First Out) 특징을 가지는 선형 자료구조 ex) 대기열

 

 

2) 큐(Queue) 자료구조 구현

  ① 배열(array, list)을 이용하여 구현 → Python List 와 method들을 이용

class ArrayQueue :
	def size(self) :				# 현재 큐에 들어 있는 데이터 원소의 수
    	return len(self.data)
    
    	def isEmpty(self) :				# 현재 큐가 비어 있는지를 판단
    		return self.size() == 0
   
    	def enqueue(self, item) :				# 데이터 원소 itme을 큐에 추가
    		self.data.append(item)
    
    	def dequeue(self) :					# 큐의 맨 끝에 저장된 데이터 원소를 제거 및 반환
    		return self,data.pop(0)
    
    	def peek(self) :				# 큐의  맨 앞에 저장된 데이터 원소를 반환 (제거 X)
    		return self.data[0]

  ※ 배열로 구현한 큐의 연산 복잡도

    - dequeue 시 삭제된 element를 제외한 나머지 element가 전체적으로 이동함

 

  ② 연결 리스트(Linked List)를 이용하여 구현 → 양방향 연결 리스트 이용

class LinkedListQueue:

    def __init__(self):
        self.data = DoublyLinkedList()

    def size(self):
        return self.data.getLength()


    def isEmpty(self):
        return self.size()==0


    def enqueue(self, item):
        node = Node(item)
        self.data.insertAt(self.size()+1, node)


    def dequeue(self):
        return self.data.popAt(1)


    def peek(self):
        return self.data.getAt(1).data

 

 

3) 큐(Queue) 라이브러리

  - pythonds 설치 필요

pip install pythonds

>>> from pythonds.basic.queue import Queue
>>> Q = Queue()
>>> dir(Q)
['__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__'
, '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', 'dequeue', 'enqueue', 'isEmpty', 'items', 'size']