Stacks and Queues

Stacks

• LIFO data structure - stands for last in, first out
• think of a stack of books, you don't pull the bottom out first, you take them off from the top
• putting an item on a stack is called pushing, adds it to the end of the stack
• removing an item from a stack is called popping, removes from the end of the stack
• example:

  class Stack:
      def __inti__(self):
          self.items = []
  
      def is_empty(self):
          return self.items == []
  
      def push(self, item):
          self.items.append(item)
  
      def pop(self):
          return self.items.pop()   # pops from end of stack
  
      def peek(self):       # returns the value of the last item, but doesn't pop it
          last = len(self.items) - 1
          return self.items[last]
  
      def size(self):
          return len(self.items)

• example: can use stacks to reverse strings
  • add each character to a stack, then pop them off one at a time into a new string

Queues

• FIFO data structure - stands for first in, first out
• think of people waiting in line
• example:

  class Queue:
      def __init__(self):
          self.items = []
  
      def is_empty(self):
          return self.items == []
  
      def enqueue(self, item):
          self.items.insert(0, item)    # inserts at the beginning /// cound append instead
  
      def dequeue(self):
          return self.items.pop()      # pops from the end /// if appended, then pop from beginning -- pop(0)
  
      def size(self):
          return len(self.items)