剑指offer Stack Queue

剑指offer-用两个栈实现队列

Posted by franki on April 23, 2021

用两个栈实现队列

思路

1 入队的时候，把元素都放入到stack1，例如a b c依次输入的话{c, b, a}，c在栈顶，a在栈底 2 出队的时候，检查stack2是否为空，若为空，把stack1的元素依次出栈并在stack2依次入栈，如果是上述输入的话，即是stack1为空，stack2的序列为{a, b, c},a在栈顶，c在栈低，再把stack2出栈，就能模拟出a -> b -> c这样的出队顺序，即满足队列的先入先出的原则

代码

class Queue {
    stack1 = [];
    stack2 = [];
    appendTail(data) {
        this.stack1.push(data);
    }
    deleteHead() {
        if (this.stack2.length <= 0) {
            while (this.stack1.length > 0) {
                this.stack2.push(this.stack1.pop());
            }
        }
        if (this.stack2.length === 0) {
            throw new Error('no more data!');
        }
        this.stack2.pop();
        return this.stack2;
    }
}

复杂度分析

  • 时间复杂度: O(N)
  • 空间复杂度: O(N)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS