###### tags: `LeetCode筆記`
# queue

[toc]

## queue 的ADT (Abstract Data Type )

- create :建立一個空串列
- enqueue() :將資料從queue的後端加入
- dequeue():將資料從queue的前端刪除
- front():查看queue 的前端的data，回傳他的值
- rear()：查看queue後端的data ，回傳其值

---
四方法實作
=====

- list
- collections.deque
- queue.Queue
- linked list

用 list 實作 dequeue & enqueue
---------------------------

很耗時間：因為你會移動整個list的值，來保持index是正確的，所以時間複雜度需要O(n)

一定要用pop(0)指定移除第一個項目，原本pop()是移除最後一個項目

# Python program to
# demonstrate queue implementation
# using list

# Initializing a queue
queue = []

# Adding elements to the queue
queue.append('a')
queue.append('b')
queue.append('c')

print("Initial queue")
print(queue)

# Removing elements from the queue
print("\nElements dequeued from queue")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

print("\nQueue after removing elements")
print(queue)

# Uncommenting print(queue.pop(0))
# will raise and IndexError
# as the queue is now empty

用dequeue collections module 實作 （已經是一個class ）
--------------------------------------------

deque is preferred over list in the cases where we need quicker append and pop operations from both the ends of container, as deque provides an O(1) time complexity for append and pop operations as compared to list which provides O(n) time complexity.

# Python program to
# demonstrate queue implementation
# using collections.dequeue


from collections import deque

# Initializing a queue
q = deque()

# Adding elements to a queue
q.append('a')
q.append('b')
q.append('c')

print("Initial queue")
print(q)

# Removing elements from a queue
print("\nElements dequeued from the queue")
print(q.popleft())
print(q.popleft())
print(q.popleft())

print("\nQueue after removing elements")
print(q)

# Uncommenting q.popleft()
# will raise an IndexError
# as queue is now empty

用**queue.Queue 實作 (python 內建module )**
--------------------------------------

Queue is built-in module of Python which is used to implement a queue.

queue.Queue(maxsize) initializes a variable to a maximum size of maxsize. A maxsize of zero ‘0’ means a infinite queue. This Queue follows FIFO rule.

There are various functions available in this module:

- **maxsize** – Number of items allowed in the queue.
- **empty()** – Return True if the queue is empty, False otherwise.
- **full()** – Return True if there are maxsize items in the queue. If the queue was initialized with maxsize=0 (the default), then full() never returns True.
- **get()** – Remove and return an item from the queue. If queue is empty, wait until an item is available.
- **get_nowait()** – Return an item if one is immediately available, else raise QueueEmpty.
- **put(item)** – Put an item into the queue. If the queue is full, wait until a free slot is available before adding the item.
- **put_nowait(item)** – Put an item into the queue without blocking. If no free slot is immediately available, raise QueueFull.
- **qsize()** – Return the number of items in the queue

用linked list 實作queue
--------------------

- dequeue 就像是刪除linked list 首節點，
- enqueue 就像是新增linked list 的末節點

#以鏈結串列實作佇列
class Node: #鏈結串列的節點
   def __init__(self, item):
      self.item = item
      self.next = None

#建立Queue類別
class Queue:
   def __init__(self):
      '''設首、尾節點為None'''
      self.qhead = None 
      self.qtail = None

   def isEmpty(self): #是否為空佇列
      return self.qhead is None

   def enqueue(self, item):
      #不是空佇列才新增節點
      newNode = Node(item)
      if self.isEmpty():
         self.qhead = newNode
      else:
         #佇列尾端指標指向新節點
         self.qtail.next = newNode
      #從佇列後端新增節點
      self.qtail = newNode

   def dequeue(self):
      if self.qhead is not None:
         #目前指標指向首節點
				#current LIKE A container 
         current = self.qhead
         #首節點指標指向下一個節點
         self.qhead = current.next
      print('刪除項目', current.item)

   def fornt(self): #取得佇列前端的項目
      if self.qhead is None:
         print('佇列是空的')
      else:
         print('前端', self.qhead.item)

   def rear(self): #取得佇列後端的項目
      current = self.qhead
      while current:
         if current.next is None:
            print('後端', current.item)
         current = current.next

   def show(self):
      current = self.qhead
      print('佇列：', end = '')
      while current:
         print(current.item, end = ' ')
         if current.next is None:
            break
         current = current.next
      print()

que = Queue()
number = ['one', 'two', 'three', 'four', 'five']
for k in number:
   que.enqueue(k)
que.show()
que.dequeue()
que.dequeue()
que.dequeue()
que.dequeue()
que.dequeue()
que.show()
que.fornt()
que.rear()
que.enqueue(256)
que.show()