Introduction

Stacks and Queues are widely used these days to solve a multitude of problems like evaluation of RPN expressions or checking if the parentheses in a string expression are balanced or not. Practically, we see use of stacks in a web browser’s back/forward functionality or undo/redo functionality seen today. Queues are used to implement caches and packet buffers in network routers to store packets in sequence in case of congestion.

As we see going further, these data structures are the basic building blocks used to implement advanced data structures like trees, graphs, tries etc.

What is a Stack?

A stack is a collection of memory spaces designed to store previous tasks in a Last In First Out (LIFO) order.

To better understand, we can assume a stack to be like a storage bin to store things, which is only open on one side. You can insert or remove items from only that side. Items inserted first, can only be removed at last.

A real-life example would be a pile of books placed in a vertical fashion. To get to a book in the middle, first we have to remove all books sitting on top of the book we want. This fashion of organizing things is called Last In First Out (LIFO) order.

Stack can be used to implement undo/redo functionality, webpage back/forward functionality, depth first search algorithm, evaluating Reverse Polish Notatiom (RPN) expressions (also called postfix expressions) etc.

A typical stack looks like this:

top -> | 45 |
       | 23 |
       | 86 |
       | 40 |

How does a stack work?

A stack must implement the following functionality:

Functionality	Description
push(data)	insert data on top of stack
pop()	fetch and remove thr element on top of stack
is_full()	return true if stack is at its capacity
is_empty()	return true if no element in stack
peek()	returns the value on top of stack, but does not remove it

Entire functionality of a stack is implemented using push(data) and pop() methods.

The following pictures show the transition:

From an empty stack to a full stack –> push(data)

 ---------          ---------          ----------         --------          --------
|         |        |         |        |          |       |        |        |        |
|         v        |         v        |          v       |        v        |        v
|       |    |     |       |    |     |       |    |     |      |    |     |      |    |
|       |    |     |       |    |     |       |    |     |      |    |     |      |    |
40      |    | --> |       |    | --> |       |    | --> |      |    | --> | top->| 45 |
86      |    |     86      |    |     |       |    |     | top->| 23 |     |      | 23 |
23      |    |     23      |    |     23 top->| 86 |     |      | 86 |     |      | 86 |
45 top->|    |     45 top->| 40 |     45      | 40 |     45     | 40 |     |      | 40 |

From a full stack to an empty stack –> pop()

         ------            ------            ------            ------           ------
        |      |          |      |          |      |          |      |         |      |
        |      |          |      |          |      |          |      |         |      |
     |    |    |       |    |    |       |    |    |       |    |    |      |    |    V
     |    |    |       |    |    |       |    |    |       |    |    V      |    |    
top->| 45 |    |  -->  |    |    |  -->  |    |    V  -->  |    |      -->  |    |    40
     | 23 |    V  top->| 23 |    V       |    |            |    |   86      |    |    86
     | 86 |            | 86 |       top->| 86 |    23      |    |   23      |    |    23
     | 40 |            | 40 |    45      | 40 |    45 top->| 40 |   45 top->|    |    45

When inserting an element into the stack, the variable that stores the position of the top element would be pointing to the number below it. So it needs to be updated to the new element every time we insert a value. Similarly, it will need to updated when removing an element from the stack.

It’s a good practice to update the value of the top variable before inserting or removing an element, so that it always points to the correct value.

Stack Implementation

Modern languages like Python or Java already have a stack implementation inbuilt, but we can implement it ourselves to extend its functionaloty for our use.

Stacks can be implemented using linked lists and arrays. Performance wise, it is not yet concluded which implementation is better. Array implementation is better because it takes less space and we don’t need to store additional pointers for linked lists.

We need an array to store the elements, a variable to store its max capacity and a variable to store the top index.

We instantiate a stack instance by creating an array of size max_capacity and setting top index to -1.
For push(data), we increment the top index and insert data to array[top].
For pop(), we return the value from array[top] and decrement the top index.
For is_empty(), we check if the value to top index is -1?
For is_full(), we check it the top index is max_capacity - 1?
For peek() (or top()), we simply return the current value at array[top] without removing the element.

NOTES:

suppress_printing flag is to simply avoid printing the element value to console every time it is pushed or popped from the stack.
prettify() returns a string representation of the stack.
print_stack() prints the string representation of the stack, as returned by prettify().

class Stack:
    def __init__(self, capacity=None, suppress_printing=False):
        self.suppress_printing = suppress_printing
        self.capacity = capacity
        self.top = -1
        self.elements = [None] * self.capacity

    def is_empty(self):
        if self.top is -1:
            return True
        return False

    def is_full(self):
        if self.top is (self.capacity - 1):
            return True
        return False

    def peek(self):
        if self.is_empty():
            print("nothing to show, stack empty...")
            return None

        return self.elements[self.top]

    def push(self, data):
        if self.is_full():
            print("can't push anymore, stack full...")
            return None

        self.top += 1
        self.elements[self.top] = data
        if not self.suppress_printing: print("pushed data = " + str(data))

    def pop(self):
        if self.is_empty():
            print("can't pop, stack empty...")
            return None

        result = self.elements[self.top]
        self.elements[self.top] = None
        self.top -= 1

        if not self.suppress_printing: print("popped data = " + str(result))
        return result

    def print_stack(self):
        pretty_list = self.prettify()
        print(pretty_list)

    def prettify(self):
        printer = ""
        for i in range(len(self.elements))[::-1]:
            printer += (str(i) + " -> " + "[ " + str(self.elements[i]) + " ]")
            if i is not 0: printer += "\n"
        return printer

Validating Stack Implementation

import educative.course1.stacks_queues.stack as stack


def main():
    print("Stack initialized with capacity = 5")
    example = stack.Stack(5)

    print("------")
    print("pushing to stack...")
    example.push(5)
    example.push(6)
    example.push(7)
    example.push(8)
    example.push(9)
    example.push(2)
    example.push(7)

    print()
    example.print_stack()

    print("------")
    print("peeking at the top...")
    print(example.peek())

    print("------")
    print("popping from stack..")
    example.pop()
    example.pop()

    print()
    example.print_stack()

    print("------")
    print("peeking at the top...")
    print(example.peek())

    print("------")
    print("popping from stack..")
    example.pop()
    example.pop()
    example.pop()
    example.pop()
    example.pop()

    print()
    example.print_stack()

    print("------")
    print("peeking at the top...")
    print(example.peek())

    print("------")
    print("pushing to stack...")
    example.push(21)
    example.push(22)

    print()
    example.print_stack()

    print("------")
    print("peeking at the top...")
    print(example.peek())


