Open Source For Geeks: Stack and Queues in Python

Thursday, 23 May 2024

Stack and Queues in Python

Background

In the last few posts, we saw how to work with classes in Python and how it can be used in an object-oriented way. In this post, I will explain how you use a stack and queue implementation in Python. This is needed if you are doing problem-solving questions using Python or in general using Python for coding.

Remember:

Stack: "Last in First out"
Queue: "First in First out"

Using stack in Python

Stack works on logic "Last in First out".Stack is pretty straightforward. You can use a standard Python list as your stack. See below the Python code

stack = []
stack.append("Aniket")
stack.append("Abhijit")
stack.append("Awantika")
print(stack)
print("Pushing Anvi to Stack")
stack.append("Anvi")
print(stack)
print(f"Popped {stack.pop()}")
print(stack)
print(f"Popped {stack.pop()}")
print(stack)

This prints the following:

['Aniket', 'Abhijit', 'Awantika']
['Aniket', 'Abhijit', 'Awantika', 'Anvi']
Popped Anvi
['Aniket', 'Abhijit', 'Awantika']
Popped Awantika
['Aniket', 'Abhijit']

As you can see initial values in the stack were "Aniket", "Abhijit" & "Awantika". Then we pushed "Anvi" to the stack. Then we popped which gave us "Anvi", then we popped again and we got "Awantika". Remember stack is "Last in First out" and the above behavior is in line with it.

NOTE: The list works better at the end of the list, so append and pop operations happen in O(1) time complexity. So if you need a stack implementation go ahead and use a list. You could also use dequeue implementation for a stack with the same O(1) complexity - It has append and pop methods similar to queue. (That's not the case for the queue - see below).

Using Queue in Python

The queue is "First in First out". You could use list implementation in Python for queue as well but remember the note from above - The list works better at the end of the list. It does not work well with the start of the list, so if you try to remove the element from the beginning of the list, the list needs to be shifted back one place making the time complexity O(N).

You should use dequeue implementation from the collections module for O(1) push/pop operations in the queue. I will show both use cases below.

Using a list for queue implementation (Not recommended)

See below the Python code:

queue = []
queue.append("Aniket")
queue.append("Abhijit")
queue.append("Awantika")
print(queue)
print("Pushing Anvi to Queue")
queue.append("Anvi")
print(queue)
print(f"Popped {queue.pop(0)}")
print(queue)
print(f"Popped {queue.pop(0)}")
print(queue)

The output in this case is:

['Aniket', 'Abhijit', 'Awantika']
Pushing Anvi to Queue
['Aniket', 'Abhijit', 'Awantika', 'Anvi']
Popped Aniket
['Abhijit', 'Awantika', 'Anvi']
Popped Abhijit
['Awantika', 'Anvi']

As you can see this time it popped "Aniket" & "Abhijit" which are first in the list (Remember - "First in First out").

Using dequeue for queue implementation (recommended)

A deque is a generalization of the stack and a queue (It is short for "double-ended queue"). Deques support thread-safe, memory-efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction. (See documentation for more details)

NOTE: Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

See below the Python code:

from collections import  deque

queue = deque([])
queue.append("Aniket")
queue.append("Abhijit")
queue.append("Awantika")
print(queue)
print("Pushing Anvi to Queue")
queue.append("Anvi")
print(queue)
print(f"Popped {queue.popleft()}")
print(queue)
print(f"Popped {queue.popleft()}")
print(queue)

Output is the same as that of above (as using list for queue) but internally the operation is O(1) in case of dequeue unlike O(N) in case of list.

['Aniket', 'Abhijit', 'Awantika']
Pushing Anvi to Queue
['Aniket', 'Abhijit', 'Awantika', 'Anvi']
Popped Aniket
['Abhijit', 'Awantika', 'Anvi']
Popped Abhijit
['Awantika', 'Anvi']

Add in the comments if you have any questions.