[Python数据结构] 使用 Circular List实现Queue

1. Queue
队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端进行删除操作。队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

Queue[维基百科]

2. Queue ADT
队列是一种抽象数据类型，其实例Q需要支持两种方法：
　　1）Q.enqueue(e) : Add an element to the back of queue.
　　2）Q.dequeue( ) : Remove and return the first element in the queue

另外，为了方便使用，我们还定义了以下方法：
　　3）Q.first() : Return the element at the front of the queue
　　4）Q.is_empty() : Return True if the queue is empty
　　5）len(Q) : Return the number of elements in the queue

3. Queue Implementation

 class Empty(Exception):

     """Error attempting to access an element from an empty container"""

     pass

 class ArrayQueue():

     """FIFO queue implementation using a python list as underlying storage."""

     Default_capacity = 10

     def __init__(self):

         """Create an empty queue"""

         self.data = [None] * ArrayQueue.Default_capacity  # reference to a list instance with a fixed capacity.

         self.size = 0  # an integer representing the current number of elements stored in the queue.

         self.front = 0  # an integer that represents the index within data of the first element of the queue.

     def __len__(self):

         """Return the number od elements in the queue."""

         return self.size

     def is_empty(self):

         """Return True if the queue is empty."""

         return self.size == 0

     def first(self):

         """Return the element at the front of the queue.

         Raise Empty exception if the queue is empty."""

         if self.is_empty():

             raise Empty('the queue is empty')

         return self.data[self.front]

     def dequeue(self):

         """Remove and return the first element in the queue.

         Raise Empty exception if the queue is empty."""

         if self.is_empty():

             raise Empty('the queue is empty')

         answer = self.data[self.front]

         self.data[self.front] = None

         self.front = (self.front + 1) % len(self.data)

         self.size -= 1

         return answer

     def enqueue(self, e):

         """Add an element to the back of queue."""

         if self.size == len(self.data):

             self.resize(2 * len(self.data))

         avail = (self.front + self.size) % len(self.data)

         self.data[avail] = e

         self.size += 1  

     def resize(self, cap):

         """Resize to a new list of capacity."""

         old = self.data

         self.data = [None] * cap

         walk = self.front

         for k in range(self.size):

             self.data[k] = old[walk]

             walk = (1 + walk) % len(old)

         self.front = 0

4. 执行结果：

 q = ArrayQueue()

 l = np.random.randint(0, 10, size=(20, ))

 for i in l:

     q.enqueue(i)

 q.data

 [0, 1, 5, 3, 9, 5, 0, 9, 1, 0, 4, 6, 7, 0, 2, 5, 9, 3, 3, 9]

 q.dequeue()

 0

 q.data

 [None, 1, 5, 3, 9, 5, 0, 9, 1, 0, 4, 6, 7, 0, 2, 5, 9, 3, 3, 9]

 q.first()

 1

 q.data

 [None, 1, 5, 3, 9, 5, 0, 9, 1, 0, 4, 6, 7, 0, 2, 5, 9, 3, 3, 9]

巴特西

[Python数据结构] 使用 Circular List实现Queue

[Python数据结构] 使用 Circular List实现Queue

最新文章

热门文章