if __name__ == '__main__':
    main()

Output

Stack initialized with capacity = 5
 -----
pushing to stack...
pushed data = 5
pushed data = 6
pushed data = 7
pushed data = 8
pushed data = 9
can’t push anymore, stack full...
can’t push anymore, stack full...

4 -> [ 9 ]
3 -> [ 8 ]
2 -> [ 7 ]
1 -> [ 6 ]
0 -> [ 5 ]
 -----
peeking at the top...
9
 -----
popping from stack..
popped data = 9
popped data = 8

4 -> [ None ]
3 -> [ None ]
2 -> [ 7 ]
1 -> [ 6 ]
0 -> [ 5 ]
 -----
peeking at the top...
7
 -----
popping from stack..
popped data = 7
popped data = 6
popped data = 5
can’t pop, stack empty...
can’t pop, stack empty...

4 -> [ None ]
3 -> [ None ]
2 -> [ None ]
1 -> [ None ]
0 -> [ None ]
 ------
peeking at the top...
nothing to show, stack empty...
None
 -----
pushing to stack...
pushed data = 21
pushed data = 22

4 -> [ None ]
3 -> [ None ]
2 -> [ None ]
1 -> [ 22 ]
0 -> [ 21 ]
 -----
peeking at the top...
22

What is a Queue?

A queue is also a linear data structure like stack. It stores data elements sequentially in a First In First Out (FIFO) order.

To better understand, a queue can be visualized as a pipe which is open from both ends. Elements enter from the “back” and exit from the “front”. Elements entered first, will leave first.

A real life example would be a line of people waiting to be served at a booth. If a new person comes, he joins the queue at the beack and when the person in front is served, they will exit the queue from the front.

Queues can be used to implement a cache, or a packet buffer in a network router which will store packets in order in case of network congestion. Generally, queues are used in scenarios where we want to prioritize something over another, or when a resource (like compute cycle time or memory) is shared among multiple tasks.

A typical Queue looks like this:

Front       Back
  |         |
[ 11 24 77 45 ]

How does a Queue work?

A queue needs to implement the following functionality:

Functionality	Description
enqueue(data)	insert data at the end of queue
dequeue()	fetch and remove the element on front of queue
is_full()	return true if queue is at its capacity
is_empty()	return true if no element in queue
peek()	returns the value on front of queue, but does not remove it

Entire functionality of a queue is implemented using enqueue(data) and dequeue() methods.

The following pictures show the transition:

From an empty queue to a full queue –> enqueue(data)

         45                                                           
         77        45                                                  
         24        77          45                                       
         11        24          77                45                  None
        /         /            /                 /                    /
    FB /      FB /       F  B /        F      B /        F         B /
     |/   -->  |/   -->  |  |/    -->  |      |/   -->   |         |/
   [   ]     [ 11 ]    [ 11 24 ]     [ 11 24 77 ]      [ 11 24 77 45 ]

From a full queue to an empty queue –> dequeue()

       F         B         F      B          F   B           FB          FB
       |         |   -->   |      |   -->    |   |    -->    |    -->    |
     [ 11 24 77 45 ]     [ 24 77 45 ]      [ 77 45 ]       [ 45 ]      [   ]
      /                   /                 /               /           /     
     /                   /                 /               /           /
  None                  11                24              77          45
                                          11              24          77
                                                          11          24
                                                                      11

Types of Queues

There 2 common types of queues which cover a wide range of problems:

Linear Queues
Circular Queues
Priority Queues

Linear Queues:

The Queue discussed above is a Linear queue.

Circular Queues:

A Circular queue is circular in structure, meaning both ends are connected to form a circle. Initially, “front” and “back” point to the same node and eventually move apart as new elements are added.

Generally, circular queues are used to simulate objects and to implement event handling.

This is how it looks like:

             F
       ________|________
      / \      22     / \
     /   \___________/   \
    /    /           \ 45 \
   / __ /             \ __ \
   |    |             |    |
   |    |      8      | 11 |       This is a circular queue of size 8.
   | __ |             | __ |   --> Elements are enqueued at back and dequeued from front.
   \    \             /    /       Structurally, front and back are connected like shown.
    \ 42 \___________/ 53 /
    /\  /      43     \  /
   B  \/_______________\/

Priority Queues:

A Priority queue keeps its elements sorted at a given time based on a specific order. Most prioritzed element stays at the front of the queue and the least stays at the back.

Priority Queues are used in an Operating System to determine which programs take priority over others.

Queue Implementation (Linear Queue)

Queues can be implemened using an array, linked list or a stack. Array implementation is the easiest and is discussed below.

We need an array to store the elements, a variable to store its max capacity and a variable to store its current size.

We instantiate a queue instance by declaring an array to store elements, setting the current_size = 0 and setting the max_capacity to a variable.
For enqueue(data), we simply append the data to the elements array and update the current_size = len(elements array).
For dequeue(), we return and delete the value from array[0] update and the current_size = len(elements array).
For is_empty(), we check if current_size = 0?
For is_full(), we check is current_size = max_capacity?
For peek() (or top()), we simply return the current value at array[0] without removing the element.

NOTES:

suppress_printing flag is to simply avoid printing the element value to console every time it is enqueued or dequeued from the queue.
prettify() returns a string representation of the queue.
print_queue() prints the string representation of the queue, as returned by prettify().

class Queue:
    def __init__(self, capacity=None, suppress_printing=False):
        self.suppress_printing = suppress_printing
        self.capacity = capacity
        self.elements = []
        self.current_size = 0

    def is_empty(self):
        if self.current_size is 0:
            return True
        return False

    def is_full(self):
        if self.current_size is self.capacity:
            return True
        return False

    def peek(self):
        if self.is_empty():
            print("nothing to show, queue empty...")
            return None

        return str(self.elements[0])

    def enqueue(self, data):
        if self.is_full():
            print("can't enqueue anymore, queue full...")
            return None

        self.elements.append(data)
        self.current_size = len(self.elements)
        if not self.suppress_printing: print("enqueued data = " + str(data))

    def dequeue(self):
        if self.is_empty():
            print("can't dequeue, queue empty...")
            return None

        result = self.elements.pop(0)
        self.current_size = len(self.elements)
        if not self.suppress_printing: print("dequeued data = " + str(result))

        return result

    def print_queue(self):
        pretty_queue = self.prettify()
        print(pretty_queue)

    def prettify(self):
        printer = "Queue -> F [ "
        for x in self.elements:
            printer += str(x) + " "
        printer += "] B"

        return printer

Validating Queue Implementation

