Implement Stack using Arrays

Stack / Queues Implementation Easy

The concept of Last-In-First-Out (LIFO) stacks is widely used in real-world scenarios such as managing function calls in programming languages
Each time a function is called, the system 'pushes' contexts onto a call stack
When the function is done, the system 'pops' the context off of the stack and restore the state before the call
This call stack is fundamental to enabling function calls and recursion in virtually all modern programming languages
Similarly, the 'undo' feature in many software applications (like text editors or graphic design tools) is often implemented using a stack

Implement a Last-In-First-Out (LIFO) stack using an array. The implemented stack should support the following operations: push, pop, peek, and isEmpty.

Implement the ArrayStack class:

void push(int x): Pushes element x onto the stack.

int pop(): Removes and returns the top element of the stack.

int top(): Returns the top element of the stack without removing it.

boolean isEmpty(): Returns true if the stack is empty, false otherwise.

Please note that this section might seem a bit difficult without prior knowledge on what stacks is, we will soon try to add basics concepts for your ease! If you know the concepts already please go ahead to give a shot to the problem. Cheers!

Examples:

Input: ["ArrayStack", "push", "push", "top", "pop", "isEmpty"]

[[], [5], [10], [], [], []]

Output: [null, null, null, 10, 10, false]

Explanation:

ArrayStack stack = new ArrayStack();

stack.push(5);

stack.push(10);

stack.top(); // returns 10

stack.pop(); // returns 10

stack.isEmpty(); // returns false

Input: ["ArrayStack","isEmpty", "push", "pop", "isEmpty"]

[[], [], [1], [], []]

Output: [null, true, null, 1, true]

Explanation:

ArrayStack stack = new ArrayStack();

stack.push(1);

stack.pop(); // returns 1

stack.isEmpty(); // returns true

Input: ["ArrayStack", "isEmpty"]

[[], []]

Constraints

1 <= numbers of calls made <= 100
1 <= x <= 100

Hints

Calling pop() or top() on an empty stack should raise an appropriate exception.
Ensure isEmpty() accurately reflects whether the stack has elements.

Company Tags

Epic Games AMD Target MongoDB Activision Blizzard PayPal Goldman Sachs Airbnb Roblox Teladoc Health Siemens Healthineers Byju's Salesforce Alibaba American Express ARM Freshworks Red Hat Broadcom Rockstar Games Intel Docker Twilio Seagate Technology Unity Technologies Google Microsoft Amazon Meta Apple Netflix Adobe TCS Cognizant Accenture Infosys Capgemini Wipro

Intuition

Imagine you're working in a library, and there's a special shelf dedicated to books that are being frequently accessed. This shelf operates on a Last-In-First-Out (LIFO) principle, meaning the last book you put on the shelf is the first one you'll take off. This shelf can be thought of as a stack, and the following operations will help manage the books on this shelf.

Push Operation (push(int x)):

Think of adding a book to the top of the stack. Every time a new book arrives, you place it on the topmost spot available on the shelf. For instance, if the current stack of books is [Book1, Book2], and Book3 arrives, you place Book3 on top. The stack now looks like [Book1, Book2, Book3].

Pop Operation (pop()):

This operation is like removing the topmost book from the stack. The book that was last added (the one on the top) is the one you take off the shelf. Continuing with our example, if you perform a pop() operation, you remove Book3 from the stack. The stack now looks like [Book1, Book2].

Top Operation (top()):

Sometimes you just want to know which book is on top without removing it. The top() operation allows you to peek at the topmost book. If your stack is [Book1, Book2, Book3], calling top() will tell you that Book3 is on the top without removing it from the stack.

IsEmpty Operation (isEmpty()):

Before adding or removing books, you might want to check if the shelf is empty. The isEmpty() operation checks whether there are any books on the shelf. If there are no books, it returns true; otherwise, it returns false.

Approach

Declare an Array of Particular Size:

We need to initialize an array that will hold the elements of the stack. The size of the array is defined when the stack is created.

Define a Variable “Top” and Initialize It as -1:

