首页 > 试题广场 > 用俩个栈模拟实现一个队列,如果栈的容量分别是O和P(O>
[单选题]
用俩个栈模拟实现一个队列,如果栈的容量分别是OP(O>P),那么模拟实现的队列最大容量是多少?
  • O+P
  • 2O+1
  • 2P+1
  • 2O-1
C 先压入p个进去s2存储栈,再压入p个入s2存储栈,最后pop出s1的最后一个元素,算出最大队列容量
发表于 2019-07-01 11:31:59 回复(0)
看到这个题,我们就要想到栈和队列的不同,所谓用两个栈实现一个队列是指,我们要实现队列的“尾插”和“头删”操作。首先,假如我们要插入一些数据“abcd”,我们知道按照这个顺序队列出现的结果也是“abcd”,而栈会出现“dcba”,刚好相反,因此将该栈的到的数据在插入另外一个栈中就会出现我们想要的结果。因此,我们定义两个栈为“stack1”和“stack2”,栈1只用来插入数据,栈2用来删除数据栈1插入进来的数据。 下面举个栗子: (1):将队列中的元素“abcd”压入stack1中,此时stack2为空; (2):将stack1中的元素pop进stack2中,此时pop一下stack2中的元素,就可以达到和队列删除数据一样的顺序了; (3):可能有些人很疑惑,当stack2只pop了一个元素a时,satck1中可能还会插入元素e,这时如果将stack1中的元素e插入stack2中,在a之后出栈的元素就是e了,显然,这样想是不对的,我们必须规定当stack2中的元素pop完之后,也就是satck2为空时,再插入stack1中的元素。
发表于 2019-07-20 09:03:58 回复(0)
class queue:
    #长度为O+P的queue
        #python
    def __init__(self,O,P):
        # OP分别为stack1,stack2的最大长度
        self.__o = O
        self.__p = P
        self.__stack1 = []
        self.__stack2 = []
        
    def push(self,ele):
        # 压入元素
        if len(self.__stack1)==self.__o:
            while len(self.__stack2)<self.__p and len(self.__stack1)>0:
                self.__stack2.append(self.__stack1.pop())
        if len(self.__stack1)<self.__o:
            self.__stack1.append(ele)
        else:
            raise(Exception("QueueFullError"))
        
    def pop(self):
        #删除元素
        if len(self.__stack2)==0 :
            while(len(self.__stack1)>0):
                self.__stack2.append(self.__stack1.pop())
        try:
           self.__stack2.pop() 
        except:
            raise(Exception("QueueEmptyError"))


发表于 2019-08-06 23:02:01 回复(0)