import educative.course1.stacks_queues.queue as queue


def main():
    print("Queue initialized with capacity = 5")
    example = queue.Queue(5)

    print("------")
    print("enqueuing in queue...")
    example.enqueue(5)
    example.enqueue(6)
    example.enqueue(7)
    example.enqueue(8)
    example.enqueue(9)
    example.enqueue(2)
    example.enqueue(7)

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())

    print("------")
    print("dequeuing from queue...")
    example.dequeue()
    example.dequeue()

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())

    print("------")
    print("dequeuing from queue...")
    example.dequeue()
    example.dequeue()
    example.dequeue()
    example.dequeue()
    example.dequeue()

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())

    print("------")
    print("enqueuing in queue...")
    example.enqueue(21)
    example.enqueue(22)

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())


if __name__ == '__main__':
    main()

Output

Queue initialized with capacity = 5
 ------
enqueuing in queue...
enqueued data = 5
enqueued data = 6
enqueued data = 7
enqueued data = 8
enqueued data = 9
can’t enqueue anymore, queue full...
can’t enqueue anymore, queue full...

Queue -> F [ 5 6 7 8 9 ] B
 ------
peeking...
5
 ------
dequeuing from queue...
dequeued data = 5
dequeued data = 6

Queue -> F [ 7 8 9 ] B
 ------
peeking...
7
 ------
dequeuing from queue...
dequeued data = 7
dequeued data = 8
dequeued data = 9
can’t dequeue, queue empty...
can’t dequeue, queue empty...

Queue -> F [ ] B
 ------
peeking...
nothing to show, queue empty...
None
 ------
enqueuing in queue...
enqueued data = 21
enqueued data = 22

Queue -> F [ 21 22 ] B
 ------
peeking...
21

Challenges

Challenges 1 - 10

Challenge 1: Generate Binary Numbers from 1 to n using a Queue

Steps:

Initialize a queue with capacity n + 1 -> for every dequeue, we enqueue 2 times.
Insert 1 in queue.
temp = dequeue() -> temp = 1.
- append temp in “result” array.
- append 0 to temp => 10
- append 1 to temp => 11
Enqueue 10 and 11 in queue.
Repeat 2. and 3. until n.
“result” array now contains binary numbers until n.

import educative.course1.stacks_queues.queue as q

input_data = 3
expected_output_data = [1, 10, 11]


def generate_binary_numbers(target_number):
    result = []
    n = target_number

    # initialize queue with capacity  n + 1, because
    # we are enqueueing 2 values for each dequeue()
    queue = q.Queue(n + 1, True) # suppress_printing = True

    # initialize queue with first value to start the conversion
    queue.enqueue(1)

    # for each entry:
    # 1. dequeue from the queue and add to result array
    # 2. append 0 and enqueue it back
    # 3. append 1 and enqueue it back
    # this process enqueues binary form of each entry to the result array
    for i in range(n):
        temp = queue.dequeue()
        result.append(temp)
        queue.enqueue(int(str(temp) + "0"))
        queue.enqueue(int(str(temp) + "1"))

    return result


def main():
    print("Input: " + str(input_data))
    print("Expected: " + str(expected_output_data))
    print("Output: " + str(generate_binary_numbers(input_data)))


if __name__ == '__main__':
    main()

Output

Input: 3
Expected: [1, 10, 11]
Output: [1, 10, 11]

Time Complexity: O(n)

Challenge 2: Implement Two Stacks using one Array

Using Stacks on opposite ends:

This implementation uses space in an efficient way.
max_capacity defines the number of total elements both stacks can accomodate at a given time.\
At initialization:
- top index of stack 1 is set to the 0th index - 1 (or -1)
- top index of stack 2 is set to the last index + 1 (or max_capacity).
Both stacks grown or shrink in opposity directions.
We keep track of overflow by checking the gap in top indices of both stacks.

Implementation:

set max_capacity from input, initialize an elements array of size max_capacity, set top1 = -1, set top2 = max_capacity
is_full() returns true if abs(top2 - top 1) = 1, meaning top1 and top2 are next to each other.
is_empty() returns true if top1 = -1 and top2 = max_capacity.
push1(data):
- checks if top1 < top2 - 1 (to ensure there is a 1 unit gap between top1 and top2)
- increments top1 by 1
- inserts data at elements array[top1]
push2(data):
- checks if top2 > top1 + 1 (to ensure there is a 1 unit gap between top1 and top2)
- decrements top2 by 1
- inserts data at elements array[top2]
pop1():
- checks if top1 > -1 (to ensure stack1 is not empty. is_full() will not work as array may be full by stack2 elements)
- set result = elements array[top1]
- set elements array[top1] = None
- decrement top1
- return result
pop2():
- checks if top2 < max_capacity (to ensure stack2 is not empty. is_full() will not work as array may be full by stack1 elements)
- set result = elements array[top2]
- set elements array[top2] = None
- increment top1
- return result
peek1() and peek2() return elements at array[top1] and array[top2] respectively.

NOTES:

suppress_printing flag is to simply avoid printing the element values to console every time they are pushed or popped from the 2 stacks.
prettify() returns a string representation of the 2 stacks.
print_stack() prints the string representation of the 2 stacks, as returned by prettify().

class TwoStacks():
    def __init__(self, capacity=None, suppress_printing=False):
        self.suppress_printing = suppress_printing
        self.capacity = capacity
        self.elements = [None] * self.capacity
        self.top1 = -1
        self.top2 = self.capacity

    def is_full(self):
        if abs(self.top1 - self.top2) is 1:
            return True
        return False

    def is_empty(self):
        if self.top1 is -1 and self.top2 is self.capacity:
            return True
        return False

    def push1(self, data):
        if self.is_full():
            print("can't push anymore, stack full...")
            return None

        if self.top1 < self.top2 - 1:
            self.top1 += 1
            self.elements[self.top1] = data
            if not self.suppress_printing: print("stack1 - pushed data = " + str(data))
        return None

    def push2(self, data):
        if self.is_full():
            print("can't push anymore, stack full...")
            return None

        if self.top2 > self.top1 + 1:
            self.top2 -= 1
            self.elements[self.top2] = data
            if not self.suppress_printing: print("stack2 - pushed data = " + str(data))
        return None

    def pop1(self):
        if self.is_empty():
            print("can't pop, stack empty...")
            return None

        if self.top1 > -1:
            result = self.elements[self.top1]
            self.elements[self.top1] = None
            self.top1 -= 1
            if not self.suppress_printing: print("stack1 - popped data = " + str(result))
            return result
        return None

    def pop2(self):
        if self.is_empty():
            print("can't pop, stack empty...")
            return None

        if self.top2 < self.capacity:
            result = self.elements[self.top2]
            self.elements[self.top2] = None
            self.top2 += 1
            if not self.suppress_printing: print("stack2 - popped data = " + str(result))
            return result
        return None

    def peek1(self):
        if self.top1 is -1:
            return None
        return str(self.elements[self.top1])

    def peek2(self):
        if self.top2 is self.capacity:
            return None
        return str(self.elements[self.top2])

    def print_stack(self):
        pretty_list = self.prettify()
        print(pretty_list)

        return None

    def prettify(self):
        printer = ""
        for i in range(self.capacity):
            printer += str(i) + " -> [  " + str(self.elements[i]) + "  ]"
            if i is not self.capacity: printer += "\n"

        return printer

