Working with stacks

Data Structures and Algorithms in Python

Miriam Antona

Software Engineer

Stacks

LIFO: Last-In First-Out
- Last inserted item will be the first item to be removed

A picture of a stack of books.

Stacks

LIFO: Last-In First-Out
- Last inserted item will be always the first item to be removed
Can only add at the top
- Pushing onto the stack

A picture of a stack of books with a new book added at the top of the stack.

Stacks

LIFO: Last-In First-Out
- Last inserted item will be always the first item to be removed
Can only add at the top
- Pushing onto the stack
Can only take from the top
- Popping from the stack

A picture of a stack of books with a book taken from the top of the stack.

Stacks

LIFO: Last-In First-Out
- Last inserted item will be always the first item to be removed
Can only add at the top
- Pushing onto the stack
Can only remove from the top
- Popping from the stack
Can only read the last element
- Peeking from the stack

A picture of a stack of books with an arrow pointing at the cover of the book located at the top of the stack.

Stacks - real uses

Undo functionality

A stack with one element.

Stacks - real uses

Undo functionality
- push each keystroke

A stack with a new element added at the top of the stack.

Stacks - real uses

Undo functionality
- push each keystroke

A stack with a new element added at the top of the stack.

Stacks - real uses

Undo functionality
- push each keystroke

A stack with a new element added at the top of the stack.

Stacks - real uses

Undo functionality
- push each keystroke

A stack with a new element added at the top of the stack.

Stacks - real uses

Undo functionality
- push each keystroke
- pop last inserted keystroke

A stack where an element has been removed from the top of the stack.

Stacks - real uses

Symbol checker: ( [ { } ] )
- push opening symbols

A stack with an opening symbol.

Stacks - real uses

Symbol checker: ( [ { } ] )
- push opening symbols

A stack with a new opening symbol added at the top of the stack.

Stacks - real uses

Symbol checker: ( [ { } ] )
- push opening symbols

A stack with a new opening symbol added at the top of the stack.

Stacks - real uses

Symbol checker: ( [ { } ] )
- push opening symbols
- check closing symbol

A stack with opening symbols and the word "check "}"".

Stacks - real uses

Symbol checker: ( [ { } ] )
- push opening symbols
- check closing symbol
- pop matching opening symbol

A stack where an opening symbol has been removed from the top of the stack.

Stacks - real uses

Function calls
- push block of memory
- pop after the execution ends

Stacks - implementation using singly linked lists

A stack represented as a linked list.

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

Stacks - implementation using singly linked lists

A stack represented as a linked list with the names of the parts of the nodes.

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

class Stack:
  def __init__(self):
    self.top = None

Stacks - implementation using singly linked lists

A stack represented as a linked list with the word "TOP" pointing to the top of the stack.

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

class Stack:
  def __init__(self):
    self.top = None

Stacks - push

A representation of an empty stack and a stack with elements.

def push(self, data):

Stacks - push

A representation of an empty stack and a stack with elements where a new node is going to be inserted.

def push(self, data): 
  new_node = Node(data)

  if self.top:

Stacks - push

A representation of an empty stack and a stack with elements, where the new node is connected to the element located at the top of the stack.

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top

Stacks - push

A representation of an empty stack and a stack with elements where the new node has been inserted.

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node

Stacks - pop

def pop(self):

  if self.top is None:

    return None

  else:

A representation of a stack with the word "TOP" pointing at the node located at the top.

Stacks - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

A representation of a stack with the word "popped_node" pointing to the node located at the top of the stack.

Stacks - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

A representation of a stack with the word "popped_node" pointing to the node located at the top of the stack and the word "TOP" pointing at the second node.

Stacks - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

A representation of a stack with the word "popped_node" pointing to a node disconnected from the stack and the word "TOP" pointing at the node located at the top of the stack.

Stacks - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

A representation of a stack with the word "TOP" pointing at the node located at the top of the stack.

Stacks - peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue in Python

LifoQueue:
- Python's queue module
- behaves like a stack

import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

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

Empty stack: True

Let's practice!

Data Structures and Algorithms in Python