The Queue Data Structure
Last week I talked about the stack data structure and it’s two operations push and pop. This week I talk about the queue data structure, in a lot of ways it is the opposite of a stack…sorta kinda. Any way the format will be the same.
- What is a queue
- What are its operations
- What are the run time complexities of those operations
What Is It
A queue is a data structure that is a collection of items that follows FIFO (First In First Out) order. This is the opposite of a stack which is LIFO order (Last In First Out). We see queues all the time in our everyday lives, here are a few examples:
- We are in line at a drive thru
- Listen to a playlist of songs
- Send documents to a printer
As far as programming is concerned, you would use queues whenever you want to maintain sequential order in your logic.
The Enqueue & Dequeue Operations
This data structure only has two main operations: Enqueue and Dequeue.
The enqueue method takes an item and puts it at the bottom of a collection. Since accessing a collection has constant runtime the run time analysis of the enqueue operation is O(1).
The dequeue method takes the top element of a collection and removes it from that collection. Once again since accessing a collection has a constant runtime this means the dequeue method has a runtime analysis of O(1) as well.
Conclusion
The queue data structure is simple in its theory and implementation. Like its counterpart the stack, it is used when order matters in your algorithms. For a helpful guide to Big O notation check out my study guide and support this blog! If you have any questions please feel free to comment below.