Validating Two Stacks

import educative.course1.stacks_queues.ch2_two_stacks as two_stacks


def main():
    print("Stack initialized with capacity = 5")
    example = two_stacks.TwoStacks(5, True) # suppress_printing = True

    print("------")
    print("pushing to stack 1...")
    example.push1(5)
    example.push1(6)
    example.push1(7)
    print("pushing to stack 2...")
    example.push2(8)
    example.push2(9)
    example.push2(2)
    example.push2(7)

    print()
    print("peeking from stack 1...")
    print(example.peek1())

    print()
    print("peeking from stack 2...")
    print(example.peek2())

    print()
    example.print_stack()

    print("------")
    print("popping from stack 1..")
    example.pop1()
    print("popping from stack 2..")
    example.pop2()

    print()
    print("peeking from stack 1...")
    print(example.peek1())

    print()
    print("peeking from stack 2...")
    print(example.peek2())

    print()
    example.print_stack()

    print("------")
    print("popping from stack 1..")
    example.pop1()
    example.pop1()
    print("popping from stack 2..")
    example.pop2()
    example.pop2()
    example.pop2()

    print()
    print("peeking from stack 1...")
    print(example.peek1())

    print()
    print("peeking from stack 2...")
    print(example.peek2())

    print()
    example.print_stack()

    print("------")
    print("pushing to stack 2...")
    example.push2(21)
    example.push2(22)
    example.push2(23)

    print()
    print("peeking from stack 1...")
    print(example.peek1())

    print()
    print("peeking from stack 2...")
    print(example.peek2())

    print()
    example.print_stack()


if __name__ == '__main__':
    main()

Output

Stack initialized with capacity = 5
 ------
pushing to stack 1...
pushing to stack 2...
can’t push anymore, stack full...
can’t push anymore, stack full...

peeking from stack 1...
7

peeking from stack 2...
9

0 -> [  5  ]
1 -> [  6  ]
2 -> [  7  ] <-- top1
3 -> [  9  ] <-- top2
4 -> [  8  ]

------
popping from stack 1..
popping from stack 2..

peeking from stack 1...
6

peeking from stack 2...
8

0 -> [  5  ]
1 -> [  6  ] <-- top1
2 -> [  None  ]
3 -> [  None  ]
4 -> [  8  ] <-- top2

------
popping from stack 1..
popping from stack 2..
can’t pop, stack empty...
can’t pop, stack empty...

peeking from stack 1...
None

peeking from stack 2...
None

0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  None  ]
4 -> [  None  ]

------
pushing to stack 2...

peeking from stack 1...
None

peeking from stack 2...
23

0 -> [  None  ]
1 -> [  None  ]
2 -> [  23  ] <-- top2
3 -> [  22  ]
4 -> [  21  ]

Time Complexity: O(n)

Challenge 3: Reversing First k Elements of a Queue

Using a stack to reverse elements:

Since we are reversing k elements, initialize a stack with k capacity to hold k elements
This algorithm consists of 3 steps:
- dequeue k elements from queue and push to stack
- pop() elements from stack and enqueue in queue (in reverse order)
- now dequeue elements from the front and enqueue again at the back
resulting array will contain first k elements in reverse order

Here is an illustration:

Reverse k=3 elements:

F [ 1 5 8 3 9 ] B  --->  F [ 3 9 ] B  --->  F [ 3 9 8 5 1 ] B  --->  F [ 8 5 1 3 9 ] B

                            [ 8 ]                 [   ]              (first k reversed)
             Stack(k=3)->   [ 5 ]                 [   ]
                            [ 1 ]                 [   ]

import educative.course1.stacks_queues.queue as q
import educative.course1.stacks_queues.stack as s

input_data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
input_k = 5
expected_output_data = [5, 4, 3, 2, 1, 6, 7, 8, 9, 10]


def reverse_k_elements(queue, k):
    temp_stack = s.Stack(k, True) # suppress_printing = True

    for i in range(k):
        temp_stack.push(queue.dequeue())

    for i in range(k):
        queue.enqueue(temp_stack.pop())

    for i in range(queue.capacity - k):
        queue.enqueue(queue.dequeue())

    return queue.prettify()


def main():
    input_queue = q.Queue(len(input_data), True) # suppress_printing = True
    [input_queue.enqueue(x) for x in input_data]

    expected_output_queue = q.Queue(len(expected_output_data), True) # suppress_printing
    [expected_output_queue.enqueue(x) for x in expected_output_data]

    print("Input: " + str(input_queue.prettify()))
    print("Expected: " + str(expected_output_queue.prettify()))
    print("Output: " + str(reverse_k_elements(input_queue, input_k)))


if __name__ == '__main__':
    main()

Output

Input: Queue -> F [ 1 2 3 4 5 6 7 8 9 10 ] B
Expected: Queue -> F [ 5 4 3 2 1 6 7 8 9 10 ] B
Output: Queue -> F [ 5 4 3 2 1 6 7 8 9 10 ] B

Time Complexity: O(n)

Challenge 4: Implement a Queue using Stack

Solution 1: Using 2 Stacks (Optimizing only dequeue() operation)

Implementation uses 2 stacks, one for storing the queue elements and 2nd as a buffer to be used at the time of dequeue.

enqueue(data) simply pushes the data on top of stack 1
dequeue():
- checks if stack 1 is empty and returns False if no elements
- stack 1 is emptied into stack 2
- This operation brings the first value in the queue to the top of stack 2
- Now it is popped and saved for returning to the caller
- Finally stack 2 is emptied back into stack 1 and the queue returns to normal.
- result is returned to the caller
peek() follows the same logic as dequeue(), but instead of popping top of stack2, we simply peek() top of stack2 before emptying stack2 into stack1.

NOTES:

