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

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();
    }
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
《L02 从零构建论坛系统》
以构建论坛项目 LaraBBS 为线索,展开对 Laravel 框架的全面学习。应用程序架构思路贴近 Laravel 框架的设计哲学。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!