The top variable keeps track of the index of the last added element in the stack. Initializing it to -1 indicates that the stack is empty.

Push Operation (push(int x)):

To push an element onto the stack, we increment the top index by one and insert the element at this position in the array. If the stack is full (i.e., top is equal to the last index of the array), we throw a stack overflow exception.

Pop Operation (pop()):

To pop an element from the stack, we check if the stack is not empty by ensuring top is not equal to -1. If the stack is empty, we throw a stack underflow exception. If the stack is not empty, we return the element at the top index and then decrement the top index by one.

Top Operation (top()):

To get the top element without removing it, we check if the stack is not empty. If the stack is empty, we throw an exception. If the stack is not empty, we return the element at the top index.

IsEmpty Operation (isEmpty()):

To check if the stack is empty, we simply check if the top index is -1.

Size Operation (size()):

To get the current size of the stack, we return top + 1.

Dry Run

#include <bits/stdc++.h>
using namespace std;

class ArrayStack {
private:
    // Array to hold elements
    int* stackArray;
    // Maximum capacity
    int capacity; 
     // Index of top element  
    int topIndex;   

public:
    // Constructor
    ArrayStack(int size = 1000) {
        capacity = size;
        stackArray = new int[capacity];
        // Initialize stack as empty
        topIndex = -1; 
    }

    // Destructor
    ~ArrayStack() {
        delete[] stackArray;
    }

    // Pushes element x 
    void push(int x) {
        if (topIndex >= capacity - 1) {
            cout << "Stack overflow" << endl;
            return;
        }
        stackArray[++topIndex] = x;
    }

    // Removes and returns top element
    int pop() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            // Return invalid value
            return -1; 
        }
        return stackArray[topIndex--];
    }

    // Returns top element
    int top() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return -1; 
        }
        return stackArray[topIndex];
    }

   /* Returns true if the 
   stack is empty, false otherwise*/
    bool isEmpty() {
        return topIndex == -1;
    }
};

// Main Function
int main() {
    ArrayStack stack;
    vector<string> commands = {"ArrayStack", "push", "push", "top", "pop", "isEmpty"};
    vector<vector<int>> inputs = {{}, {5}, {10}, {}, {}, {}};

    for (size_t i = 0; i < commands.size(); ++i) {
        if (commands[i] == "push") {
            stack.push(inputs[i][0]);
            cout << "null ";
        } else if (commands[i] == "pop") {
            cout << stack.pop() << " ";
        } else if (commands[i] == "top") {
            cout << stack.top() << " ";
        } else if (commands[i] == "isEmpty") {
            cout << (stack.isEmpty() ? "true" : "false") << " ";
        } else if (commands[i] == "ArrayStack") {
            cout << "null ";
        }
    }

    return 0;
}
import java.util.*;

class ArrayStack {
    // Array to hold elements
    private int[] stackArray;
    // Maximum capacity
    private int capacity;
    // Index of top element
    private int topIndex;

    // Constructor
    public ArrayStack(int size) {
        capacity = size;
        stackArray = new int[capacity];
        // Initialize stack as empty
        topIndex = -1;
    }

    public ArrayStack() {
        this(1000);
    }

    // Pushes element x 
    public void push(int x) {
        if (topIndex >= capacity - 1) {
            System.out.println("Stack overflow");
            return;
        }
        stackArray[++topIndex] = x;
    }