suppress_printing flag is to simply avoid printing the element values to console every time they are pushed or popped from the 2 stacks or enqueued/dequeued from the queue
prettify() returns a string representation of the queue.
print_queue() prints the string representation of the queue, as returned by prettify().

import educative.course1.stacks_queues.stack as s


class QueueUsingStacks_1:
    def __init__(self, capacity=None, suppress_printing=False):
        self.suppress_printing = suppress_printing
        self.capacity = capacity
        self.stack1 = s.Stack(self.capacity, suppress_printing)
        self.stack2 = s.Stack(self.capacity, suppress_printing)

    def is_empty(self):
        if self.stack1.is_empty():
            return True
        return False

    def is_full(self):
        if self.stack1.is_full():
            return True
        return False

    def peek(self):
        if self.is_empty():
            print("nothing to show, queue empty...")
            return None

        while not self.stack1.is_empty():
            self.stack2.push(self.stack1.pop())

        result = self.stack2.peek()

        while not self.stack2.is_empty():
            self.stack1.push(self.stack2.pop())

        return result

    def enqueue(self, data):
        if self.is_full():
            print("can't enqueue anymore, queue full...")
            return False

        self.stack1.push(data)
        if not self.suppress_printing: print("enqueued data = " + str(data))

        return True

    def dequeue(self):
        if self.is_empty():
            print("can't dequeue, queue empty...")
            return None

        while not self.stack1.is_empty():
            self.stack2.push(self.stack1.pop())

        result = self.stack2.pop()

        while not self.stack2.is_empty():
            self.stack1.push(self.stack2.pop())

        if not self.suppress_printing: print("dequeued data = " + str(result))
        return result

    def print_queue(self):
        pretty_queue = self.prettify()
        print(pretty_queue)

    def prettify(self):
        printer = "Queue -> F [ "
        for x in self.stack1.elements:
            printer += str(x) + " "
        printer += "] B"

        return printer

Validating Solution 1: “Queue using Stack” Implementation

import educative.course1.stacks_queues.ch4_queue_using_stacks_1 as queue


def main():
    print("Queue initialized with capacity = 5")
    example = queue.QueueUsingStacks_1(5, True) # suppress_printing = True

    print("------")
    print("enqueuing in queue...")
    example.enqueue(5)
    example.enqueue(6)
    example.enqueue(7)
    example.enqueue(8)
    example.enqueue(9)
    example.enqueue(2)
    example.enqueue(7)

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())

    print("------")
    print("dequeuing from queue...")
    example.dequeue()
    example.dequeue()

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())

    print("------")
    print("dequeuing from queue...")
    example.dequeue()
    example.dequeue()
    example.dequeue()
    example.dequeue()
    example.dequeue()

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())

    print("------")
    print("enqueuing in queue...")
    example.enqueue(21)
    example.enqueue(22)

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())


if __name__ == '__main__':
    main()

Output

Queue initialized with capacity = 5
 ------
enqueuing in queue...
can’t enqueue anymore, queue full...
can’t enqueue anymore, queue full...

Queue -> F [ 5 6 7 8 9 ] B
 ------
peeking...
5
 ------
dequeuing from queue...

Queue -> F [ 7 8 9 None None ] B
 ------
peeking...
7
 ------
dequeuing from queue...
can’t dequeue, queue empty...
can’t dequeue, queue empty...

Queue -> F [ None None None None None ] B
 ------
peeking...
nothing to show, queue empty...
None
 ------
enqueuing in queue...

Queue -> F [ 21 22 None None None ] B
 ------
peeking...
21

Time Complexity - enqueue(data) = O(1), dequeue() = O(n)

Solution 2: Using 2 Stacks (Optimizing enqueue() and dequeue() operations)

Implementation uses 2 stacks, one for storing the queue elements and 2nd as a buffer to be used at the time of dequeue

enqueue(data) simply pushes the data on top of stack 1
dequeue()
- checks if stack 1 and stack 2 are empty and returns False if no elements
- IF stack 2 is empty, stack 1 is emptied into stack 2
- This operation reverses the order of stored elements and the top element in stack 2 represents the front of the queue
- Elements in stack 2 can be popped for dequeuing until it goes empty.
- and IF stack2 is NOT emptied yet, it still contains the front element in the queue.
- Finally, result is popped off of stack 2 and returned to the caller
peek() follows the same logic as dequeue(), but instead of popping top of stack2, we simply peek() top of stack2 before emptying stack2 into stack1.

NOTES:

suppress_printing flag is to simply avoid printing the element values to console every time they are pushed or popped from the 2 stacks or enqueued/dequeued from the queue
prettify() returns a string representation of the queue.
print_queue() prints the string representation of the queue, as returned by prettify().

import educative.course1.stacks_queues.stack as s


class QueueUsingStacks_2:
    def __init__(self, capacity=None, suppress_printing=False):
        self.suppress_printing = suppress_printing
        self.capacity = capacity
        self.stack1 = s.Stack(self.capacity, suppress_printing)
        self.stack2 = s.Stack(self.capacity, suppress_printing)

    def is_empty(self):
        if self.stack1.is_empty() and self.stack2.is_empty():
            return True
        return False

    def is_full(self):
        if self.stack1.is_full() or self.stack2.is_full():
            return True
        return False

    def peek(self):
        if self.is_empty():
            print("nothing to show, queue empty...")
            return None
        elif self.stack2.is_empty():
            while not self.stack1.is_empty():
                self.stack2.push(self.stack1.pop())

            result = self.stack2.peek()
        else:
            result = self.stack2.peek()

        return result

    def enqueue(self, data):
        if self.is_full():
            print("can't enqueue anymore, queue full...")
            return False

        self.stack1.push(data)
        if not self.suppress_printing: print("enqueued data = " + str(data))

        return True

    def dequeue(self):
        if self.is_empty():
            print("can't dequeue, queue empty...")
            return None
        elif self.stack2.is_empty():
            while not self.stack1.is_empty():
                self.stack2.push(self.stack1.pop())

            result = self.stack2.pop()
        else:
            result = self.stack2.pop()

        if not self.suppress_printing: print("dequeued data = " + str(result))
        return result

    def print_queue(self):
        pretty_queue = self.prettify()
        print(pretty_queue)

    def prettify(self):
        printer = "Queue -> F [ "
        for x in self.stack1.elements:
            printer += str(x) + " "
        printer += "] B"

        return printer

Validating Solution 2: “Queue using Stack” Implementation

import educative.course1.stacks_queues.ch4_queue_using_stacks_2 as queue


