python 通过双栈实现队列

忘是亡心i 2022-05-23 09:06 219阅读 0赞

# 开始做法 #

# coding:utf-8
    
    # !/usr/bin/env python
    
    # Time: 2018/6/6 9:32
    
    # Author: sty
    
    # File: stack_queue.py
    
    
    class Solution():
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
    
        def push(self, data):
            self.stack1.append(data)
    
        def pop(self):
            if len(self.stack1) == 0 and len(self.stack2) == 0:
                return []
            elif len(self.stack2) == 0:
                while len(self.stack1) != 0:
                    self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

# 优化做法 #

减少了一次stack2的入栈和出栈操作

class Solution():
        def __init__(self):
            self.stack1 = []
            self.stack2 = []
    
        def push(self, data):
            self.stack1.append(data)
    
        def pop(self):
            if len(self.stack1) == 0 and len(self.stack2) == 0:
                return []
            elif len(self.stack2) == 0:
                while len(self.stack1) != 1:
                    self.stack2.append(self.stack1.pop())
                # 减少了一次stack2的入栈和出栈操作
                return self.stack1.pop()
            return self.stack2.pop()

# 全部操作合集 #

class MyQueue:
    
        def __init__(self):
            """ Initialize your data structure here. """
            self.stack1 = []
            self.stack2 = []
    
        def push(self, x):
            """ Push element x to the back of queue. :type x: int :rtype: void """
            self.stack1.append(x)
    
        def pop(self):
            """ Removes the element from in front of queue and returns that element. :rtype: int """
            if len(self.stack1) == 0 and len(self.stack2) == 0:
                return None
            else:
                if len(self.stack2) == 0:
                    while len(self.stack1) != 1:
                        self.stack2.append(self.stack1.pop())
                    return self.stack1.pop()
                else:
                    return self.stack2.pop()
    
        def peek(self):
            """ Get the front element. :rtype: int """
            if len(self.stack2) == 0 and len(self.stack1) == 0:
                return None
            else:
                if len(self.stack2) == 0:
                    return self.stack1[0]
                else:
                    return self.stack2[-1]
    
        def empty(self):
            """ Returns whether the queue is empty. :rtype: bool """
            if len(self.stack1) == 0 and len(self.stack2) == 0:
                return True
            else:
                return False

# 参考文档 #

[https://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html][https_www.cnblogs.com_wanghui9072229_archive_2011_11_22_2259391.html]  
[https://blog.csdn.net/slibra\_L/article/details/78098683][https_blog.csdn.net_slibra_L_article_details_78098683]  
[https://leetcode.com/problems/implement-queue-using-stacks/description/][https_leetcode.com_problems_implement-queue-using-stacks_description]

[https_www.cnblogs.com_wanghui9072229_archive_2011_11_22_2259391.html]: https://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html
[https_blog.csdn.net_slibra_L_article_details_78098683]: https://blog.csdn.net/slibra_L/article/details/78098683
[https_leetcode.com_problems_implement-queue-using-stacks_description]: https://leetcode.com/problems/implement-queue-using-stacks/description/