DinS          Written on 2017/4/25

1. Visually, what is a queue(队列)?

See featured image above.

Queue is a specialized data structure that can be implemented as a list. It follows a special rule called first-in-first-out, or FIFO. In many occasions using queue will simplify your codes

2. Access

We can only get the front element from queue. As a list it only needs O(1).

3. Insert

We can only insert new elements to the rear of queue. As a list this needs only O(1).

4. Delete

We can only delete the front element from queue. As a list it only needs O(1).

5. Some illustrations

First we have this queue.

Second we delete the front element.

Now we have this queue.

Please notice that although in the picture Data1 and Data2 moved position, in reality they won’t. If they did, we can’t ensure the O(1) time operation.

Third we insert a new element.

6. Queue and Deque

Deque(双端队列), read as [dek], is an improved version of queue. It supports access, insert and delete operations for both front and rear. Using list it is not a hard job. The interesting part is that in STL deque is a more fundamental one. Besides the above operations, it supports access to any elements in O(1) time, like a vector. Queue, on the contrary, inherits from deque.