def main():
    print("Queue initialized with capacity = 5")
    example = queue.QueueUsingStacks_2(5, True) # suppress_printing = True

    print("------")
    print("enqueuing in queue...")
    example.enqueue(5)
    example.enqueue(6)
    example.enqueue(7)
    example.enqueue(8)
    example.enqueue(9)
    example.enqueue(2)
    example.enqueue(7)

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())

    print("------")
    print("dequeuing from queue...")
    example.dequeue()
    example.dequeue()

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())

    print("------")
    print("dequeuing from queue...")
    example.dequeue()
    example.dequeue()
    example.dequeue()
    example.dequeue()
    example.dequeue()

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())

    print("------")
    print("enqueuing in queue...")
    example.enqueue(21)
    example.enqueue(22)

    print()
    example.print_queue()

    print("------")
    print("peeking...")
    print(example.peek())


if __name__ == '__main__':
    main()

Output

Queue initialized with capacity = 5
 ------
enqueuing in queue...
can’t enqueue anymore, queue full...
can’t enqueue anymore, queue full...

Queue -> F [ 5 6 7 8 9 ] B
 ------
peeking...
5
 ------
dequeuing from queue...

Queue -> F [ None None None None None ] B
 ------
peeking...
7
 ------
dequeuing from queue...
can’t dequeue, queue empty...
can’t dequeue, queue empty...

Queue -> F [ None None None None None ] B
 ------
peeking...
nothing to show, queue empty...
None
 ------
enqueuing in queue...

Queue -> F [ 21 22 None None None ] B
 ------
peeking...
21

Time Complexity - enqueue(data) = O(1), dequeue() < O(n) –> amortized = O(n), because worst-case = O(n)

Challenge 5: Sort the Values in a Stack

This solution uses a second stack to hold resulting sorted stack. (See online video if confusing)

Until input stack is not empty, we pop the top value and compare it with the top value of the second stack
- if value > top of stack 2, we insert the popped value in stack 2
- else:
  - while popped value < top of stack 2, we keep pushing top of stack 2 to stack 1
Finally when stack 2 is empty we push the popped value and start over again
The output will be a sorted stack

NOTE - This can also be done by recursion

import educative.course1.stacks_queues.stack as s

input_data = [23, 60, 12, 42, 4, 97, 2]
expected_output_data = [2, 4, 12, 23, 42, 60, 97]


def sort_stack_1(stack):
    result = s.Stack(stack.capacity, True) # suppress_printing = True

    while not stack.is_empty():
        value = stack.pop()
        if not result.is_empty() and value >= int(result.peek()):
            result.push(value)
        else:
            while not result.is_empty() and value < int(result.peek()):
                stack.push(result.pop())

            result.push(value)

    return result.prettify()


def main():
    input_stack = s.Stack(len(input_data), True) # suppress_printing = True
    [input_stack.push(x) for x in input_data]

    expected_output_stack = s.Stack(len(expected_output_data), True) # suppress_printing
    [expected_output_stack.push(x) for x in expected_output_data]

    print("Input: \n" + str(input_stack.prettify()))
    print("Expected: \n" + str(expected_output_stack.prettify()))
    print("Output: \n" + str(sort_stack_1(input_stack)))


if __name__ == '__main__':
    main()

Output

Input:
6 -> [ 2 ]
5 -> [ 97 ]
4 -> [ 4 ]
3 -> [ 42 ]
2 -> [ 12 ]
1 -> [ 60 ]
0 -> [ 23 ]
Expected:
6 -> [ 97 ]
5 -> [ 60 ]
4 -> [ 42 ]
3 -> [ 23 ]
2 -> [ 12 ]
1 -> [ 4 ]
0 -> [ 2 ]
Output:
6 -> [ 97 ]
5 -> [ 60 ]
4 -> [ 42 ]
3 -> [ 23 ]
2 -> [ 12 ]
1 -> [ 4 ]
0 -> [ 2 ]

Time Complexity = O(n^2) –> Inner and Outer loops traverse all n elements

Challenge 6: Evaluate PostFix Epressions using Stacks (RPN)

PostFix or RPN notations have the operator between two numbers written after the concerned numbers as an epxression (like 912+-4+2* = 20)

So stacks are perfect to evaluate such strings:

Traverse the expression character by character.
If character is numerical, push the character to a temp_stack.
If character is an operator, pop last 2 characters from stack and perform the arithmetic operatio and push the result back to the stack.
After the expression is traversed, the temp_stack will contain the result of given expression.

import educative.course1.stacks_queues.stack as s

input_data = "921*-8-4+"
expected_output_data = 3


