Stacks

I can neither confirm nor deny that when I was younger I was involved in an incident of breaking a stack of my mother’s treasured plates. Needless to say that the stack of plates will be replaced in due time. All because I wanted a purple plate. Speaking of stacks, a stack is a linear data structure that follows the principle of Last In First Out (LIFO). Meaning the item inserted last should be removed as the first. If I knew this back then, I would have removed the plates one by one instead of summoning the superman in me to lift all the plates.

Stack Operations

• push( 'i'): Adds items to the top of the stack, in this case, i
• pop(): Removes the top item from the stack
• empty(): Returns whether the stack is empty
• isFull: Returns if the stack is full
• peek: Gets the value of the top element without removing it
• size(): Returns the size of the stack
• top(): Returns a reference to the topmost element of the stack

Stack Implementation

Stacks in Python can be implemented in the following ways:

• Using a list
• Collections.deque
• Queue.LifoQueue
• Using singly linked list

Using a List

A list can be used as a stack, in that push() is replaced with append() to add elements to the top of the stack while pop() removes the elements in LIFO. One downside is that the list has speed issues as it grows, since it will require more memory.

#create stack
stack = []

#push elements to the stack
stack.append('p')
stack.append('y')
stack.append('t')
stack.append('h')
stack.append('o')
stack.append('n')

print('Initial stack')
print(stack)

#pop items from list
print('Popped items from list:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('Stack after popping elements:')
print(stack)

""" output
The stack
['p', 'y', 't', 'h', 'o', 'n']
Popped items from list:
n
o
h
t
Stack after popping elements:
['p', 'y']

"""

Collections.deque

Deque is a class from the collections module. It performs append and pop operations faster as compared to lists in a stack.

from collections import deque

#create a stack 
stack = deque()


#push elements to the stack
stack.append('p')
stack.append('y')
stack.append('t')
stack.append('h')
stack.append('o')
stack.append('n')

print('Initial stack')
print(stack)

#pop items from list
print('Popped items from list:')
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())

print('Stack after popping elements:')
print(stack)

"""
output
The stack

deque(['p', 'y', 't', 'h', 'o', 'n'])
Popped items from list:
n
o
h
t
Stack after popping elements:
deque(['p', 'y'])


"""

Using Queue Module

The queue module uses the LIFO Queue, which is a Stack. Data is inserted into the queue using the put() and get() takes data out from the queue.

Functions used in this module include:

• maxsize: Number of items allowed in the queue.
• empty(): Returns True if queue is empty else False
• full(): Return True if there are maxsize items in the queue.
• get(): Removes an item from the queue.
• get_nowait(): Return an item if one is immediately available, else raise QueueEmpty.
• put(item): Put an item into the queue. If the queue is full, wait for a free slot then add the item.
• put_nowait(item) – Put an item into the queue without blocking.
• qsize() – Return the number of items in the queue. If no free slot is immediately available, raise QueueFull.

from queue import LifoQueue

#create a stack 
stack = LifoQueue(maxsize=6)


#push elements to the stack
stack.put('p')
stack.put('y')
stack.put('t')
stack.put('h')
stack.put('o')
stack.put('n')

print('The stack')
print(stack.qsize())


#pop items from list
print('Popped items from list:')
print(stack.get())
print(stack.get())
print(stack.get())
print(stack.get())

print("Empty: ", stack.empty())

"""
output
The stack
6
Popped items from the list:
n
o
h
t

Empty:  False

"""

Using Singly Linked List

Linked lists are an ordered collection of objects. The difference between linked lists and normal lists is that lists use a contiguous memory block to store the references to their data while linked lists store references as part of their own elements.

Linked lists have a structure where each element identifies as a node. A node has different fields, data, and next. Data contains the value to be stored in the node while next contains a reference to the next node on the list.

A singly linked list is a type of linked list that is unidirectional. This means that traversing the list is done in only one direction. From the head to the last node, tail. The singly linked list has two main methods addHead(element) and removeHead(element). These two methods are used to implement a stack.

#create a node class
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class Stack:

    #initialize a stack, handle edge cases
    def __init__(self):
        self.head = Node("head")
        self.size = 0

    # String representation of stack
    def __str__(self):
        current = self.head.next
        nextVal = ""
        while current:
            nextVal += str(current.value) + "->"
            current = current.next
        return nextVal[:-3]

    # current size of the stack
    def getSize(self):
        return self.size

    # Check if  stack is empty
    def isEmpty(self):
        return self.size == 0

    # top item of the stack
    def peek(self):

        # check to see if we are peeking  in an empty stack.
        if self.isEmpty():
            raise Exception("Peeking from an empty stack")
        return self.head.next.value

    # Push a value to the stack.
    def push(self, value):
        node = Node(value)
        node.next = self.head.next
        self.head.next = node
        self.size += 1

    # Remove a value from the stack and return.
    def pop(self):
        if self.isEmpty():
            raise Exception("Popping from an empty stack")
        remove = self.head.next
        self.head.next = self.head.next.next
        self.size -= 1
        return remove.value


# Driver Code
if __name__ == "__main__":
    stack = Stack()
    for i in range(1, 11):
        stack.push(i)
    print(f"Stack: {stack}")

    for _ in range(1, 6):
        remove = stack.pop()
        print(f"Pop: {remove}")
    print(f"Stack: {stack}")