    // Removes and returns top element
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            // Return invalid value
            return -1;
        }
        return stackArray[topIndex--];
    }

    // Returns top element
    public int top() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return -1;
        }
        return stackArray[topIndex];
    }

    /* Returns true if the 
       stack is empty, false otherwise */
    public boolean isEmpty() {
        return topIndex == -1;
    }

    // Main function
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack();
        List<String> commands = Arrays.asList("ArrayStack", "push", "push", "top", "pop", "isEmpty");
        List<List<Integer>> inputs = Arrays.asList(Arrays.asList(), Arrays.asList(5), Arrays.asList(10), Arrays.asList(), Arrays.asList(), Arrays.asList());

        for (int i = 0; i < commands.size(); ++i) {
            switch (commands.get(i)) {
                case "push":
                    stack.push(inputs.get(i).get(0));
                    System.out.print("null ");
                    break;
                case "pop":
                    System.out.print(stack.pop() + " ");
                    break;
                case "top":
                    System.out.print(stack.top() + " ");
                    break;
                case "isEmpty":
                    System.out.print((stack.isEmpty() ? "true" : "false") + " ");
                    break;
                case "ArrayStack":
                    System.out.print("null ");
                    break;
            }
        }
    }
}
class ArrayStack:
    # Constructor
    def __init__(self, size=1000):
        # Array to hold elements
        self.stackArray = [0] * size
        # Maximum capacity
        self.capacity = size
        # Initialize stack as empty
        self.topIndex = -1

    # Pushes element x
    def push(self, x):
        if self.topIndex >= self.capacity - 1:
            print("Stack overflow")
            return
        self.topIndex += 1
        self.stackArray[self.topIndex] = x

    # Removes and returns top element
    def pop(self):
        if self.isEmpty():
            print("Stack is empty")
            # Return invalid value
            return -1
        top_element = self.stackArray[self.topIndex]
        self.topIndex -= 1
        return top_element

    # Returns top element
    def top(self):
        if self.isEmpty():
            print("Stack is empty")
            return -1
        return self.stackArray[self.topIndex]

    '''Returns true if the 
       stack is empty, false otherwise'''
    def isEmpty(self):
        return self.topIndex == -1

# Main function
if __name__ == "__main__":
    stack = ArrayStack()
    commands = ["ArrayStack", "push", "push", "top", "pop", "isEmpty"]
    inputs = [[], [5], [10], [], [], []]

    for i in range(len(commands)):
        if commands[i] == "push":
            stack.push(inputs[i][0])
            print("null", end=" ")
        elif commands[i] == "pop":
            print(stack.pop(), end=" ")
        elif commands[i] == "top":
            print(stack.top(), end=" ")
        elif commands[i] == "isEmpty":
            print("true" if stack.isEmpty() else "false", end=" ")
        elif commands[i] == "ArrayStack":
            print("null", end=" ")
class ArrayStack {
    // Constructor
    constructor(size = 1000) {
        // Array to hold elements
        this.stackArray = new Array(size);
        // Maximum capacity
        this.capacity = size;
        // Index of top element
        this.topIndex = -1; // Initialize stack as empty
    }

    // Pushes element x 
    push(x) {
        if (this.topIndex >= this.capacity - 1) {
            console.log("Stack overflow");
            return;
        }
        this.stackArray[++this.topIndex] = x;
    }

    // Removes and returns top element
    pop() {
        if (this.isEmpty()) {
            console.log("Stack is empty");
            // Return invalid value
            return -1;
        }
        return this.stackArray[this.topIndex--];
    }

    // Returns top element
    top() {
        if (this.isEmpty()) {
            console.log("Stack is empty");
            return -1;
        }
        return this.stackArray[this.topIndex];
    }

    /* Returns true if the 
       stack is empty, false otherwise */
    isEmpty() {
        return this.topIndex === -1;
    }
}

// Main function
const stack = new ArrayStack();
const commands = ["ArrayStack", "push", "push", "top", "pop", "isEmpty"];
const inputs = [[], [5], [10], [], [], []];

for (let i = 0; i < commands.length; ++i) {
    switch (commands[i]) {
        case "push":
            stack.push(inputs[i][0]);
            console.log("null");
            break;
        case "pop":
            console.log(stack.pop());
            break;
        case "top":
            console.log(stack.top());
            break;
        case "isEmpty":
            console.log(stack.isEmpty() ? "true" : "false");
            break;
        case "ArrayStack":
            console.log("null");
            break;
    }
}

Complexity Analysis

Time Complexity: O(1) because the individual stack operations take O(1). Space Complexity: O(N) for using a stack which is equivalent to the size of the array.

Code

Problem List

Implement Stack using Arrays

Examples:

Constraints

Hints

Company Tags

Editorial