def evaluate_postfix_rpn(expression_string):
    expression = list(expression_string)
    temp_stack = s.Stack(len(expression), True) # suppress_printing = True
    valid_input = ["+", "-", "/", "*"]

    for c in expression:
        if c not in valid_input and not c.isdigit():
            return "Expression is invalid!"

        if c is "+":
            x = int(temp_stack.pop())
            y = int(temp_stack.pop())
            temp_stack.push(y + x)
        elif c is "-":
            x = int(temp_stack.pop())
            y = int(temp_stack.pop())
            temp_stack.push(y - x)
        elif c is "*":
            x = int(temp_stack.pop())
            y = int(temp_stack.pop())
            temp_stack.push(y * x)
        elif c is "/":
            x = int(temp_stack.pop())
            y = int(temp_stack.pop())
            temp_stack.push(y//x)
        else:
            temp_stack.push(c)

    result = temp_stack.pop()

    return result


def main():
    print("Input: " + str(input_data))
    print("Expected: " + str(expected_output_data))
    print("Output: " + str(evaluate_postfix_rpn(input_data)))


if __name__ == '__main__':
    main()

Output

Input: 921*-8-4+
Expected: 3
Output: 3

Time Complexity = O(n)

Challenge 7: Next Greater Element using Stack

The most optimal solution is to use a stack for storing elements yet to be processed. The key is to order the stack in ascending order until the next element under comparison is bigger than the top element on the stack.

Steps:

For each element in input, check:
- if stack is empty, push the element to stack as stack is empty and move to the next iteration
- if stack does have a node, check:
  - if current element is smaller than top of the stack, push element on top of stack
  - else:
    - iterate the stack popping all elements one by one
    - appending current element to the result array for each pop
- finally after all nodes in stack are popped, push the current element on top of the stack for next iteration
Now that all array elements are processed, we are left with a stack of nodes which don’t have the next greater element.
pop() the elements one by one and append -1 to the result array for each popped element.
Resulting array will now contain -1 for each element which does not have a NGE.
Return the result array

import educative.course1.stacks_queues.stack as s

input_data = [4, 6, 3, 2, 8, 1]
expected_output_data = [6, 8, 8, 8, -1, -1]


def next_greater_element_2(input_data):
    stack = s.Stack(len(input_data), True) # suppress_printing = True
    result = []

    for x in input_data:
        if stack.is_empty():
            stack.push(x)
        else:
            if x < stack.peek():
                stack.push(x)
            else:
                while not stack.is_empty():
                    stack.pop()
                    result.append(x)

                stack.push(x)

    while not stack.is_empty():
        stack.pop()
        result.append(-1)

    return result


def main():
    print("Input: " + str(input_data))
    print("Expected: " + str(expected_output_data))
    print("Output: " + str(next_greater_element_2(input_data)))


if __name__ == '__main__':
    main()

Output

Input: [4, 6, 3, 2, 8, 1]
Expected: [6, 8, 8, 8, -1, -1]
Output: [6, 8, 8, 8, -1, -1]

Time Complexity = O(n) -> Significant Improvement over brute force - O(n^2)

Challenge 8: Solve a Celebrity Problem using a Stack

Definitions:

input_data[row][col] = 1 means row knows column
input_data[row][col] = 0 means row does not know col
A celebrity does not know anyone, but everyone knows a celebrity.
Assume there is at max a single celebrity at the party

Terminology:

Row index represents a person identifier eg. row 1 represents the guest no. 2 at the party, columns represent if the guest knows another guest whose row index is same as column index

Meaning in above example:

Guest no. 1 knows guest no. 2 and guest no. 3, but not guest no. 4
Guest no. 2 knows guest no. 1, guest no. 3 and guest no. 4
Guest no. 4 only knows guest no. 2 and guest no. 3, but not guest no. 1
Guest no. 3 however does not know anybody.

–> This means guest no. 3 is a celebrity as everyone else knows guest no. 3, but guest no. 3 does not know anyone

Solution:

Push all row indices (guest ids) in a stack
Pop guest ids from stack until stack is empty, 2 at a time
If party[x][y] 1, means guest x knows guest y
- push next guest y to stack and discard x
else:
- push guest x back to stack, ignoring y (compare x with y+1 in the next iteration)
Finally the stack only contains 1 guest it means everyone knows that guest
Now assume that guest is a celebrity and check if the guest knows anyone else at the party.
If the guest knows anyone:
- means they are not a celebrity
- return -1 (no celebrity)
else:
- guest is a celebrity
- return guest id

import educative.course1.stacks_queues.stack as s

input_data = [
    [0, 1, 1, 0],
    [1, 0, 1, 1],
    [0, 0, 0, 0],
    [0, 1, 1, 0]
]
input_num_people = 4 # num rows in the input array
expected_output_data = 2


def find_celebrity(party_data, num_people):
    stack = s.Stack(num_people, True) # suppress_printing = True
    celebrity = -1

    for i in range(num_people):
        stack.push(i)

    while not stack.is_empty():
        x = stack.pop()

        # check if stack empty before popping second guest id
        if stack.is_empty():
            # if stack empty, previously popped guest id is the last id
            # and therefore we assume everyone knows them.
            celebrity = x
            break

        y = stack.pop()

        if party_data[x][y] is 1:
            stack.push(y)
        else:
            stack.push(x)

    for i in range(num_people):
        if celebrity is not i:
            if (party_data[celebrity][i] is 1) or (not party_data[i][celebrity] is 1):
                return -1

    return celebrity


def main():
    print("Input: " + str(input_data))
    print("Expected: " + str(expected_output_data))
    print("Output: " + str(find_celebrity(input_data, input_num_people)))


if __name__ == '__main__':
    main()

Output

Input: [
  [0, 1, 1, 0],
  [1, 0, 1, 1],
  [0, 0, 0, 0],
  [0, 1, 1, 0]
]
Expected: 2
Output: 2

Time Complexity = O(n)

Challenge 9: Check for Balanced Parentheses using Stack

We can check if the parentheses are balanced by pushing all opening parentheses on to a stack and then popping elements one by one, comparing next character with the popped element in a loop.

Iterate the input expression character by character.
If current character is an opening parentheses - “(“ or “[“ or “{“.
- Push character to stack.
Else:
- If stack is empty already, means number of opening parentheses in the stack were less then number of closing parentheses in the string, means string is unbalanced.
- Else:
  - Pop the last element from stack and compare with current character.
  - If the popped element is NOT the opening parentheses of the current character, it means the string is not balanced.
  - So, return False.

import educative.course1.stacks_queues.stack as s

input_string = "{[({})]}"
expected_output = True


def check_balanced(expression):
    input_chars = list(expression)
    stack = s.Stack(len(input_chars), True) # suppress_printing = True

    for char in input_chars:
        if char is "{" or char is "[" or char is "(":
            stack.push(char)
        else:
            if stack.is_empty():
                # if the string is unbalanced, number of opening parentheses
                # do not match with the closing parentheses, this will lead
                # to stack running empty before the whole string has been
                # processed, so return False
                return False
            if char is "}" and stack.pop() is not "{":
                return False
            if char is "]" and stack.pop() is not "[":
                return False
            if char is ")" and stack.pop() is not "(":
                return False

    if not stack.is_empty():
        return False

    return True


def main():
    print("Input: " + str(input_string))
    print("Expected: " + str(expected_output))
    print("Output: " + str(check_balanced(input_string)))


if __name__ == '__main__':
    main()

Output

Input: {[({})]}
Expected: True
Output: True

Time Complexity = O(n)

Challenge 10: Create Stack where min() gives minimum in O(1)

Defintion:

Min Stack implementation returns the minimum element of a stack in O(1), instead of O(n) which will be the case if we searched for the minimum value every time.

Solution:

This is achieved by keeping track of the minimum value is a separate stack in parallel to the main stack.

push(data) ->

Push data to main_stack
If min stack is empty:
- Push the data to min stack and return
if data <= top of min_stack
- Push the data to min stack and return

pop() ->

If min_stack is not empty, check:
- If top of min stack is same as top of main stack:
  - Pop the top of min_stack
Else:
- Pop and return the top of main stack.

min() ->

If min_stack is not empty:
- Return top of min_stack.

import educative.course1.stacks_queues.stack as s


class MinStack():
    def __init__(self, capacity=None, suppress_printing=False):
        self.suppress_printing = suppress_printing
        self.capacity = capacity
        self.stack = s.Stack(capacity, suppress_printing)
        self.min_stack = s.Stack(capacity, suppress_printing)

    def is_full(self):
        if self.stack.is_full():
            return True
        return False

    def is_empty(self):
        if self.stack.is_empty():
            return True
        return False

    def push(self, data):
        if self.is_full():
            print("can't push anymore, stack full...")
            return None

        self.stack.push(data)
        if not self.suppress_printing:
        	print("pushed data = " + str(data))

        if self.min_stack.is_empty():
            self.min_stack.push(data)
            if not self.suppress_printing:
            	print("pushed data to min stack = " + str(data))
            return None

        if data <= self.min_stack.peek():
            self.min_stack.push(data)
            if not self.suppress_printing:
            	print("pushed data to min stack = " + str(data))

        return None

    def pop(self):
        if self.is_empty():
            print("can't pop, stack empty...")
            return None

        if not self.min_stack.is_empty():
            if self.min_stack.peek() is self.stack.peek():
                min_pop = self.min_stack.pop()
                if not self.suppress_printing:
                	print("popped data from min stack= " + str(min_pop))

        popped = self.stack.pop()
        if not self.suppress_printing:
        	print("popped data (main stack) = " + str(popped))

        return popped

    def peek(self):
        if self.stack.is_empty():
            print("nothing at top, stack empty...")
            return None
        return self.stack.peek()

    def min(self):
        if self.stack.is_empty():
            print("no min exists, stack empty...")

        return self.min_stack.peek()

    def print_stack(self):
        pretty_list = self.prettify()
        print(pretty_list)

        return None

    def print_min_stack(self):
        pretty_list = self.prettify_min()
        print(pretty_list)

        return None

    def prettify(self):
        printer = "main:\n"
        for i in range(self.capacity)[::-1]:
            printer += str(self.capacity - i -1) + \
	            " -> [  " + str(self.stack.elements[i]) + "  ]"
            if i is not self.capacity: printer += "\n"

        return printer

    def prettify_min(self):
        printer = "min:\n"
        for i in range(self.capacity)[::-1]:
            printer += str(self.capacity - i - 1) + \
            	" -> [  " + str(self.min_stack.elements[i]) + "  ]"
            if i is not self.capacity: printer += "\n"

        return printer

Validating Stack with O(1) min() Implementation

import educative.course1.stacks_queues.ch10_min_stack as min_stack


def main():
    print("Stack initialized with capacity = 6")
    example = min_stack.MinStack(6, True) # suppress_printing = True

    print("------")
    print("pushing to stack...")
    example.push(5)
    example.push(6)
    example.push(7)
    example.push(8)
    example.push(9)
    example.push(2)
    example.push(7)

    print()
    print("peeking from stack...")
    print(example.peek())

    print()
    example.print_stack()

    print("------")
    print("popping from stack..")
    example.pop()
    example.pop()

    print()
    print("peeking from stack...")
    print(example.peek())

    print()
    example.print_stack()

    print("------")
    print("popping from stack..")
    example.pop()
    example.pop()
    example.pop()
    example.pop()
    example.pop()

    print()
    print("peeking from stack...")
    print(example.peek())

    print()
    example.print_stack()

    print("------")
    print("pushing to stack...")
    example.push(7)
    example.print_stack()
    example.print_min_stack()
    print("minimum: " + str(example.min()))

    print()
    print("pushing to stack...")
    example.push(8)
    example.print_stack()
    example.print_min_stack()
    print("minimum: " + str(example.min()))

    print()
    print("pushing to stack...")
    example.push(5)
    example.print_stack()
    example.print_min_stack()
    print("minimum: " + str(example.min()))

    print()
    print("pushing to stack...")
    example.push(9)
    example.print_stack()
    example.print_min_stack()
    print("minimum: " + str(example.min()))

    print()
    print("pushing to stack...")
    example.push(5)
    example.print_stack()
    example.print_min_stack()
    print("minimum: " + str(example.min()))

    print()
    print("pushing to stack...")
    example.push(2)
    example.print_stack()
    example.print_min_stack()
    print("minimum: " + str(example.min()))

    print()
    print("popping from stack...")
    example.pop()
    example.print_stack()
    example.print_min_stack()
    print("minimum: " + str(example.min()))


if __name__ == '__main__':
    main()

Output

Stack initialized with capacity = 6
 ------
pushing to stack...
can’t push anymore, stack full...

peeking from stack...
2

main:
0 -> [  2  ]
1 -> [  9  ]
2 -> [  8  ]
3 -> [  7  ]
4 -> [  6  ]
5 -> [  5  ]

------
popping from stack..

peeking from stack...
8

main:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  8  ]
3 -> [  7  ]
4 -> [  6  ]
5 -> [  5  ]

------
popping from stack..
can’t pop, stack empty...

peeking from stack...
nothing at top, stack empty...
None

main:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  None  ]
4 -> [  None  ]
5 -> [  None  ]

------
pushing to stack...
main:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  None  ]
4 -> [  None  ]
5 -> [  7  ]

min:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  None  ]
4 -> [  None  ]
5 -> [  7  ]

