Search⌘ K
AI Features
Home
Courses
Learn Data Structures and Algorithms

Key Operations of a Stack

Explore the core operations of a stack data structure such as push, pop, peek, isEmpty, isFull, and size. Understand how to implement these operations in Python using arrays and linked lists. Learn to handle stack capacity, check states before operations, and evaluate time and space complexities for efficient stack management.

We'll cover the following...

With stack implementations using arrays and linked lists established, the next step is to examine the fundamental operations for interacting with a stack. These operations define the stack’s behavior and how its data is manipulated.

A stack supports several core operations, but they all revolve around the LIFO (Last in, first out) principle. Before we can add or remove elements, we often need to check the current state of the stack. Let's begin with two essential utility operations.

The isEmpty() operation

The isEmpty() method checks whether the stack is empty. This is crucial before attempting to remove or view elements, as popping an empty stack would result in an error.

Example: Consider a stack that currently holds [88, 95, 72, 80, 91]. The top index points to position 4 (where 91 is stored). Calling isEmpty() on this stack would return False because top is 4, not -1.

If we were to pop all five elements one by one, top would eventually become -1 again. At that point, calling isEmpty() would return True.

Python implementation

In an array-based stack, we check if top equals -1. Remember that we initialized top to -1 when creating an empty stack, so if it's still -1, no elements have been added.

Python
class Stack:
    def __init__(self, capacity=10):
        """Initialize an empty stack with given capacity"""
        self.capacity = capacity  # Maximum number of elements
        self.data = [None] * capacity  # Array to store elements
        self.top = -1  # Index of top element (-1 means empty)
    
    def isEmpty(self):
        """Check if the stack is empty"""
        return self.top == -1
# Create a stack
stack = Stack(10)
print(" Is stack empty?",stack.isEmpty())  # Output: True (stack is empty)

The isFull() operation

The isFull() operation checks whether the stack has reached its maximum capacity. This is only relevant for array-based stacks with a fixed size. Before pushing a new element, we should check if there’s space available.

Example: Consider a stack with capacity 5 that currently holds [88, 95, 72, 80, 91]. The top is 4, and the capacity is 5. As top equals capacity - 1, i.e., (5 - 1 = 4), the stack is full. Calling isFull() would return True.

If we pop one element (91), top would become 3. Now top (3) is less than capacity - 1 (4), so calling isFull() would return False.

Python implementation

In an array-based stack, we check if top equals capacity - 1. As array indices start at 0, the last valid index is capacity - 1. If top has reached this position, the stack is full.

Python
class Stack:
    def __init__(self, capacity=10):
        self.capacity = capacity  # Maximum number of elements
        self.data = [None] * capacity  # Array to store elements
        self.top = -1  # Index of top element (-1 means empty)
    
    def isEmpty(self):
        return self.top == -1
    
    def isFull(self):
        """Check if the stack is full"""
        return self.top == self.capacity - 1
# Create a stack with capacity 5
stack = Stack(5)
# Simulate a full stack with elements: [88, 95, 72, 80, 91]
stack.top = 4  # top index is 4
print("Is stack full?",stack.isFull())  # Output: True (stack is full)
print( "Simulating popping one element from the stack")
stack.top = 3  # top index is now 3
print("Is stack full?", stack.isFull())  # Output: False (stack has space)

Note: For linked list-based stacks, isFull() is typically not needed because they can grow dynamically until the system runs out of memory.

Push operation

The push operation adds a new element to the top of the stack. This is how we insert data into the stack, and it always happens at one end, i.e., the top.

Before pushing an element into an array-based stack, we must first check if the stack is full using isFull(). If there's space available, we increment the top index and place the new element at that position.

Example: Let’s say we have a stack with capacity 10 that currently holds [88, 95, 72, 80], and we want to push the value 91 onto the stack. After the push, the stack contains [88, 95, 72, 80, 91] with top at index 4.

