Unlike an array, in stacks and queues in data structures, there is no random access operation (we can not access an element directly with an ‘index’). We usually have fewer methods/actions that we can perform such as push(), pop(), peek(), enqueue(), and dequeue() all of which deal exclusively with the element at the beginning of the end of the Data structure.
But…
Question: This sounds so limiting since we only can access the first or the last element in the data structure. Why would we ever want to use something like this? Why don’t we just use arrays for more flexibility?
Why Stacks and Queues?
Answer: Stacks and Queues are usually ‘higher-level data structures built on top of lower-level ones (array or linked list) to limit the operations we can do on them. That’s a benefit if we want constrained access.
Having this limited ability on a data structure is an advantage because we can control whoever uses this data structure that performs only the write operations that are efficient. For example, we won’t have to wonder if somebody randomly inserted an element into the middle of our list, messing up some invariants. That saved us from a lot of issues. Let’s take a more close look at them.
What Is a Stack?
A stack is a one-ended linear data structure that models a real-world stack by having two primary operations, namely, push and pop.
In the image below, we could see one data member getting popped off of the top of the stack and another one getting added to it. There is a top pointer pointing to the block at the top of the stack. This is because elements in a stack always get removed and added to the top of the pile. This behavior is commonly known as LIFO (Last In First Out).
1. Stack operations
The following are the 2 basic operations that can be performed on a stack.
- Push function: Add an element to the top of the stack
- Pop function: Remove the top element (and might return it)
Visualization of Stack’s basic Operations
Furthermore, the following additional functions are provided for a stack in order to check its status.
- Peek function: Return the top element of the stack without removing or deleting it
- isEmpty function: Check if the stack is empty or not
- isFull function: Check if the stack is full or not
Everything operates on the top of the stack. We don’t have access to anything else but the top. This is critical in understanding how it works.
2. Complexity analysis
The following complexity table assumes that you implemented a stack using a linked list
3. Stacks applications
When and where is a Stack used? we use Stack a lot in programming without even noticing it, here are some examples:
- Can be used for expression evaluation (e.g.: a shunting-yard algorithm for parsing and evaluating mathematical expressions).
- Can be used to implement function calls in recursion programming.
- Used by undoing mechanisms in text editors to undo text that we’ve written (Cmd + Z on Mac OS and Ctrl + Z on Windows)
- Used in Browser to navigate backward and forwards
- Can be used to do a Depth First Search (DFS) on a graph
- Used behind the scenes to support recursion by keeping track of previous function calls
What Is a Queue?
A queue is also a linear data structure that models real-world queues by having two primary operations, namely, enqueue (we can think of that as “enter the queue”) and dequeue (we can also think of that as “delete from the queue”). This structure is named “queue” because of the fact that it resembles a real-world queue — (where people are waiting in a queue).
Every queue has a front and a back end (sometimes called ‘rear’). We insert elements through the back and remove them through the front.
A queue is a FIFO (First In First Out — the element placed at first can be accessed at first) structure which can be commonly found in many programming languages.
1. Queue operations
The following are the 3 basic operations that can be performed on a queue.
- Enqueue function: Add an element to the end of the queue
- Dequeue function: Remove the element from the beginning of the queue
- Peeking function: Looking at the value at the front of the queue without removing it
2. Complexity analysis
As we can see in the image, enqueuing and dequeuing operations take constant time O(1). However, checking if an element is contained within the queue is linear time O(n) since we would potentially need to scan through all of the elements.
There is also element removal (not dequeuing) internally. It requires linear time since we have to scan through all elements in the worst case.
3. Queues applications
- Used to manage threads in multithreading.
- Can be used to efficiently keep track of the x most recently added elements
- Web server request management where we want first come first serve. For example: At any given moment, our web server can only serve up to maximum of 50 people simultaneously.
If 70 requests come in in a short period of time, then we will not be able to process all of them. So the webserver pops only 50 requests from the queue and puts the remaining 20 on hold. When the web server finishes processing a request, it dequeues the next one to serve and it keeps doing that until the queue is empty.
- Breadth-first search (BFS) graph traversal
- Used to implement queuing systems (e.g.: priority queues)
- Used in network printer: The printer can only serve one single request at a time. So if other requests come when the printer is busy, the program that manages the printer will not reject those requests but put them in a queue waiting for execution. The first request will be served first (FIFO).
We hope that this article has given you a picture of stacks and queues with data structures in mind. Don’t forget to subscribe to our blog and follow Designveloper’s Facebook, Twitter, and LinkedIn.
Also published on
Share post on
Read more topics
