Array Implementation of Stack in Data Structure

A stack is a fundamental data structure in computer science that follows the Last In, First Out (LIFO) principle. In a stack, elements are added (pushed) and removed (popped) from the same end, referred to as the top of the stack. This simple yet powerful concept has wide applications in problems such as expression evaluation, function calls, and undo mechanisms in software.

While there are several ways to implement a stack, one of the most common methods is using an array. In this blog post, we’ll explore how to implement a stack using arrays, the advantages and limitations of this approach, and how to perform basic operations on a stack.

What is a Stack?

A stack is a linear data structure that allows operations at only one end, called the top. The two primary operations on a stack are:

1. Push: Adding an element to the top of the stack.
2. Pop: Removing the top element from the stack.

Additionally, there are two auxiliary operations often associated with a stack:

• Peek/Top: Checking the element at the top of the stack without removing it.
• IsEmpty: Checking if the stack is empty.

Array Implementation of Stack

In array implementation, the stack is represented as a fixed-size array. The top of the stack is maintained by an index variable. Here’s how we can manage the stack using an array:

• Push Operation: When an element is pushed, the value is inserted at the top index, and the index is incremented.
• Pop Operation: When an element is popped, the top index is decremented, and the element at that position is removed.
• Peek Operation: This operation allows checking the value of the element at the top index without modifying the stack.
• IsEmpty Operation: This operation checks if the stack has any elements (i.e., if the top index is greater than or equal to 0).

Array-Based Stack Operations

Let’s break down the implementation of the basic operations of a stack using an array:

1. Push Operation

To push an element, we add it at the current top index of the array and then increment the index.

class Stack {
    constructor(size) {
        this.stack = new Array(size);  // Creates an array of given size
        this.top = -1;  // Initializes top to -1, indicating the stack is empty
        this.maxSize = size;  // Maximum size of the stack
    }

    push(element) {
        if (this.top < this.maxSize - 1) {  // Check if there is space
            this.stack[++this.top] = element;  // Increment top and add element
            console.log(`${element} pushed to stack`);
        } else {
            console.log("Stack Overflow! Cannot add more elements.");
        }
    }
}

2. Pop Operation

To pop an element, we remove the top element by decrementing the index and return the value.

class Stack {
    // Existing constructor code...
    
    pop() {
        if (this.top >= 0) {  // Check if the stack is not empty
            let poppedElement = this.stack[this.top--];  // Retrieve and decrement top
            console.log(`${poppedElement} popped from stack`);
            return poppedElement;
        } else {
            console.log("Stack Underflow! No elements to pop.");
            return null;
        }
    }
}

3. Peek/Top Operation

To peek, we simply return the element at the top index without modifying the stack.

class Stack {
    // Existing constructor and methods...

    peek() {
        if (this.top >= 0) {
            console.log(`Top element is ${this.stack[this.top]}`);
            return this.stack[this.top];
        } else {
            console.log("Stack is empty.");
            return null;
        }
    }
}

4. IsEmpty Operation

The isEmpty method checks if the stack is empty by looking at the top index.

class Stack {
    // Existing constructor and methods...

    isEmpty() {
        return this.top === -1;  // Returns true if stack is empty
    }
}

Example of Stack Implementation Using an Array

Let’s combine all of the above methods into a complete stack class and run some examples.

class Stack {
    constructor(size) {
        this.stack = new Array(size);
        this.top = -1;
        this.maxSize = size;
    }

    push(element) {
        if (this.top < this.maxSize - 1) {
            this.stack[++this.top] = element;
            console.log(`${element} pushed to stack`);
        } else {
            console.log("Stack Overflow! Cannot add more elements.");
        }
    }

    pop() {
        if (this.top >= 0) {
            let poppedElement = this.stack[this.top--];
            console.log(`${poppedElement} popped from stack`);
            return poppedElement;
        } else {
            console.log("Stack Underflow! No elements to pop.");
            return null;
        }
    }

    peek() {
        if (this.top >= 0) {
            console.log(`Top element is ${this.stack[this.top]}`);
            return this.stack[this.top];
        } else {
            console.log("Stack is empty.");
            return null;
        }
    }

    isEmpty() {
        return this.top === -1;
    }
}

// Usage
let stack = new Stack(5);
stack.push(10);
stack.push(20);
stack.push(30);
stack.peek();  // Should print "Top element is 30"
stack.pop();   // Should pop 30
stack.pop();   // Should pop 20
stack.isEmpty(); // Should return false
stack.pop();   // Should pop 10
stack.isEmpty(); // Should return true

Advantages of Array Implementation of Stack

1. Simple Implementation: Array-based stack is simple to implement and doesn’t require complex data structures or memory management techniques.
2. Constant-Time Operations: Both push and pop operations take O(1) time, as they only involve adding or removing elements from one end (the top of the stack).
3. Memory Efficiency: If the size of the stack is known beforehand, using an array ensures memory is allocated efficiently.

Limitations of Array Implementation of Stack

1. Fixed Size: The primary limitation of an array-based stack is its fixed size. Once the array is full, no more elements can be added, leading to a stack overflow condition. This can be mitigated by using dynamic resizing techniques, but in basic array implementations, this is a limitation.
2. Memory Wastage: If the stack does not use all the allocated space, memory might be wasted. This is a tradeoff between preallocating memory and dynamically resizing the stack.

Conclusion

The array implementation of a stack provides a simple and efficient way to manage a collection of elements in a LIFO order. While it is ideal for scenarios where the maximum size of the stack is known and fixed, it may not be as flexible as other implementations like the linked list for dynamic sizing. Understanding how to implement a stack using arrays is a fundamental concept in data structures that has practical applications in algorithms, memory management, expression parsing, and many other domains.