数据结构 | 栈和队列相互实现（含JS实现）

队列具有先进先出的特点，栈具有先进后出的特点，栈和队列互转是经常遇到的情况

参考LeetCode原题：

225. 用队列实现栈

232. 用栈实现队列

用队列实现栈

• push
• pop
• top
• empty

class MyStack {
    constructor() {
        this.queue1 = [];
        this.queue2 = [];
    }
    
    // push to back
    push(val) {
        this.queue2.push(val);
        
        while (this.queue1.length) {
            this.queue2.push(this.queue1.shift())
        }
        
        while (this.queue2.length) {
            this.queue1.push(this.queue2.shift());
        }
    }
    
    // 注意：因为是队列，所以只能是pop to front即使用shift()
    pop() {
        if (this.queue1.length) {
            return this.queue1.shift();
        }
    }
    
    // top：要获取的是栈顶元素，对应于队列是队尾元素
    top() {
        if (this.queue1.length) {
            return this.queue1[0];
        }
    }
    
    // empty 判断栈是否为空
    empty() {
        return !this.queue1.length
    }  
}

用栈实现队列

• push
• pop
• peek
• empty

class MyQueue {
    constructor() {
        this.stack1 = [];
        this.stack2 = [];
    }
    
    // push
    push(val) {
        this.stack1.push(val);
    }
    
    // pop from bcak 即使用pop方法
    pop() {
        if (!this.stack2.length) {
            while (this.stack1.length) {
                this.stack2.push(this.stack1.pop());
            };
        };
        return this.stack2.pop();
    }
    
    // 取出对头元素 栈只能从后面取，即栈顶元素，所以要交换
    peek() {
        if (!this.stack2.length) {
            while (this.stack1.length) {
                this.stack2.push(this.stack1.pop());
            };
        };
        return this.stack2[this.stack2.length -1];
    }
    
    // 判断为空
    empty() {
        return !this.stack1.length && !this.stack2.length;
    }
}