代码随想录算法训练营day10

Leetcode232 用栈实现队列

链接：232. 用栈实现队列 - 力扣（LeetCode）

首先大家要知道：队列的模式是先进先出。

如下图所示 

 （来自代码随想录）

如图所示，这是就是我们题目要求的用两个栈实现队列 

我们可以用第一个栈来储存当前队列出来的元素 

然后从第一个栈中在弹出 再次添加第二个栈中 这样子就完成了他们顺序的交换

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

代码：

#
# @lc app=leetcode.cn id=232 lang=python3
#
# [232] 用栈实现队列
#

# @lc code=start



class MyQueue:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []


    def push(self, x: int) -> None:
        self.stack1.append(x)

    def pop(self) -> int:
        if self.empty():
            return None
        if self.stack2:
            return self.stack2.pop()
        else:
            for i in range(len(self.stack1)):
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

    def peek(self) -> int:
        """peek只是取到栈顶元素的值 并不会删除元素 但是pop会删除栈顶元素 
        所以这里pop出来了 要给添加回去"""
        res = self.pop()
        self.stack2.append(res)
        return res 


    def empty(self) -> bool:
        return not (self.stack1 or self.stack2)




# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
# @lc code=end

Leetcode225:用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

 首先要知道 如果直接用两个队列(先进先出的规则) 去实现栈（先进后出的规则） 并不能直接改变顺序，也就是说从第一个队列弹出来的数据加入到第二个队列中，顺序并没有发生变化。

所以这里只能采取交换的方式，例如说 1234 这四个元素

然后定义一个queue_in&queue_out分别代表进来和出去

我取123这三个并不包括末尾元素 先放到out里面 然后当下 我们dequq_in的队列里面只剩一个元素4，我们直接让当下的deque_in,deque_out = deque_out,deque_in 完成交换。那么就是说当前out队列中也是有一个元素4，然后直接弹出。我们就完成了我们的弹出栈顶元素也就是pop的操作了，在这之前要判断是否为空哦~并且我们的边界条件循环到哪里要清楚~只选取到从头开始到最后一个元素的前一个 所以我们len(queue_in)需要-1

那我们的peek操作呢？

首先要清楚 peek是只获取值，但是不弹出哦 

所以我们把in里的数据弹出获取到了之后要重新添加回去！

最后判断是否为空操作！

因为deque_in是我们储存数据的地方所以只需要判断他的长度是否等于0就可以啦~

代码：

#
# @lc app=leetcode.cn id=225 lang=python3
#
# [225] 用队列实现栈
#

# @lc code=start
from collections import deque


class MyStack:

    def __init__(self):
        self.queue_in = deque()
        self.queue_out = deque()

    def push(self, x: int) -> None:
        #直接添加就好了
        
        self.queue_in.append(x)



    def pop(self) -> int:
        """任何时候都要确认不为空"""
        if self.empty():
            return None
        for i in range(len(self.queue_in)-1):
            self.queue_out.append(self.queue_in.popleft())
        """这里做了交换之后 因为in queue里面除了最后一个元素 前面的元素都被转移到了out里
        然后in和out做一个交换 最后直接返回当前的out.popleft()就是我们的栈顶元素了"""
        self.queue_in,self.queue_out = self.queue_out,self.queue_in
        return self.queue_out.popleft()

    def top(self) -> int:
        """同上"""
        if self.empty():
            return None
        """因为只有in是用来保存数据的 所以直接返回-1就可以了"""
        return self.queue_in[-1]


    def empty(self) -> bool:
        """因为只有in里面存了数据 所以只需要判断in里面是不是为空就好了"""
        return len(self.queue_in)==0


# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
# @lc code=end

总结：

这两个思路比较清晰 图像动手画画也比较容易理解 算是对栈和队列实现的基本功的考察 

要勤加练习