Stacks and Queue

Stack: Introduction

Stacks are a data structure that are similar to lists. The difference is that they are FILO (first in last out). A simple real-world example of a stack would be a can of tennis balls. If you put balls numbered 1, 2, and 3 in that order into a tennis ball can. they can only be removed in the order 3, 2, 1. (See reference). Stacks have method called push and pop.

tennis balls alt

Stack: Constructor

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Stack:
    def __init__(self, value):
        new_node = Node(value)
        self.top = new_node
        self.height = 1

    def print_stack(self):
        temp = self.top
        while temp is not None:
            print(temp.value)
            temp = temp.next

my_stack = Stack(4)

my_stack.print_stack()

Stack: Push

    def push(self, value):
        new_node = Node(value)
        if self.height == 0:
            self.top = new_node
        else:
            new_node.next = self.top
            self.top = new_node
        self.height += 1

Stack: Pop

    def pop(self):
        if self.height == 0:
            return None
        temp = self.top
        self.top = self.top.next
        temp.next = None
        self.height -= 1
        return temp

Queue: Introduction

Queues are FIFO (first in first out). A simple real-world example of a queue would be a line of people waiting to get in a bus. If you put people in the line in the order 1, 2, and 3, they can only be removed in the order 1, 2, and 3. (See reference). Queues have method called enqueue and dequeue.

Queue: Constructor

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        
class Queue:
    def __init__(self, value):
        new_node = Node(value)
        self.first = new_node
        self.last = new_node
        self.length = 1

    def print_queue(self):
        temp = self.first
        while temp is not None:
            print(temp.value)
            temp = temp.next

my_queue = Queue(4)

my_queue.print_queue()

Queue: Enqueue

    def enqueue(self, value):
        new_node = Node(value)
        if self.first is None:
            self.first = new_node
            self.last = new_node
        else:
            self.last.next = new_node
            self.last = new_node
        self.length += 1

Queue: Dequeue

    def dequeue(self):
        if self.length == 0:
            return None
        temp = self.first
        if self.length == 1:
            self.first = None
            self.last = None
        else:
            self.first = self.first.next
            temp.next = None
        self.length -= 1
        return temp