Phylis Jepchumba, MScData structures are a way of organizing and storing data so that they can be accessed and worked with efficiently while Algorithms are sequence of well defined instructions for solving a problem or a accomplishing a given task.
This article gives a detailed understanding of the most commonly used data structures that is Stack and queue and their implementation in python.
STACK
Stack is one of the earliest data structure defined in computer science as a linear data structure which stores items using LIFO( Last In First Out) principle for insertion and deletion.
To get a clear understanding of a stack think about a pile/stack of books. You add a book at the top of the stack, so the first one to be picked up will be the last one that was added to the stack.
Stack has two operations:
- Push- adds an item to the top of the stack.
- Pop- removes an item from the stack.
Why do we use stacks?
- Stack are simple to learn and implement.
- Stack allows us store and retrieve data sequentially.
- Stacks take O(1) time for insert and delete operations.
Real world use cases of a stack.
- Web browsers use stack to keep track of URL that you have accessed previously. When you visit a new page, it is added to the stack when you hit the back button, stack is popped and previous URL is accessed.
- Undo mechanism in text editor uses stack to keep all changes.
- To implement other data structures- stack is used to implement searches in graphs and trees.
- Compilers and Parsers uses stack
More applications of Stack Data structures
Stack Methods
Stack operations are implemented using the following methods:
- stack.IsEmpty- Returns True if a stack is empty and false otherwise.
- stack.length()- Returns length of stack.
- stack.top()- returns a pointer/reference to top element in stack.
- stack.push(x)- inserts element x to the top of the stack.
- stack.pop()- Removes top element of stack and returns it.
Stack implementation in Python.
In python, we can implement stack using the following ways;
- Using the built-in List data structure.
- Using the deque library which efficiently provides stack operations in one object.
Stack Using List.
To implement stack using list, append and pop methods are used.
append() method in python adds a single item to the existing list
pop() removes the element at the specified position
Example
s = []
s.append('stack')
s.append('queue')
s.append('list')
s.append('tuple')
print(s)
Output
['stack', 'queue', 'list', 'tuple']
Using pop
s.pop()
>>tuple
s.pop()
>>list
s.pop()
>>queue
s.pop()
>>stack
s.pop()
>>IndexError: pop from empty list
QUEUES
Just like a stack, a queue is a linear data structure.
Queue stores items using FIFO (First in first out) principle for insertion and deletion.
Operations Associated with Queue in Python.
-
Enqueue: It adds an element to the end of the queue. When the queue reaches its total capacity, it reaches an overflow condition.
- Dequeue: Removes an element from the queue. When the queue becomes empty, it reaches an underflow condition.
- Front: returns the first item from the queue.
- Rare: Returns the last item from the queue.
Applications of a Queue
A queue is useful in the following scenarios;
- Handling interrupts in real-time systems- interrupts are handled in same order as they arrive.
- Handling website traffic.
- Serving request on a single shared resource like a printer or CPU task scheduling.
Applications of Queue Data Structure
How to implement queue in Python
There are different ways to implement a queue in Python. The
common ways are;
- Using built-in List data structure.
- Using collections.deque library
Implementing a Queue in Python with a List
The list’s append() and pop() methods are used to insert and delete elements from the queue.
# Initialize a queue
queue = []
# Adding elements to the queue
queue.append('Python')
queue.append('Javascript')
queue.append('Typescript')
print(queue)
Output
['Python', 'Javascript', 'Typescript']
# Removing elements from the queue
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))
print(queue)
Output
Python
Javascript
Typescript
[]
Implementing a Queue in Python with collections.deque
The deque class from the python collections module can also be used to implement a queue. It is more efficient because deque provides faster enqueue and dequeue operations.
from collections import deque
queue = deque()
queue.append('Black')
queue.append('White')
queue.append('Orange')
print(queue)
Output
deque(['Black', 'White', 'Orange'])
I hope you enjoy reading the article as much as I enjoyed writing it, the following are the useful resources and reference materials that i used.
Find the full source code here
