Stack

Created : January 27, 2021

Written in Python.

  • Linear data structure
  • LIFO (Last In First Out)
  • Insertion/Deletion: only on same end
  • Example

    • stacked plates
    • undo (Ctrl + z)

Basic Operations

  • push: Add an item.

    • If the stack is full → Overflow condition
    • append(item)
  • pop: Remove an item.

    • If the stack is empty → Underflow condition
    • pop()
  • peek or top: Return top element of stack.
  • isEmpty: Return true if stack is empty, else false.
  • size: Return the size of the stack

Big-O Complexity for Stack

  • Time complexity

    • Insertion/Deletion: O(1)
    • Access/Search: O(n)
  • Space complexity: O(n)

Implementation

# Create stack class
class Stack:
  # Initialize
  def __init__(self):
    self.items = []

  # Push an item to the end
  def push(self, item):
    self.items.append(item)

  # Pop an item from the end
  def pop(self):
    # Check if stack is not empty
    if not self.isEmpty():
      return self.items.pop()
    else:
      print('Stack underflow')
      exit()
  
  # Return top element of stack
  def peek(self):
    # Check if stack is not empty
    if not self.isEmpty():
      return self.items[-1]
    else:
      print('Stack underflow')
      exit()

  # Check if stack is empty
  def isEmpty(self):
    return len(self.items) == 0

  # Return size of stack
  def size(self):
    return len(self.items)