Java教程

算法设计与分析—用两个栈实现队列

本文主要是介绍算法设计与分析—用两个栈实现队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目描述:

用两个栈实现队列
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )

示例 1:
输入:
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
输出:[null,null,3,-1]

来源:力扣(LeetCode)


算法实现:

解题思路
两个栈A,B 模拟实现一个队列,A栈作为输入,B栈作为输出用。
1、入栈时直接加入到A栈中。
2、出栈时:
(1)B栈有数据,直接在B栈中pop
(2)B栈中没有数据,先将A栈的所有数据倒入B栈中,再从B栈中pop
(3)B栈和A栈中都没有数据,直接返回-1

class CQueue(object):
    def __init__(self):
        self._list1=list()
        self._list2=list()

    def appendTail(self, value):
        """
        :type value: int
        :rtype: None
        """
        self._list1.append(value)


    def deleteHead(self):
        """
        :rtype: int
        """
        _len1=len(self._list1)
        _len2=len(self._list2)

        if _len1==0 and _len2==0:
            return -1;
        elif _len2==0:
            for i in range(_len1):
                self._list2.append(self._list1.pop())
        return self._list2.pop()
这篇关于算法设计与分析—用两个栈实现队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!