Mwenda Harun Mbaabu
Data structures and algorithms in Python are two of the most fundamental concepts in computer science. They are indispensable tools for any programmer.
Data structures in Python deal with the organization and storage of data in the memory while a program is processing it. On the other hand, Python algorithms refer to the detailed set of instructions that helps in the processing of data for a specific purpose.
Data structure organises the storage in computers so that we can easily access and change data.
Stacks and Queues are the earliest data structure defined in computer science. A simple Python list can act as a queue and stack, also we can implement stack and queue using classes and functions and today we will be looking at the two approaches.
A queue follows FIFO rule (First In First Out) and used in programming for sorting. It is common for stacks and queues to be implemented with an array or linked list.
1). Stack.
A Stack is a data structure that follows the LIFO(Last In First Out) principle. To implement a stack, we need two simple operations:
push : It adds an element to the top of the stack.
pop : It removes an element from the top of the stack.
Operations:
- Adding - It adds the items in the stack and increases the stack size. The addition takes place at the top of the stack.
- Deletion - It consists of two conditions, first, if no element is present in the stack, then underflow occurs in the stack, and second, if a stack contains some elements, then the topmost element gets removed. It reduces the stack size.
- Traversing - It involves visiting each element of the stack.
Characteristics:
Insertion order of the stack is preserved.
Useful for parsing the operations.
Duplicacy is allowed.
# Implementation of stack using Python list.
x = ["Python", "C", "Android"]
x.append("Java")
x.append("C++")
print(x)
print(x.pop())
print(x)
print(x.pop())
print(x)
Output:
['Python', 'C', 'Android', 'Java', 'C++']
C++
['Python', 'C', 'Android', 'Java']
Java
['Python', 'C', 'Android']
2). Queue
A Queue follows the First-in-First-Out (FIFO) principle. It is opened from both the ends hence we can easily add elements to the back and can remove elements from the front.
To implement a queue, we need two simple operations:
enqueue - It adds an element to the end of the queue.
dequeue - It removes the element from the beginning of the queue.
Operations on Queue
- Addition - It adds the element in a queue and takes place at the rear end, i.e., at the back of the queue.
- Deletion - It consists of two conditions - If no element is present in the queue, Underflow occurs in the queue, or if a stack contains some elements then element present at the front gets deleted.
- Traversing - It involves to visit each element of the queue.
Characteristics:
- Insertion order of the queue is preserved.
- Duplicacy is allowed.
- Useful for parsing CPU task operations.
import queue
# Queue is created as an object 'L'
L = queue.Queue(maxsize=10)
# Data is inserted in 'L' at the end using put()
L.put(9)
L.put(6)
L.put(7)
L.put(4)
# get() takes data from
# from the head
# of the Queue
print(L.get())
print(L.get())
print(L.get())
print(L.get())
Output:
9
6
7
4
Use Case:
1). Stack.
Imagine you're a software engineer working on a brand new word processor. You're tasked with creating an undo feature - allowing users to backtrack their actions till the beginning of the session.
A stack is an ideal fit for this scenario. We can record every action the user takes by pushing it to the stack. When the user wants to undo an action they'll pop it from the stack.
We can quickly simulate the feature like this:
document_actions = Stack()
# The first enters the title of the document
document_actions.push('action: enter; text_id: 1; text: This is my favourite document')
# Next they center the text
document_actions.push('action: format; text_id: 1; alignment: center')
# As with most writers, the user is unhappy with the first draft and undoes the center alignment
document_actions.pop()
# The title is better on the left with bold font
document_actions.push('action: format; text_id: 1; style: bold')
2). Queues.
Queues have widespread uses in programming as well. Think of games like Street Fighter or Super Smash Brothers. Players in those games can perform special moves by pressing a combination of buttons. These button combinations can be stored in a queue.
Now imagine that you're a software engineer working on a new fighting game. In your game, every time a button is pressed, an input event is fired. A tester noticed that if buttons are pressed too quickly the game only processes the first one and special moves won't work!
You can fix that with a queue. We can enqueue all input events as they come in.
This way it doesn't matter if input events come with little time between them, they'll all be stored and available for processing. When we're processing the moves we can dequeue them.
A special move can be worked out like this:
input_queue = Queue()
# The player wants to get the upper hand so pressing the right combination of buttons quickly
input_queue.enqueue('DOWN')
input_queue.enqueue('RIGHT')
input_queue.enqueue('B')
# Now we can process each item in the queue by dequeueing them
key_pressed = input_queue.dequeue() # 'DOWN'
# We'll probably change our player position
key_pressed = input_queue.dequeue() # 'RIGHT'
# We'll change the player's position again and keep track of a potential special move to perform
key_pressed = input_queue.dequeue() # 'B'
# This can do the act, but the game's logic will know to do the special move
More examples to use:
Stack data structure in Python
Queue data structure in Python
If you find some errors in the article or have an addition or some inputs please feel free to leave a feed back or comment or DM me on twitter, https://twitter.com/HarunMbaabu
Conclusion.
Stacks and queues are simple data structures that allow us to store and retrieve data sequentially. In a stack, the last item we enter is the first to come out. In a queue, the first item we enter is the first come out.
We can add items to a stack using the push operation and retrieve items using the pop operation. With queues, we add items using the enqueue operation and retrieve items using the dequeue operation.
In Python, we can implement stacks and queues just by using the built-in List data structure. Python also has the deque library which can efficiently provide stack and queue operations in one object. Finally, we've made our stack and queue classes for tighter control of our data.
There are many real-world use cases for stacks and queues, understanding them allows us to solve many data storage problems in an easy and effective manner.
