Introduction

Many of the beginners on the site are pre-college students. Often beginners will learn by reading tutorials on the Internet, copying code from books, and trying out things that they find interesting.

This article is part of a series that focuses on giving pre-college developers the basics they need to understand data structures.

The previous article was Arrays, Dynamic Arrays, and Linked Lists.

This article is about stacks and queues.

The Stack

Imagine you have a bunch of papers. You push one paper onto the stack. Now you can only easily access the top paper. You push another paper onto the stack. The earlier paper is now covered and inaccessible, and the new paper is available for use. When you are done with the top paper you can remove it from the stack, exposing the one beneath.

That is the idea of a stack.

A stack is a LIFO structure. That stands for Last In First Out. When you add and remove from a stack, the last one that you put in will be the first one you get out.

There are really only three operations needed for a stack: Push, Pop, and Top. Push will add an object to the stack. Pop will remove an object from the stack. Top will give you the last-most object on the stack.

These containers are part of the standard libraries of most languages. In C++ it is called a stack. In Java and C# it is a Stack. (Yes, the only difference is the capitalization of the first letter.)

Under the hood, a stack is often implemented as a dynamic array. If you recall from that data structure, the fastest operations on a dynamic array are to add and remove elements from the end. Since a stack is always adding and removing from the end, it is usually extremely fast to push and pop objects onto a stack.

The Queue

Imagine you are waiting in line for something. The first person in the line gets served, then leaves. The second person in line gets served, then leaves. More people walk over to the line and stand at the end of it.

That is the idea of a queue.

A queue is a FIFO structure. That stands for First In First Out. When you add and remove from a queue, the first one you put in will be the first one you get out.

A queue only needs a few operations: Push_Back, Pop_Front, Front, and Back. Push_Back will add to the end of the queue. Pop_Front will remove from the front of the queue. Front and Back will let you examine the two ends of a queue.

Programmers will frequently need to add and remove from both ends of a queue. This is called a double ended queue, or deque. In this case they add two other operations, Push_Front and Pop_Back.

Again, these containers are included in most major languages. In C++ it is a queue and a deque. Java specifies interfaces for both queue and deque, then relies on a LinkedList for the implementation. C# provides a Queue class, but not a Deque class.

Internally, a queue and a double-ended queue can be somewhat complex. Since objects can come and go at either end, the internal container needs to be able to grow and shrink at the beginning and at the end.

Many implementations will rely on multiple pages of memory. When either end grows beyond the current page, an extra page is added. Similarly a page is removed when it is no longer needed. Java follows a different route; it requires a little additional memory using a linked list rather than pages of memory, but it works for the language.

Priority Queue

There is a very common variation on the queue. A priority queue is very similar to a basic queue. You push things on to the end, and you pop things off from the front.

The difference is that you can give priority to certain items in the queue. All of the most important items are processed in a FIFO order. Then the next priority items are processed in a FIFO order. Repeat until the lowest priority items are handled in FIFO order. If you add a new item that is higher priority than the rest of the queue, it will immediately jump to the head of the line.

In C++ this is called a priority_queue. In Java it is a PriorityQueue. C# does not include a priority queue in the standard library.

Priority queues are not just useful in getting yourself to the front of the line on the corporate printer. Priority queues can be used to easily implement algorithms like the A-star searching routine. The most likely results can be given a higher priority over the less likely results. You could choose to build your own system for sorting and organizing your A-star search, but it will be much easier to just use the built-in priority queue.

Conclusion

Stacks and queues and deques and priority queues can be implemented in terms of other data structures. They are not fundamental data structures, but they are frequently used.

They are very efficient when you need to work only with the endpoints of your data, and don’t really care what is in the middle.

This will be continued in Part 3: Trees and Heaps

(This appeared as a gamedev.net featured article.)