List-Based Collections - Stacks and Queues

Nov. 9, 2020

Vuong Huynh

Stacks

Stacks are also list-based data structures. Think about a stack of pancakes, we keep putting a pancake on top of others.

Stacks are really useful when we care about the recent (oldest) elements.

Push: add an element on top of the stack, similar to append or insert.

Pop: take an element out from the top of the stack, similar to remove.

L.I.F.O: Last In, First Out. The last element added will be the first element to be taken out.

In the Python list, the stack is already functionally built-in. append() function is equivalent to a push, while pop() is ... a pop. These functions make stack manipulation in Python so easy.

Practice: We will build a Stack class to see how stack really works under the hood by using our old LinkedList class.

"""Add a couple of methods to our LinkedList class, 
and use that to implement a Stack.
You have 4 functions below to fill in:
insert_first, delete_first, push, and pop.
Think about this while you're implementing:
why is it easier to add an "insert_first"
function than just use "append"?"""

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


class LinkedList():
    def __init__(self, head=None):
        self.head = head
        
    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

    def insert_first(self, new_element):
        "Insert new element as the head of the LinkedList"
        new_element.next = self.head
        self.head = new_element

    def delete_first(self):
        "Delete the first (head) element in the LinkedList as return it"
        if self.head:
            deleted_element = self.head
            temp = deleted_element.next
            self.head = temp
            return deleted_element
        else:
            return None


class Stack(object):
    def __init__(self,top=None):
        self.ll = LinkedList(top)

    def push(self, new_element):
        "Push (add) a new element onto the top of the stack"
        self.ll.insert_first(new_element)

    def pop(self):
        "Pop (remove) the first element off the top of the stack and return it"
        return self.ll.delete_first()
    
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)

# Start setting up a Stack
stack = Stack(e1)

# Test stack functionality
stack.push(e2)
stack.push(e3)
print(stack.pop().value)            # 3 - e3 is the last in
print(stack.pop().value)            # 2 - e2 is the second last in
print(stack.pop().value)            # 1 - e1 is the first in
print(stack.pop())                  # None - stack is empty
stack.push(e4)
print(stack.pop().value)            # 4 - e4 is the only new element in stack

Queues

Think about a line of people checking out at the check-out counter. The first one in the line will be checked out first.

F.I.F.O: First In, First Out. The oldest element will come out first. It is opposite to stack in this method. The first element in the queue is called HEAD. The last element in the queue called TAIL.

Enqueue: add an element into the TAIL of the queue (the last in and will be the last out)

Dequeue: remove an element from the HEAD of the queue (the first in and will be the first out)

Peak: the HEAD element which is still in the queue.

Priority queue: a numerical priority is assigned when we enqueue an element into the queue. The highest priority will be dequeue first. If all elements have the same priority, the oldest element will be dequeue first.

Deques: (deks) are the double-ended queues that go both ways. We can enqueue or dequeue on both sides of the queue. deque is a combination of stack and queue.

In Python, deque package can be called from collections library:

from collections import deque

Practice: we will build a class Queue which uses a list in Python to implement Queue methods

"""Make a Queue class using a list!
Hint: You can use any Python list method
you'd like! Try to write each one in as 
few lines as possible.
Make sure you pass the test cases too!"""

class Queue():
    def __init__(self, head=None):
        self.storage = [head]

    def enqueue(self, new_element):
        self.storage.append(new_element)

    def peek(self):
        return self.storage[0]

    def dequeue(self):
        return self.storage.pop(0)
    
# Setup
q = Queue(1)
q.enqueue(2)
q.enqueue(3)

# Test peek
print(q.peek())                 # 1 -  first element with value 1

# Test dequeue
print(q.dequeue())              # 1 - took the first element out

# Test enqueue
q.enqueue(4)
print(q.dequeue())              # 2 - the second element becomes the first element 
print(q.dequeue())              # 3 - the third element becomes the first element 
print(q.dequeue())              # 4 - the fourth element becomes the first element 

q.enqueue(5)
print(q.peek())                 # 5 - the fifth element is the head of the queue