剑指offer 用两个栈实现队列

Posted on |

方法

Leetcode 232.用栈实现队列

方法1

队列是先进先出，栈是后进后出。这意味着新元素加入到栈底。将s1的元素转移到辅助栈s2中。然后将新加入的元素push到栈s2，再将所有元素弹出并push到s1

push
新加入的元素必须压入到栈底。将s1的所有元素转换为辅助栈s2中。新加入的元素push到s2中，并且所有元素被s2 pop掉再push到s1.

  • 时间复杂度：每个新加入的元素，都被push和pop两次。最后一个加入的元素，pop和push依次。因此，当队列长度是n，操作次数是4n+2，push和pop复杂度是O(1)
  • 空间复杂度：O(n)，需要额外的空间存储队列元素

pop
所有元素都是从栈s1 pop掉的。因为s1的栈顶总是第一个加入的元素front。队列的队头记作front

  • 时间复杂度和空间复杂度都是O(1)

empty
栈s1包含了所有的元素，所以只需要检查s1的size就可以得知队列是否为空

  • 时间复杂度和空间复杂度都是O(1)

peek
元素front总是保存在恒定的内存中，当push和pop才会改变

  • 时间复杂度和空间复杂度都是O(1)
  • front早就被计算，当peek时才返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.s1=[]
        self.s2=[]
    def push(self, node):
        # write code here
        while self.s1:
            self.s2.append(self.s1.pop())
        self.s1.append(node)
        while self.s2:
            self.s1.append(self.s2.pop())
    def pop(self):
        return self.s1.pop()
        # return xx

方法2

  • Push:新加入的元素总是被添加在s1的顶部，第一个元素始终作为队列的队头
  • Pop：队头元素在栈s1的栈底，要pop，只能将所有元素弹出并push到辅助栈s2（有助于存储s1的元素，以相反的顺序）。这样s1的栈底元素就位于s2的栈顶，此时可以简单的从s2弹出。当s2为空，再将s1的元素转移到s2
  • empty：栈s1和s2包含所有栈元素，检查s1和s2的size来判断队列是否为空
  • peek：当s2不空，队头元素位于s2的栈顶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.s1=[]
        self.s2=[]
    def push(self, node):
        # write code here
        self.s1.append(node)
    def pop(self):
        # return xx
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2.pop()