Data structures are essential for managing the way data is stored in computers, allowing for straightforward access and modification of that data. Stacks and Queues represent some of the foundational data structures established in the field of computer science. Interestingly, a basic Python list can serve as both a queue and a stack. A queue operates under the FIFO principle (First In First Out) and is often utilized in programming for organizing data. Typically, stacks and queues can be implemented using either an array or a linked list.
Stack
A Stack is a data structure that adheres to the LIFO (Last In First Out) principle. To construct a stack, we require two fundamental operations:
- push: This operation places an element onto the uppermost position of the stack.
- pop: This operation extracts an element from the topmost position of the stack.
Operations on Stack
There are several operation of Stack in Python. Some of them are as follows:
- 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, underflow occurs in the stack. Secondly, if a stack contains some elements, the topmost element gets removed. It reduces the stack size.
- Traversing: It involves visiting each element of the stack.
Characteristics of the Stack
There are several characteristics of the Stack in Python. Some of them are as follows:
- Insertion order of the stack is preserved.
- Useful for parsing the operations.
- Duplicacy is allowed.
Python Stack Example using List
Allow us to illustrate the concept of a Stack in Python with an example.
# Code to demonstrate Implementation of
# stack using list
x = ["Python", "C", "Android"]
x.push("Python")
x.push("C++")
print(x)
print(x.pop())
print(x)
print(x.pop())
print(x)
Output:
['Python', 'C', 'Android', 'Python', 'C++']
C++
['Python', 'C', 'Android', 'Python']
Java
['Python', 'C', 'Android']
Queue
A Queue adheres to the First-in-First-Out (FIFO) concept. It is accessible from both ends, allowing for the effortless addition of elements to the rear while simultaneously enabling the removal of elements from the front.
To create a queue, it is essential to have two fundamental operations:
- enqueue: This operation appends an item to the rear of the queue.
- dequeue: This operation extracts the item from the front of the 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. First, if no element is present in the queue, underflow occurs in the queue. Secondly, iif a stack contains some elements, element present at the front gets deleted.
- Traversing: It involves to visit each element of the queue.
- Insertion order of the queue is preserved.
- Duplicacy is allowed.
- Useful for parsing CPU task operations.
Operations on Queue
Characteristics of Queue
Note: The implementation of a queue is a little bit different. A queue follows the "First-In-First-Out". Time plays an important factor here. The Stack is fast because we insert and pop the elements from the end of the list, whereas in the queue, the insertion and pops are made from the beginning of the list, so it becomes slow. The cause of this time difference is due to the properties of the list, which is fast in the end operation but slow at the beginning operations because all other elements have to be shifted one by one.
Python Queue Example
To illustrate the concept of a queue in Python, let us consider an example.
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