"""
output
Stack: 10->9->8->7->6->5->4->3->2->
Pop: 10
Pop: 9
Pop: 8
Pop: 7
Pop: 6
Stack: 5->4->3->2->
"""

Applications of Stacks

• Stacks are used to reverse words due to the LIFO principle.
• Compilers use stacks to calculate the value of expressions e.g 5 + 3 / 6 * (9 - 3) to prefix or postfix form.
• Forward and backward surfing in browsers.
• History of websites you have already visited.
• Message and phone logs where the person you communicated with last shows up first.
• Galleries, Emails, downloads, and notifications all use stacks.

Queues

Queue is a linear data structure that follows the First-In/First Out(FIFO) principle. The item inserted first will be removed first.

Queue Operations

• Enqueue: Adds an item to the end of the queue. If the queue is full it is said to be in overflow condition.
• Dequeue: Removes an item from the front of the queue. If the queue is empty then it is said to be an underflow condition.
• IsEmpty: Check if the queue is empty
• IsFull: Check if the queue is full
• Peek: Get the value of the front of the queue without removing it
• Front: Get the front item from the queue
• Rear: Get the last item from the queue

Queue Implementation

Queues can be implemented in Pyhton through the following ways:

• List
• Collections.deque
• queue.Queue

Using a List

Lists can be used to create queues so that instead of using enqueue() and dequeue(), you use append() and pop(). Lists are also slow for this use case because it will require shifting all elements one by one in order to insert or delete items.

# Initializing a queue
queue = []

# Adding elements to the queue
queue.append('P')
queue.append('Y')
queue.append('T')
queue.append('H')
queue.append('O')
queue.append('N')

print("Initial queue")
print(queue)

# Removing elements from the queue
print("Elements dequeued from queue ")
print(queue.pop(0))
print(queue.pop(0))
print(queue.pop(0))

print("Queue after removing elements")
print(queue)

'''
output 
Initial queue
['P', 'Y', 'T', 'H', 'O', 'N']

Elements dequeued from queue 
P
Y
T

Queue after removing elements
['H', 'O', 'N']
'''

Using Collections.deque

Queues can be implemented using dequeue from the collections module. Dequeue is preferred when we need to append and pop items faster from either end of the queue. For this implementation instead of using enqueue and dequeue we use append() and popleft().

from collections import deque

# Initializing a queue
q = deque()

# Adding elements 
q.append('P')
q.append('Y')
q.append('T')
q.append('H')
q.append('O')
q.append('N')

print("Initial queue")
print(q)

# Removing elements
print("Elements dequeued from the queue")
print(q.popleft())
print(q.popleft())
print(q.popleft())

print("Queue after removing elements")
print(q)

''' output
Initial queue
deque(['P', 'Y', 'T', 'H', 'O', 'N'])
Elements dequeued from the queue
P
Y
T
Queue after removing elements
deque(['H', 'O', 'N'])
'''

Using queue.Queue

Queue is a module of python used to implement a queue.

from queue import Queue

# Initializing a queue
q = Queue(maxsize = 6)

# qsize() give the maxsize of the Queue
print(q.qsize())

# Adding of element 
q.put('P')
q.put('Y')
q.put('T')
q.put('H')
q.put('O')
q.put('N')

# Return Boolean if Full
print("Full: ", q.full())

# Removing element 
print("Elements dequeued from the queue")
print(q.get())
print(q.get())
print(q.get())

# Return Boolean if Empty
print("Empty: ", q.empty())

#size of current queue
print("Size of Queue:",q.qsize())

'''output
0
Full:  True
Elements dequeued from the queue
P
Y
T
Empty:  False
Size of Queue: 3
'''

Applications of Queues

• CPU scheduling
• Customer service centers implement this while offering services
• For synchronization when data is being transferred between two processes asynchronously e.g pipes
• Interruption in real-life systems.
• Servers will tend to request using queues
• Sent emails are also queued until the recipient is able to receive them
• Networks handle congestion by using queues
• Internet requests and processes use queues

Difference Between Stacks and Queues

Bonus Content: Leetcode Question [232]

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

• void push(int x) Pushes element x to the back of the queue.
• int pop() Removes the element from the front of the queue and returns it.
• int peek() Returns the element at the front of the queue.
• boolean empty() Returns true if the queue is empty, false otherwise.

Notes:

You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

Follow-up: Can you implement the queue such that each operation is amortized O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

The amortized analysis gives the average performance (over time) of each operation in the worst case.

#O(1)
class MyQueue:
    #define both stacks
    def __init__(self):
        self.firstStack = [ ]
        self.secondStack = [ ]

    #add items to the 1st stack
    def push(self, x) -> None:
        self.firstStack.append(x)

    #remove items from the second stack
    def pop(self):
        self.peek()
        return self.secondStack.pop()

    #pop items of 1st stack and add to the second, return last item of second stack
    def peek(self):
        if not self.secondStack:
            while self.firstStack:
                self.secondStack.append(self.firstStack.pop())
        return self.secondStack[-1]
    #check if stack is empty
    def empty(self):
        return not self.firstStack and not self.secondStack

Thank you for reading this article. I hope that it has bestowed knowledge on stacks and queues and the application areas that we use on a daily basis.