What Is Stack In Data Structure

What is Stack in Data Structure and how to implement it using arrays in C#

Introduction

In this blog will let you know what stack is and how we can implement stack operations using arrays. We will learn few important operations of stack as well.

Stack in Data Structure

Stack is a collection of objects which work with Last-In First-Out (LIFO) principle. It means that we can insert object at any time, but we can only remove an object from the top or recently inserted object.

Different operations in Stack

Push -> Insert an object

POP -> Remove recent inserted object

Peek -> Get the object which is recently inserted.

In Stack, every time the item/object will be inserted on top which is called push operation, and only item from top will be removed which is called pop operation.

Examples of stack

• The stack of trays in a cafeteria.
• A pack of Tennis ball in a bottle (Bottom is closed and we can put ball only from top)

Applications on Stacks

• Undo/Redo example
• HTML tags matching
• Web browser history
• Arithmetic expression evaluation

Implement Stack using Array in C#

Here we will look how to use Array to represent stacks data and stacks operations.

 Below are main operations that we must implement.

• push - Insert an element
• pop - remove an element and return it
• top() - return top element
• IsEmpty() - Check stack is empty or not
• len() - return length of stacks means total number of elements.

Create a console application in Visual studio environment as below. Main method will be static and it will call once you run this project.

namespace DataStructureTutorials {
    class Program {
        static void Main(string[] args) {
            Console.WriteLine("Hello World!");
        }
    }
}

I have renamed Program class with StackUsingArray just for understanding purpose.

First, we have to declare an array of integers which will store data and top variable of integer type which will hold position of top element in array.

Initially top will be zero because we don’t have any element in array.

class StackUsingArray {
    // array of integer
    int[] data;
    // position of top element
    int top;
    public StackUsingArray(int arraySize) {
        data = new int[arraySize];
        top = 0;
    }
}

Write methods to check below,

• IsEmpty - check if stack doesn’t have any element
• Length - Length of stack or how many items there are in the stack
• isFull - Check if stack is full

public bool IsEmpty() {
    return (top == 0) ? true : false;
}
public int Length() {
    return top;
}
public bool IsFull() {
    return (top == data.Length) ? true : false;
}

Implement Push operation

Push will take an integer as an input param. First, it will verify if stack is full then it will not insert the element but if there is space in stack then the new element will get inserted at top index of data array and then we will increase top position by one.

public void Push(int newElement) {
    // Check if stack is full
    if (IsFull()) {
        Console.WriteLine("Stack is full. Can not push any element");
        return;
    } else {
        // assign new element at top index
        data[top] = newElement;
        top = top + 1;
    }
}

Pop operation

This will return most recent inserted element from stack.

// Remove the most recent inserted element
public int Pop() {
    // check if stack is empty
    if (IsEmpty()) {
        Console.WriteLine("Stack is empty. Can not pop any element");
        return -1;
    }
    int e = data[top - 1];
    top = top - 1;
    return e;
}

Peek operation

This method is used to fetch current top element from stack.

// Return the top element
public int Peek() {
    if (IsEmpty()) {
        Console.WriteLine("Stack is empty.");
        return -1;
    } else return data[top - 1];
}

Display Operation

// Display all element of stack
public void Display() {
    if (IsEmpty()) {
        Console.WriteLine("Stack is empty. Can not display elements");
        return;
    }
    for (int i = 0; i < top; i++) {
        Console.Write(data[i] + "--");
    }
    Console.WriteLine();
}

Now update Main method as below and run the solution. Array size I am passing as 10.

static void Main(string[] args) {
    Console.WriteLine("Hello World!");
    ExecuteStackExample();
}
private static void ExecuteStackExample() {
    StackExample stack = new StackExample(10);
    stack.Push(5);
    stack.Push(3);
    stack.Display();
    Console.WriteLine("Performing Pop operation..");
    Console.WriteLine("Element removed: " + stack.Pop());
    stack.Display();
    Console.ReadKey();
}

Output will be as below. We can clearly see first it is pushing 5 & 3 into stack and both are getting displayed. After that top item is getting popped.

Summary

In this blog we understand, what is stack data structure and how to implement stack using arrays in C#.

Thank you!