Implementation of Stack and Queue in JavaScript with Application in Shunting-yard Algorithm

Fundamental Concepts of Data Structures

In computer science, data structures are methods of organizing and storing data that directly impact program performance and efficiency. Stacks and queues, as two fundamental linear data structures, play crucial roles in algorithm implementation and system design.

Stack Data Structure Implementation

Stacks follow the Last-In-First-Out (LIFO) principle, similar to stacking plates in real life. In JavaScript, we can easily implement stack functionality using arrays.

let stack = [];
stack.push(2);       // stack becomes [2]
stack.push(5);       // stack becomes [2, 5]
let i = stack.pop(); // stack becomes [2]
console.log(i);      // outputs 5

The above code demonstrates basic stack operations using arrays. The push method adds elements to the top of the stack, while the pop method removes the top element. Both operations have O(1) time complexity, ensuring efficient performance.

Queue Data Structure Implementation

Queues follow the First-In-First-Out (FIFO) principle, analogous to real-world排队 scenarios. JavaScript arrays can also be used to implement queues, but performance considerations must be noted.

let queue = [];
queue.push(2);          // queue becomes [2]
queue.push(5);          // queue becomes [2, 5]
let j = queue.shift();  // queue becomes [5]
console.log(j);         // outputs 2

Although the shift method can implement dequeue operations for queues, its time complexity is O(n), which may cause performance issues in large-scale data scenarios. Therefore, for high-performance applications, custom queue implementations are recommended.

Class-Based Implementation Approach

To provide better encapsulation and maintainability, we can use ES6 class syntax to implement stacks and queues.

class Stack {
    constructor() {
        this.items = [];
    }
    
    push(element) {
        this.items.push(element);
    }
    
    pop() {
        if (this.isEmpty()) {
            return "Stack is empty";
        }
        return this.items.pop();
    }
    
    isEmpty() {
        return this.items.length === 0;
    }
    
    peek() {
        return this.items[this.items.length - 1];
    }
}

class Queue {
    constructor() {
        this.items = [];
    }
    
    enqueue(element) {
        this.items.push(element);
    }
    
    dequeue() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        return this.items.shift();
    }
    
    isEmpty() {
        return this.items.length === 0;
    }
    
    front() {
        return this.items[0];
    }
}

Performance Analysis and Optimization

Performance is a critical factor when implementing stacks and queues. Array push and pop operations have O(1) time complexity, while shift operations have O(n) time complexity. For high-frequency queue operation scenarios, using linked lists or double-ended queues is recommended for performance optimization.

An optimized queue implementation can use objects to store elements, avoiding array reindexing:

class OptimizedQueue {
    constructor() {
        this.items = {};
        this.frontIndex = 0;
        this.rearIndex = 0;
    }
    
    enqueue(element) {
        this.items[this.rearIndex] = element;
        this.rearIndex++;
    }
    
    dequeue() {
        if (this.isEmpty()) {
            return "Queue is empty";
        }
        const element = this.items[this.frontIndex];
        delete this.items[this.frontIndex];
        this.frontIndex++;
        return element;
    }
    
    isEmpty() {
        return this.frontIndex === this.rearIndex;
    }
}

Application in Shunting-yard Algorithm

The shunting-yard algorithm is essential for converting infix expressions to postfix notation, where stacks play a critical role. The algorithm uses output queues and operator stacks to handle expression conversion.

function shuntingYard(expression) {
    const outputQueue = [];
    const operatorStack = [];
    const operators = {
        '+': 1, '-': 1, '*': 2, '/': 2, '^': 3
    };
    
    const tokens = expression.split(' ');
    
    tokens.forEach(token => {
        if (!isNaN(token)) {
            outputQueue.push(token);
        } else if (token in operators) {
            while (operatorStack.length > 0 && 
                   operators[operatorStack[operatorStack.length - 1]] >= operators[token]) {
                outputQueue.push(operatorStack.pop());
            }
            operatorStack.push(token);
        } else if (token === '(') {
            operatorStack.push(token);
        } else if (token === ')') {
            while (operatorStack.length > 0 && operatorStack[operatorStack.length - 1] !== '(') {
                outputQueue.push(operatorStack.pop());
            }
            operatorStack.pop();
        }
    });
    
    while (operatorStack.length > 0) {
        outputQueue.push(operatorStack.pop());
    }
    
    return outputQueue.join(' ');
}

Practical Application Scenarios

Stacks and queues have wide-ranging applications in software development:

• Stack Applications: Function call stacks, undo operations, expression evaluation, browser history
• Queue Applications: Task scheduling, message queues, breadth-first search, print queue management

Understanding the characteristics and implementation methods of these data structures helps developers choose the most appropriate solutions when facing specific problems.

Conclusion

JavaScript provides flexible ways to implement stack and queue data structures. Array implementations are simple and intuitive, suitable for most scenarios; class implementations offer better encapsulation; optimized implementations target high-performance requirements. In specific applications like the shunting-yard algorithm, proper use of these data structures can significantly improve algorithm efficiency and code quality. Developers should choose the most suitable implementation based on specific requirements while fully considering performance optimization factors.