Stacks and Queues are commonly used data structures capable of performing specific tasks in a specialised way.
Let’s dive deeper!
What are data structures?
Data structures in general terms refer to a way of storing and organising data in a computer so that it can be used more efficiently and can give better results.
Depending on the application, the type of data structure is chosen and implemented.
So, we will discuss two data structures in this article, namely stacks and queues. Let’s get started!
Stacks
Stacks are linear structures that follow the LIFO (Last In First Out) manner which means the last inserted will be removed first. The insertions and deletions take place at one end of the stack only i.e. the top of the stack.
For example, a stack of plates, the plate on the top was inserted in the stack last and is also picked up first.
Stacks follow certain rules as listed below
- Data can be only removed from the top of the stack i.e. the last element added will be removed first. This is known as POP operation.
- When adding new data it will only be added to the stacks top and this is termed as PUSH operation.
Another important point to note is that stacks are dynamic data structures so by increasing the number of elements it can grow or by decreasing the number of elements it can shrink in size. It does not have a fixed size. Whereas a static data structure will have a fixed size.
Terminologies
Now there are a few terminologies while referring to a stack
Peek
Peek refers to inspecting the value at the stack’s top. It does not remove the value from stack as it is just for inspecting. And so it is also known as inspection.
Overflow
Overflow refers to a case in the stack when the stack is completely filled and new elements are trying to be added to it. In such situations, where we have previously fixed the size of the stack, it does not increase in size but causes this error.
Underflow
This occurs when we are using the POP operation to remove elements from the stack. If the stack is empty and further no elements can be removed, Underflow situation occurs and causes an error.
Implementing Stack in Python
To implement Stacks in Python, we use Lists
So we can perform the below options on a List in python which behaves as a Stack
Peek
To check the top most value of the stack
Syntax –
<stack> [top]
Where top is the index of the last element in the list.
We can reach the top of the stack by finding its length and subtracting 1 from it.
{ len(stack)-1 } . We do so because the index in a list starts from 0.
Push
To add a new element to the list
Since the list behaves as a stack, we will append the item to the end of the list only.
Syntax-
stackname.append(item)
Stackname is the name of the stack and item refers to the value to be appended to the stack.
Pop
To remove an element from the list
Since the list behaves as a stack, so element will be removed from the end only.
Syntax-
stackname.pop()
This will automatically pop the last element from the stack and return it.
Applications of Stack
Stack follows LIFO manners and so it is useful in many cases. For example,
Reversing a line and in implementing polish strings, like infix to postfix conversion, postfix and prefix expression evaluation, etc.
Queues
What are Queues?
Queues are also linear lists similar to Stacks, but Queues are implemented in FIFO (First in First Out) manner.
In Queues, the insertions take place at the rear-end while the deletions take place at the front-end only.
For example, a queue in real life i.e. people standing in a line. So, the person who joined the line first will be the first one to leave the line. Any new person will join at the end and the person at the first place will only be allowed to leave.
Instead of Pop and Push operations we use the terms Enqueue and Dequeue operations in queues.
Where Enqueue is the insertion of new elements to the queue and this takes place at the rear of the queue.
Dequeue refers to deletion of elements from the queue and this takes only at the front of the queue.
Terminologies
Peek
Peek refers to inspecting the value at the queues top. It does not remove the value from the queue as it is just for inspecting. And so it is also known as inspection.
Overflow
Overflow refers to a case in the queue when the queue is completely filled and new elements are trying to be added to it. In such situations, where we have previously fixed the size of the queue, it does not increase in size but causes this error. It happens when a user tries to enqueue items into the queue.
Underflow
This occurs when we are using the dequeue operation to remove elements from the queue. If the queue is empty and further no elements can be removed, Underflow situation occurs and causes an error.
Implementing Queues in Python
Peek
Syntax- QueueName [front]
Here, QueueName refers to the name given to the queue and front refers to the index of the first value in the queue.
Enqueue
Syntax- QueueName.append(item)
The append function will add the item to the end of the queue. Here item is the value to be added to the queue and not the index.
Dequeue
Syntax- Queuename.pop(0)
Since deletions in a queue takes place from the front-end, we give the index 0 to the pop so this will remove the first element of the queue and return it.
Calculating Number of Elements in a Queue
To determine the size of the queue, we use the formula-
Number of elements in a queue = rear – front +1
Usually, in python front =0 and rear = len(<queue>) – 1
Also, you can directly get the size of the queue using the in-built function len
{ len(<queue>) }
Variations in Queues
Depending on the requirement, we can use the type of queue we want.
Two popular types of queues are Circular queues and Deque (Double-Ended queues).
Circular Queues
Circular queues are queues which are implemented in a circular manner rather than a straight line.
These are helpful to remove the unutilised space in a queue of a fixed size where insertions and deletions are taking place which leave a few spaces in between.
In Python, we don’t generally use circular queues as we use lists which are itself dynamic in nature i.e. they can grow and shrink according to the requirement.
Deque (Double-Ended queues)
As the name suggests deque are a special type of queues where elements can be added or removed from both the ends but not from the middle.
In deque, we further have two variations –
Input restricted deque and output restricted deque
Input Restricted Deque
A deque in which insertions are allowed only at one end but deletions can take place from both the ends.
Output Restricted Deque
A deque in which deletions are allowed only at one end but insertions can take place from both the ends.
Applications of Queues
General cases of queues are seen where FIFO is implemented. For example in a waiting list or a call center or the list of passengers at a bus stop or an airport.
Queues are also used when there is resource sharing. For example if multiple systems are using a common printer, the computer which first sends the command will be able to use the printer first and so on.
Queues are also used in many computer applications and to organise the structures in a better and efficient manner.
So that was all about Stacks and Queues. Good Day!