Stacks

Like a pile of plates a stack is a last in first out (LIFO) data structure

If you think of the pile of plates then we can only access the plate on the top of the pile which is the last one added to the pile. To get to the first one we added to the pile we’d have to take off every other plate. This is exactly how the stack data structure works – Last In First Out (LIFO).

A stack uses the following operations:

Push – puts and item on top of the stack

Pop – takes an item off the top of the stack

Peek – looks at the item on top of the stack BUT doesn’t remove it

You also need a pointer to indicate where the top of the stack is.

Useful Links

• Isaac Computer Science – Stacks
• Craig ‘n Dave – Stacks and Queues Part 1
• Craig ‘n Dave – Stacks and Queues Part 2

Example Python Program

class Stack():
    def __init__(self, max_size):
        self.max_size = max_size
        self.stack = [None] * max_size
        self.top = -1

    def is_empty(self):
        return self.top == -1

    def is_full(self):
        return self.top == self.max_size-1

    def push(self, item):
        if self.is_full():
            return None
        self.top += 1
        self.stack[self.top] = item

    def pop(self):
        if self.is_empty():
            return None
        item = self.stack[self.top]
        self.top -= 1
        return item

    def peek(self):
        if self.is_empty():
            return None
        return self.stack[self.top]

Program Notes

This program uses a list to hold the data in the stack initially setting each element in the list to None. It shows how the push, pop and peek operations work. Note that if you needed to implement a stack in Python you could use the inbuilt push and pop list operations.

__init__()

• this is the constructor and is run every time a Stack object is created (instantiated)
• set the max_size of the stack
• creates a blank stack using a list and sets each element to None
• creates a pointer to the top of the stack which is initially set to -1 to show the stack is empty

is_empty()

• if top is set to -1 then we know the stack is empty

is_full()

• if top points to the last element in the list (max-size-1) then we know the stack is full

push() – add an item to the top of the stack

• if the stack is full
  • return None
• else
  • increment the top pointer
  • add an element to the list at the new top

pop() – remove an item from the top of the stack

• if the stack is empty
  • return None
• else
  • store the item on the top of the stack
  • decrement the top of the stack pointer
  • return the item we ‘popped’ off the stack

peek() – take a copy of the item on top of the stack

• if the stack is empty
  • return None
• else
  • return the item on top of the stack