编程笔试题(五)队列

队列在现实生活中非常常见。

比如去一些餐厅吃饭是需要排队的，先来的先吃，这就是一个等待的队列。

队列是先到先出的,FIFO(first in, first out)。队列有下面一些主要操作。

enqueue: 将元素加入队列

dequeue: 将排在最前面的元素推出队列

下面的图演示了这两个过程。

使用python deque来实现队列

python内置了deque(发音是deck)实现。

所谓的deque实际上就是double end queue的意思。

普通的queue只能在尾部推入元素，从头部移除元素，而deque可以从任意方向推入和移除元素。

在命令行里使用pydoc collections.deque可以查看deque类的内置方法。

比较重要的一些方法有

|  append(...)
|      Add an element to the right side of the deque.
|
|  appendleft(...)
|      Add an element to the left side of the deque.
|  extend(...)
|      Extend the right side of the deque with elements from the iterable
|
|  extendleft(...)
|      Extend the left side of the deque with elements from the iterable
|
|  pop(...)
|      Remove and return the rightmost element.
|
|  popleft(...)
|      Remove and return the leftmost element.
|
|  remove(...)
|      D.remove(value) -- remove first occurrence of value.
|
|  reverse(...)
|      D.reverse() -- reverse *IN PLACE*
|
|  rotate(...)
|      Rotate the deque n steps to the right (default n=1).  If n is negative, rotates left.
下面是queue的具体实现

from collections import deque
class Queue():
    def __init__(self):
        self.data = deque()
    def enqueue(self, elm):
        self.data.append(elm)
    def dequeue(self):
        return self.data.popleft()
    def is_empty(self):
        return len(self.data) == 0
    def size(self):
        return len(self.data)

import unittest
class QueueTestCase(unittest.TestCase):
    def test_enqueue_and_dequeue(self):
        q = Queue()
        self.assertTrue(q.is_empty())
        q.enqueue(1)
        self.assertFalse(q.is_empty())
        self.assertEqual(q.size(), 1)
        q.enqueue(2)
        q.enqueue(3)
        self.assertFalse(q.is_empty())
        self.assertEqual(q.size(), 3)
        self.assertEqual(1, q.dequeue())
        self.assertEqual(2, q.dequeue())
        self.assertEqual(3, q.dequeue())

if __name__ == '__main__':
    unittest.main()

思考

我们所知道的cpu中进程的等待队列，消息队列等都是队列的具体应用。