Leetcode 232.用栈实现队列

Posted on |

232.用栈实现队列

题目

使用栈实现队列的下列操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

你只能使用标准的栈操作 — 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

方法

方法1：两个栈Push 每个操作O(N),Pop 每个操作O(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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class MyQueue(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.s1=[]
        self.s2=[]

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: void
        """
        while self.s1:
            self.s2.append(self.s1.pop())
        self.s1.append(x)
        while self.s2:
            self.s1.append(self.s2.pop())

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        return self.s1.pop()


    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        return self.s1[-1]

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return not self.s1



# 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()

方法2：两个栈Push 每个操作O(1)；Pop 每个操作O(1)

  • 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
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class MyQueue(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.s1=[]
        self.s2=[]

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: void
        """
        self.s1.append(x)

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        self.peek()
        return self.s2.pop()


    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2[-1]

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return not self.s1 and not self.s2


# 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()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class MyQueue(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.input=[]
        self.output=[]

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: void
        """
        self.input.append(x)


    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        self.peek()
        return self.output.pop()


    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if self.output==[]:
            while self.input!=[]:
                self.output.append(self.input.pop())
        return self.output[-1]


    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return self.input==[] and self.output==[]



# 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()