Stacks and queues are foundational data structures that are useful for problems that rely on adding and removing elements in a particular order. It's important to be comfortable with these two data structures.
A stack stores objects such that the most recently added objects are the first ones to be removed (LIFO: last in, first out). An example to help you remember the mechanics of a stack is to associate it with stacks in real life. In a stack of plates, the ones placed on top will be the first ones removed!
It's important to know the common operations of a stack. The two key stack operations are:
- pop(): removing an item from the stack in last in, first out order (LIFO)
- push(item): adding an item (to the top of the stack)
A queue stores objects such that the objects added earliest are the first ones to be removed (FIFO: first in first out). An example to help you remember the mechanics of a queue is to associate it with queues in real life. In a queue of people waiting to get a seat in a restaurant, the first people in line (in the queue) will be the first to get a table.
It's important to know the common operations associated with a queue. The two important queue operations are:
- dequeue(): removing an item from the queue in first in, first out order (FIFO)
- enqueue(item): adding an item (to the back of the queue)
- Stacks are very useful for their backtracking features. For example, parsing questions tend to use stacks because of their LIFO property.
- Stacks can be used to implement recursive solutions iteratively.
- Queues are useful when the ordering of the data matters because they preserve the original ordering. For example, queues are used for caching.
-
Stacks:
-
Queues: