How to implement stacks and queues in python?



The stacks and queues in python programming can be implemented using list method. Let’s see one by one.


Using lists as stacks

The list method makes it very easy to implement a stack in python programming, where the last element added is the first element retrieved (“last-in, first-out”). 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.

To add an item to the top of the stack, use the append() method.

To pop an item from the top of the stack, use pop() method without an explicit index.

Example:

num = [10,20,30,40]
print(f"The list of number:{num}")
num.append(50)  #adding new item ie 50
print("new list:",num)
first_out = num.pop()
print("popping the last added item first:",  first_out)
print(num)

Output:

The list of number:[10, 20, 30, 40]
new list: [10, 20, 30, 40, 50]
popping the last added item first: 50
[10, 20, 30, 40]



Using lists as queues

It is also possible to implement lists as queues In python, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of the list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one).

To implement a queue in python, use collections.deque which was designed to have fast appends and pops from both ends.

Example:

from collections import deque
names = deque(["pema", "sonam", "karma"])
print(f"Inital list: {names}")
names.append("Tashi") # adding Tashi to the list
names.append("Choden") # adding Choden to the list
print(f"Updated list: {names}")
print(f"Popping first item:{names.popleft()}")
print(f"Popping second item:{names.popleft()}")
print(f"Final list of names: {names}")

Output:

Inital list: deque(['pema', 'sonam', 'karma'])
Updated list: deque(['pema', 'sonam', 'karma', 'Tashi', 'Choden'])
Popping first item:pema
Popping second item:sonam
Final list of names: deque(['karma', 'Tashi', 'Choden'])