Stacks and queues are two fundamental data structures in computer science. They are used for manipulating collections of objects. This article aims at giving a general overview of stacks and queues and helping you to understand what they are.
Let’s see what are the operations supported by these two data structures.
The two main operations of a stack are push and pop:
- push() adds a new element at the end of the structure (or better to say, at the top of the stack);
- pop() extracts and returns the last added element.
The two main operations of a queue are enqueue and dequeue:
- enqueue() adds a new element at the end (also said the back) of the structure;
- dequeue() extracts and returns the first element that was added to the queue, also said the front element.
Both structures will also typically support:
- isEmpty() to test whether the structure is empty or not;
- size() that returns the number of elements contained.
Differences between stacks and queues
From the preceding paragraph, the main difference between a stack and a queue is the order of the returned elements. A queue returns them in the order they were added to it, a stack in reverse order. A stack is a LIFO (last in, first out) structure, a queue is a FIFO (first in, first out) structure.
To understand what a stack is, you can imagine a stack of dishes. You can add (push) dishes only at the top of the stack. Likewise you can only remove (pop) the last added dish from the top. To add or remove dishes in the middle you should first remove the other dishes that are above the insertion point and put them again at the end. Another example: some days ago I was taking apart a toy with my son and I realized that if I had to store the sequence of the operations I would have to use a stack. Why? Because to rebuild it I would have to use the same operations, but in reverse order.
In a computer program for example you will use a stack to implement the undo operation. The stack will store the history of all the executed operations. When you click undo, the stack will pop the last operation done to undo it.
To understand what a queue is, you can imagine a queue of people waiting for the bus. The first arrived person will be the first to get on the bus. An example of a queue is the printer queue: every print job is sent to the printer queue. Then we expect they are printed in the same order as they have been sent to the queue.
Except for the difference in the order, stacks and queues have a lot in common:
- elements are ordered;
- very efficient at adding and removing elements from their end, normally constant time O(1);
- no support (or better to say, very inefficient) for random access;
- no support (or better to say, very inefficient) for adding and removing elements in the middle of the structure.
Stacks and queues compared to arrays
So, you’ll use them only when you can meet the conditions above. If you compare stacks and queues to traditional arrays, they are the opposite for many aspects:
- arrays are very efficient at random access, normally constant time O(1);
- arrays are very inefficient (or it is forbidden by the language) at resizing (adding and removing elements).
So, depending on your needs, you’ll have to choose the right structure. For example, if you have to do a lot of insertions and deletions in the middle of the structure, array, queues and stacks are not the way to go. A linked list could be the solution.