svg viewer

Python implementation

Here’s how we implement the Push operation step by step:

  1. We will check if the stack is full by calling the isFull() function. If it is full, we print an error message and return False as no further elements can be added to the stack.

  2. If the stack has capacity, increment top as we will place our new element at the top.

  3. Place the new element at the top.

Python
class Stack:
    def __init__(self, capacity=10):
        self.capacity = capacity  # Maximum number of elements
        self.data = [None] * capacity  # Array to store elements
        self.top = -1  # Index of top element (-1 means empty)
    
    def push(self, value):
        """Add an element to the top of the stack"""
        # Check if stack is full
        if self.isFull():
            print("Stack Overflow! Cannot push element.")
            return False
        
        # Increment top and add the element
        self.top += 1
        self.data[self.top] = value
        return True
        
    def isEmpty(self):
        return self.top == -1
    
    def isFull(self):
        return self.top == self.capacity - 1
# Create a stack with capacity 10
stack = Stack(10)
# Push elements one by one
stack.push(88)   # Stack: [88], top = 0
stack.push(95)   # Stack: [88, 95], top = 1
stack.push(72)   # Stack: [88, 95, 72], top = 2
stack.push(80)   # Stack: [88, 95, 72, 80], top = 3
stack.push(91)   # Stack: [88, 95, 72, 80, 91], top = 4
print(f"Top index: {stack.top}")  # Output: Top index: 4

Pop operation

The pop operation removes and returns the element at the top of the stack. This is how we retrieve data from the stack while also removing it from the structure.

Before popping, we must check if the stack is empty using isEmpty(). If the stack has elements, we retrieve the element at the top index, then decrement top to reflect that the stack now has one fewer element.

Example: Consider a stack that currently contains [88, 95, 72, 80, 91], and we want to pop an element. After the pop, the stack contains [88, 95, 72, 80] with top at index 3. The value 91 is returned to the caller.

Python implementation

Here’s how we implement the Pop operation step by step:

  1. We will check if the stack is empty by calling the isEmpty() function. If it is empty, we print an error message and return None as no elements can be removed from the stack.

  2. If the stack is not empty, we retrieve the value stored at its top index and store it in the variable value.

  3. After retrieving the top element, we decrement the top index to indicate that the top element has been removed.

  4. in the end,, we return the value of the removed top element.

Python 
class Stack:
    def __init__(self, capacity=10):
        """Initialize an empty stack with given capacity"""
        self.capacity = capacity  # Maximum number of elements
        self.data = [None] * capacity  # Array to store elements
        self.top = -1  # Index of top element (-1 means empty)
    
    def pop(self):
        """Remove and return the top element"""
        # Check if stack is empty
        if self.isEmpty():
            print("Stack Underflow! Cannot pop from empty stack.")
            return None
        
        # Get the top element
        value = self.data[self.top]
        # Decrement top
        self.top -= 1
        return value
    
    def isEmpty(self):
        return self.top == -1
    
    def isFull(self):
        return self.top == self.capacity - 1
    
    def push(self, value):
        if self.isFull():
            print("Stack Overflow! Cannot push element.")
            return False
        self.top += 1
        self.data[self.top] = value
        return True
# Create a stack and push elements: [88, 95, 72, 80, 91]
stack = Stack(10)
stack.push(88)
stack.push(95)
stack.push(72)
stack.push(80)
stack.push(91)
# Pop elements
print(stack.pop())  # Output: 91, Stack now: [88, 95, 72, 80]
print(stack.pop())  # Output: 80, Stack now: [88, 95, 72]
print(stack.pop())  # Output: 72, Stack now: [88, 95]
print(f"Top index after popping 3 elements: {stack.top}")  # Output: 1

Peek operation

The peek operation returns the element at the top of the stack without removing it. This allows us to see what's on top without modifying the stack's contents. Like pop, we must first check if the stack is empty. If it has elements, we ...