minimum: 7

pushing to stack...
main:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  None  ]
4 -> [  8  ]
5 -> [  7  ]

min:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  None  ]
4 -> [  None  ]
5 -> [  7  ]

minimum: 7

pushing to stack...
main:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  5  ]
4 -> [  8  ]
5 -> [  7  ]

min:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  None  ]
4 -> [  5  ]
5 -> [  7  ]

minimum: 5

pushing to stack...
main:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  9  ]
3 -> [  5  ]
4 -> [  8  ]
5 -> [  7  ]

min:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  None  ]
4 -> [  5  ]
5 -> [  7  ]

minimum: 5

pushing to stack...
main:
0 -> [  None  ]
1 -> [  5  ]
2 -> [  9  ]
3 -> [  5  ]
4 -> [  8  ]
5 -> [  7  ]

min:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  5  ]
4 -> [  5  ]
5 -> [  7  ]

minimum: 5

pushing to stack...
main:
0 -> [  2  ]
1 -> [  5  ]
2 -> [  9  ]
3 -> [  5  ]
4 -> [  8  ]
5 -> [  7  ]

min:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  2  ]
3 -> [  5  ]
4 -> [  5  ]
5 -> [  7  ]

minimum: 2

popping from stack...
main:
0 -> [  None  ]
1 -> [  5  ]
2 -> [  9  ]
3 -> [  5  ]
4 -> [  8  ]
5 -> [  7  ]

min:
0 -> [  None  ]
1 -> [  None  ]
2 -> [  None  ]
3 -> [  5  ]
4 -> [  5  ]
5 -> [  7  ]

minimum: 5

Time Complexity for min() = O(1)