# Stacks and Queues

• Recall queues and stacks.

• A queue is a data structure that is similar in spirit to a fair line. As you can see in this photo, the first dog in line can expect to be the first to pee on the tree.

• A stack is a data structure that is similar in spirit to a pile of trays or plates in a dining hall. When the dining staff put plates out before meals, they pile them from the bottom to the top, and then you take the top-most plate. The last plate that the staff put on the piles is the first one taken from the pile.

• Since Project 1 will involve both queues and stacks, you might first try to create two separate data structures for each. However, it is much easier to maintain just one data structure. STL deque (usually pronounced like deck) allows you to do exactly that. It is a double-ended queue. You can push items to the front and to the end and you can remove items from the front and from the end in constant time.

To use deques, #include <deque> atop your code. Declare a deque of ints with this line of code.

deque<int> numbers;

After you insert some integers, the deque might look something like this:

 …​ 281 101 183 280 203 381 …​