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

Key Operations of a Stack

Explore fundamental operations of a stack data structure including push, pop, peek, isEmpty, and isFull. Understand how these functions work with both array and linked list implementations in JavaScript, and learn their constant time complexity for efficient data manipulation.

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.

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

Javascript (babel-node)
class Stack {
    constructor(capacity = 10) {
        /** Initialize an empty stack with given capacity */
        this.capacity = capacity; // Maximum number of elements
        this.data = new Array(capacity).fill(null); // Array to store elements
        this.top = -1; // Index of top element (-1 means empty)
    }
    isEmpty() {
        /** Check if the stack is empty */
        return this.top === -1;
    }
}
// Create a stack
const stack = new Stack(10);
console.log("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.

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

Javascript (babel-node)
class Stack {
    constructor(capacity = 10) {
        this.capacity = capacity; // Maximum number of elements
        this.data = new Array(capacity).fill(null); // Array to store elements
        this.top = -1; // Index of top element (-1 means empty)
    }
    isEmpty() {
        return this.top === -1;
    }
    isFull() {
        /** Check if the stack is full */
        return this.top === this.capacity - 1;
    }
}
// Create a stack with capacity 5
const stack = new Stack(5);
// Simulate a full stack with elements: [88, 95, 72, 80, 91]
stack.top = 4; // top index is 4
console.log("Is stack full?", stack.isFull()); // Output: true (stack is full)
console.log("Simulating popping one element from the stack");
stack.top = 3; // top index is now 3
console.log("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.

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

Javascript (babel-node)
class Stack {
    constructor(capacity = 10) {
        this.capacity = capacity; // Maximum number of elements
        this.data = new Array(capacity).fill(null); // Array to store elements
        this.top = -1; // Index of top element (-1 means empty)
    }
    push(value) {
        /** Add an element to the top of the stack */
        // Check if stack is full
        if (this.isFull()) {
            console.log("Stack Overflow! Cannot push element.");
            return false;
        }
        // Increment top and add the element
        this.top += 1;
        this.data[this.top] = value;
        return true;
    }
    isEmpty() {
        return this.top === -1;
    }
    isFull() {
        return this.top === this.capacity - 1;
    }
}
// Create a stack with capacity 10
const 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.log(`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.

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

Javascript (babel-node)
class Stack {
    constructor(capacity = 10) {
        /** Initialize an empty stack with given capacity */
        this.capacity = capacity; // Maximum number of elements
        this.data = new Array(capacity).fill(null); // Array to store elements
        this.top = -1; // Index of top element (-1 means empty)
    }
    pop() {
        /** Remove and return the top element */
        // Check if stack is empty
        if (this.isEmpty()) {
            console.log("Stack Underflow! Cannot pop from empty stack.");
            return null;
        }
        // Get the top element
        const value = this.data[this.top];
        // Decrement top
        this.top -= 1;
        return value;
    }
    isEmpty() {
        return this.top === -1;
    }
    isFull() {
        return this.top === this.capacity - 1;
    }
    push(value) {
        if (this.isFull()) {
            console.log("Stack Overflow! Cannot push element.");
            return false;
        }
        this.top += 1;
        this.data[this.top] = value;
        return true;
    }
}
// Create a stack and push elements: [88, 95, 72, 80, 91]
const stack = new Stack(10);
stack.push(88);
stack.push(95);
stack.push(72);
stack.push(80);
stack.push(91);
// Pop elements
console.log(stack.pop()); // Output: 91, Stack now: [88, 95, 72, 80]
console.log(stack.pop()); // Output: 80, Stack now: [88, 95, 72]
console.log(stack.pop()); // Output: 72, Stack now: [88, 95]
console.log(`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 simply return the value at the top ...