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

Key Operations of a Stack

Explore fundamental stack operations in C# including checking if the stack is empty or full, pushing new elements, popping the top element, peeking at the top without removal, and determining size. Understand how these operations work with both array-based and linked list implementations, and their efficient constant time performance essential for LIFO data handling.

We'll cover the following...

Now that we have seen stack implementations using arrays and linked lists, the next step is to examine the fundamental operations used to interact 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 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, because 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.

C# 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.

C# 14.0
using System;
class Stack
{
    private readonly int[] data;
    private readonly int capacity;
    private int top;
    public Stack(int capacity = 10)
    {
        this.capacity = capacity;          // Maximum number of elements
        data = new int[capacity];          // Array to store elements
        top = -1;                          // Index of top element (-1 means empty)
    }
    public bool IsEmpty()
    {
        return top == -1;
    }
}
class Solution
{
    static void Main()
    {
        // Create a stack
        Stack stack = new Stack(10);
        Console.WriteLine($"Is stack empty? {stack.IsEmpty().ToString().ToLower()}"); // Output: true
    }
}

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. Since 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.

C# implementation

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

C# 14.0
using System;
class Stack
{
    private readonly int[] data;
    private readonly int capacity;
    private int top;
    public Stack(int capacity = 10)
    {
        this.capacity = capacity;
        data = new int[capacity];
        top = -1;
    }
    public bool IsEmpty()
    {
        return top == -1;
    }
    public bool IsFull()
    {
        return top == capacity - 1;
    }
    public bool Push(int value)
    {
        if (IsFull())
        {
            return false;
        }
        top++;
        data[top] = value;
        return true;
    }
    public int? Pop()
    {
        if (IsEmpty())
        {
            return null;
        }
        int value = data[top];
        top--;
        return value;
    }
}
class Solution
{
    static void Main()
    {
        // Create a stack with capacity 5
        Stack stack = new Stack(5);
        // Fill the stack with elements: [88, 95, 72, 80, 91]
        stack.Push(88);
        stack.Push(95);
        stack.Push(72);
        stack.Push(80);
        stack.Push(91);
        Console.WriteLine($"Is stack full? {stack.IsFull().ToString().ToLower()}"); // Output: true
        Console.WriteLine("Simulating popping one element from the stack");
        stack.Pop();
        Console.WriteLine($"Is stack full? {stack.IsFull().ToString().ToLower()}"); // Output: false
    }
}

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.

C# implementation

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

  1. We check if the stack is full by calling the IsFull() method. If it is full, we display an error message and return false because no more elements can be added to the stack.

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

  3. Place the new element at the top.

C# 14.0
using System;
class Stack
{
    private readonly int[] data;
    private readonly int capacity;
    public int Top { get; private set; }
    public Stack(int capacity = 10)
    {
        this.capacity = capacity;          // Maximum number of elements
        data = new int[capacity];          // Array to store elements
        Top = -1;                          // Index of top element (-1 means empty)
    }
    public bool Push(int value)
    {
        // Check if stack is full
        if (IsFull())
        {
            Console.WriteLine("Stack Overflow! Cannot push element.");
            return false;
        }
        // Increment top and add the element
        Top++;
        data[Top] = value;
        return true;
    }
    public bool IsEmpty()
    {
        return Top == -1;
    }
    public bool IsFull()
    {
        return Top == capacity - 1;
    }
}
class Solution
{
    static void Main()
    {
        // Create a stack with capacity 10
        Stack stack = new 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
        Console.WriteLine($"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 ...

...