# 编程笔试题(五)队列




队列也是是常用的数据结构。尽管一般的面试里不会让你直接写一个队列的实现，不过了解队列是必须的。

### 定义

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

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

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

* enqueue: 将元素加入队列
* dequeue: 将排在最前面的元素推出队列

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

![](http://ww1.sinaimg.cn/large/726a2979gy1g0fe87h8ayj20go0ax3yk.jpg)

### 使用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的具体实现

```python

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中进程的等待队列，消息队列等都是队列的具体应用。




原始封面

![课程图片](https://images.unsplash.com/photo-1482938289607-e9573fc25ebb?w=300)