Skip to content

stack.md

Latest commit

 

History

History
478 lines (348 loc) · 7.27 KB

stack.md

File metadata and controls

478 lines (348 loc) · 7.27 KB
Raw

Stack

Implement Stack (array-based)

class Stack {
    constructor() {
        this.items = [];
    }

    push(value) {
        this.items.push(value)
    }

    pop() {
        if (this.isEmpty()) {
            return 'Stack underflow';
        }
        return this.items.pop();
    }

    peek() {
        return this.items[this.items.length - 1]
    }

    isEmpty() {
        return this.items.length === 0;
    }

    size() {
        return this.items.length;
    }
}

const stack = new Stack();

stack.push(30);
stack.push(40);
stack.push(50);
stack.push(60);

console.log(stack.pop());
console.log(stack.size())
console.log(stack.peek());

Min Stack

Track the minimum element in O(1) using a second stack.

class MinStack {
    constructor() {
        this.stack = []
        this.minStack = []
    }

    push(x) {
        this.stack.push(x);

        if (this.minStack.length == 0 ||
            x <= this.minStack[this.minStack.length - 1]) {
            this.minStack.push(x)
        }
    }

    pop() {
        let removed = this.stack.pop()

        if (removed == this.minStack[this.minStack.length - 1]) {
            this.minStack.pop()
        }

        return removed
    }

    top() {
        return this.stack[this.stack.length - 1]
    }

    getMin() {
        return this.minStack[this.minStack.length - 1]
    }
}

const m = new MinStack()

m.push(10)
m.push(30)
m.push(4)
m.push(55)
m.push(2)

console.log('min:', m.getMin());
m.pop()
console.log(m.stack)
console.log(m.getMin())

Reverse a String Using Stack

function reverseString(str) {
    let reverse = ''
    let stack = [];

    for (let char of str) {
        stack.push(char)
    }

    while (stack.length > 0) {
        reverse += stack.pop()
    }
    return reverse;
}

console.log(reverseString('the world is beautiful'));

Reverse Each Word in a String

function reverseEachWord(str) {
    let reverse = ''
    let stack = [];

    for (let char of str) {
        if (char !== ' ') {
            stack.push(char);
        } else {
            while (stack.length > 0) {
                reverse += stack.pop();
            }
            reverse += ' ';
        }
    }

    while (stack.length > 0) {
        reverse += stack.pop()
    }
    return reverse
}

console.log(reverseEachWord('hello world'));

Stack Implemented Using Linked List

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedListStack {
    constructor() {
        this.head = null;
    }

    push(data) {
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
    }

    pop() {
        if (!this.head) {
            return null;
        }
        let removed = this.head.data
        this.head = this.head.next
        return removed
    }

    peek() {
        return this.head ? this.head.data : null;
    }

    display() {
        let current = this.head;
        while (current) {
            console.log(current.data);
            current = current.next
        }
    }
}

const llStack = new LinkedListStack();

llStack.push(23);
llStack.push(33);
llStack.push(44);
llStack.push(332);
let removed = llStack.pop();

console.log('removed element is :', removed)
llStack.display();

Reverse a Stack Using Only Its Own Operations — O(n²)

function reverseStack(stack) {
    if (stack.length === 0) return;

    let top = stack.pop();
    reverseStack(stack);
    insertAtBottom(stack, top);
}

function insertAtBottom(stack, value) {
    if (stack.length === 0) {
        stack.push(value);
        return;
    }

    let top = stack.pop();
    insertAtBottom(stack, value);
    stack.push(top);
}

let numbers = [1, 2, 3, 4];

reverseStack(numbers);

console.log(numbers);

Implement Stack Using Queue

class StackUsingQueue {
    constructor() {
        this.queue = [];
    }

    push(x) {
        this.queue.push(x);
        for (let i = 0; i < this.queue.length - 1; i++) {
            this.queue.push(this.queue.shift()); // Take the first element, remove it, and add it to the end.
        }
    }

    pop() {
        return this.queue.shift() ?? null;
    }

    peek() {
        return this.queue[0] ?? null;
    }
}

let s = new StackUsingQueue();

s.push(10);
s.push(20);
s.push(30);
s.pop()

console.log(s.queue)

Undo–Redo Operations in a Text Editor

let text = ''
let undoStack = [];
let redoStack = [];

function type(newText) {
    undoStack.push(text);
    text += newText;
    redoStack = []
}

function undo() {
    if (undoStack.length === 0) return;
    redoStack.push(text);
    text = undoStack.pop();
}

function redo() {
    if (redoStack.length === 0) return;
    undoStack.push(text);
    text = redoStack.pop();
}

type('hello ');
type('world ');
type('is')

console.log(text);

undo()
console.log('after undo :', text)

redo();
console.log('after redo:', text)

Remove Nth Element From a Stack Using Recursion

function removeNth(stack, n) {
    if (stack.length == 0) return;

    if (n == 1) {
        stack.pop()
        return
    }

    let top = stack.pop()

    removeNth(stack, n - 1)

    stack.push(top)
}

const stack1 = [1, 12, 3, 14, 5]

removeNth(stack1, 4)

console.log(stack1)

Delete a Specific Element From Stack

function deleteElement(stack, x) {
    if (stack.length == 0) return;

    let top = stack.pop();

    if (top !== x) {
        deleteElement(stack, x);
        stack.push(top)
    } else {
        deleteElement(stack, x)
    }
}

let stack2 = [1, 2, 3, 4, 5];

deleteElement(stack2, 3);

console.log(stack2);

Delete the Middle Element From Stack

function deleteMiddle(stack) {
    let middle = Math.floor(stack.length / 2);
    let temp = [];

    for (let i = 0; i < middle; i++) {
        temp.push(stack.pop())
    }

    stack.pop()

    while (temp.length > 0) {
        stack.push(temp.pop())
    }
}

let stack3 = [1, 2, 3, 4, 5];

deleteMiddle(stack3);

console.log(stack3);

Remove Duplicate Elements From Stack

function removeDuplicates(stack) {
    let seen = new Set();
    let tempStack = [];

    while (stack.length > 0) {
        let curr = stack.pop();

        if (!seen.has(curr)) {
            seen.add(curr);
            tempStack.push(curr);
        }
    }

    return tempStack;
}

const stack4 = [1, 5, 2, 3, 4, 5, 1, 2];

let result1 = removeDuplicates(stack4);

console.log(result1);

Sort a Stack Using a Temporary Stack

function sortStack(stack) {
    let tempStack = [];

    while (stack.length > 0) {
        let temp = stack.pop();

        while (
            tempStack.length > 0 &&
            tempStack[tempStack.length - 1] > temp
        ) {
            stack.push(tempStack.pop());
        }

        tempStack.push(temp);
    }

    return tempStack;
}

let stack5 = [34, 3, 31, 98, 92, 23];

let result2 = sortStack(stack5);

console.log(result2);

Insert an Element Into a Sorted Stack

function insertSorted(stack, target) {
    if (stack.length === 0 || stack[stack.length - 1] <= target) {
        stack.push(target);
        return
    }

    let top = stack.pop()

    insertSorted(stack, target)

    stack.push(top)
}

const stack6 = [10, 20, 30]

insertSorted(stack6, 25)

console.log(stack6)