Skip to content

Data Structures In Python – Stacks , Queues & Deques

DS2

Practically , when it comes to Python , we rarely talk about stacks , queues and deques. Although i’ve been using python for over 8+ years now , honestly i’m yet to use them in any of my real world projects !

Nevertheless , Let’s cover these data structures in detail and some visuals.

Distraction alert : You may love to understand how are arrays developed in python from scratch. Refer here for an amazing article.

1. Stacks In Detail

Ever used a back button in your browser ? Stacks work in similar fashion !
You open facebook.com followed by instagram.com followed by twitter. When we HIT back button , we would land in twitter followed by instagram followed by facebook.

In short, first IN last OUT

Okay , Now some strict technical definitions 😛

A stack is an ordered collection of elements where the addition of new element and the removal of existing always happens from the same end.

Checkout below , We get a clear picture.

stack
Credits : https://upload.wikimedia.org/wikipedia/commons/b/b4/Lifo_stack.png

Push & pop form 2 major operations , where push = insert & pop = remove.

Code below implements Stacks from scratch in python. 

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def push(self, item):
        self.items.append(item)

    def pop(self):
        return self.items.pop()

    def top(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

  • Stack() : creates a new empty stack.
  • push(item) : Adds new element to stack.
  • pop() : Removes top most element in the stack. This returns the pop element.
  • top() : Returns the top most element in the stack.
  • isEmpty() : Check if stack is empty.
  • size() : Returns the size of stack.


Lets check if this works !

s = Stack()

print (s.isEmpty())
: True

s.push(100)
s.push(200)

s.pop()
 : 200

s.size()
: 1

Thats works. Phew !

2. Queues In Detail

Have you every been to a theatre to buy a ticket ? If so , queues work same way.
Confused ?
Person in front of queue gets his chance to get his tickets first whereas one at the end of the queue will get an opportunity last.

In short , its first IN first OUT !

Okay , again some strict technical definitions 😛

A queue is an ordered collection of elements where the addition of new elements happens at one end and the removal of existing elements occurs at the other end. They are named front and rear respectively.

When an element is added to the queue it starts at the rear and makes its way toward the front. Checkout visuals below for a clear picture.

Queues
Credit : http://www.csit.parkland.edu/~mbrandyberry/CS2Java/Lessons/Stack_Queue/images/QueuePushPop.jpg


When we push 1 , it starts from the rear end. Next when we push 2 , 3 , the number 1 starts moving towards front end. This process is called enqueue.

Imagine we wanna remove an element , this happens as first come first serve. Hence 1 will be popped out first. This process is called dequeue.

Checkout below !

enqDeq
credits : https://netmatze.files.wordpress.com/2014/08/queue.png

Code below implements Queues from scratch in python.

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

  • Queue() : creates a new empty queue.
  • enqueue(item) : adds a new item to the rear of the queue.
  • dequeue() : removes the front item from the queue.
  • isEmpty() : Check if queue is empty.
  • size() : Returns the size of queue.

Lets run the code !

q = Queue()

q.enqueue(2)
q.enqueue(10)

q.dequeue()
: 2 

q.size()
: 1

Phew ! This worked too.

3. Deque In Detail

You have been waiting for a movie tickets in an indoor queue and it starts raining. All the folks outside would rush to shelter and join the queue either from the end or from the beginning , just to stop getting wet.

So , when the rain ends , they would exit from either the front of the queue or end of the queue.
Did that make sense ? Thats how deque works.

Entry/Exit from any end of the queue.


Deque is widely known as double ended queue.

Checkout below.

DeQ
deque


We could notice , there is push or pop options either from the front or the end. This overcomes limitations of queues giving in more flexibility,

Code below implements Deque from scratch in python.

class Deque:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self, item):
        self.items.insert(0,item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)
  • Deque() : creates a new empty deque.
  • addFront(item) : adds a new element to the front of the deque.
  • addRear(item) : adds a new item to the rear of the deque..
  • removeFront() : removes the front element from the deque.
  • removeRear() : removes the rear element from the deque.
  • isEmpty() : tests to see whether the deque is empty.
  • size() : returns the number of element in the deque.

4. Final Say

That was an easy way to understand stacks , queues and deque. Each of the data structures have their own implantations and we have covered in layman terms , how can we create all these data structures from scratch.

Make sure to read other amazing articles in the blog.

Thanks for reading !

You may not want to miss these exciting posts :

Tags: