Stacks and Queues
Stacks and queues are foundational data structures that are useful when adding and removing in particular orders. It's important to be comfortable with these two data structures.
A stack is a data structure that stores objects in which the most recently stored 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. With a stack of plates, the plates that are placed on top of a stack will be the first ones that are removed from the top!
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 a last in, first out order (LIFO)
- push(item): adding an item to the stack
A queue is a data structure that stores objects in which the most stored objects are the first ones to be removed. A helpful acronym associated with queues is 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. With a queue of people waiting to get a seat in a restaurant, the first people to get in the queue will be the first people seated at that restaurant.
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 a first in, first out order (FIFO)
- enqueue(item): adding an item to the queue
- Stacks are very useful for it's backtracking features. For example, parsing questions tend to use stacks because of the LIFO property.
- Stacks can be used to implement recursive solutions iteratively.
- Queues are useful when the ordering of the data matters as it preserves that ordering. For example, they're used for caching.
-
Stacks:
-
Queues: