代码随想录算法训练营第八天 | leetcode：用栈实现队列,用队列实现栈

_zzh 的个人博客 / 0 / 0 / 创建于 1年前 / 更新于 1年前

Problem: 232. 用栈实现队列 #

#需要注意的地方

出栈时，需要把入栈的数据全部装进出栈，否则会导致数据错误。

解题方法#

使用两个栈，一个入栈对应队列进数据，一个出栈对应队列出数据。

复杂度#

时间复杂度:

push 和 empty 为 O (1), pop 和 peek 为 O (n)

空间复杂度:

O(n)

code#

 class MyQueue {
    /**
     */
    private $stackIn;
    private $stackOut;
    function __construct() {
        $this->stackIn = new SplStack();
        $this->stackOut = new SplStack();
    }

    /**
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        $this->stackIn->push($x);
    }

    /**
     * @return Integer
     */
    function pop() {
        $res = [];
        //判断出栈是否为空，为空查询入栈是否有数据，有数据则全部转入到出栈。
        //这里处理的是栈的top与pop不是队列的。
        if($this->stackOut->isEmpty()){
            while(!$this->stackIn->isEmpty()){
                // $this->stackOut->push($this->stackIn->top());
                // $this->stackIn->pop();
                $this->stackOut->push($this->stackIn->pop());
            }
        }
        $res = $this->stackOut->pop();
        // $this->stackOut->pop();
        return $res;
    }

    /**
     * @return Integer
     */
    function peek() {
        $res = $this->pop();
        $this->stackOut->push($res);
        return $res;
    }

    /**
     * @return Boolean
     */
    function empty() {
        //判断队列是否为空需要把入栈和出栈一起判断
        return $this->stackIn->isEmpty() && $this->stackOut->isEmpty();
    }
}

Problem: 225. 用队列实现栈 #

需要注意的地方#

SplQueue 继承自 SplDoublyLinkedList。因此，SplQueue 的对象支持方法 push（）和 pop（）。但请注意，如果您在 SplQueue 对象上使用 push（）和 pop（）方法，它的行为就像堆栈而不是队列。因此，请确保在 SplQueue 对象上只使用入队列 enqueue () 和出队列 dequeue () 方法，而不是 push（）和 pop（）方法

另外出队列方向是头部，栈顶是栈的头部，所以当入队列后，队列的尾部对应栈顶，但这里因为 SplQueue 继承自 SplDoublyLinkedList。它的行为就像堆栈而不是队列。top () 与 bottom () 指向也符合堆栈而不是队列。因此当需要指向栈头部时，直接使用 top () 即可。

解题方法#

关键点：把队列除了末尾元素，全部弹出然后重新入队列，最后一个元素即是栈顶所需要弹出的数据。如此循环，即弹出顺序与栈相同。

复杂度#

时间复杂度:

pop 为 O (n)，其他为 O (1)

空间复杂度:

O(n)

code#

class MyStack {
    private $queue;
    /**
     * SplQueue继承自SplDoublyLinkedList。因此，SplQueue的对象支持方法push（）和pop（）。
     * 但请注意，如果您在SplQueue对象上使用push（）和pop（）方法，它的行为就像堆栈而不是队列。
     * top()与bottom()指向也符合堆栈而不是队列
     * 因此，请确保在SplQueue对象上只使用入队列enqueue()和出队列dequeue()方法，而不是push（）和pop（）方法。
     */
    function __construct() {
        $this->queue = new SplQueue();
    }

    /**
     * @param Integer $x
     * @return NULL
     */
    function push($x) {
        $this->queue->enqueue($x);
    }

    /**
     * @return Integer
     */
    function pop() {
        $result = [];
        $size = $this->queue->count();
        //需要保留末尾元素 先减减
        $size--;
        //把队列除了末尾元素，全部弹出然后重新入队列，最后一个元素即是栈所需要弹出的数据
        while($size--){
            $this->queue->enqueue($this->queue->dequeue());
        }
        $result = $this->queue->dequeue();
        return $result;
    }

    /**
     * @return Integer
     */
    function top() {
        return $this->queue->top();
    }

    /**
     * @return Boolean
     */
    function empty() {
        return $this->queue->isEmpty();
    }
}