首页 > 试题广场 > 用俩个栈模拟实现一个队列,如果栈的容量分别是O和P(O>
[单选题]
用俩个栈模拟实现一个队列,如果栈的容量分别是OP(O>P),那么模拟实现的队列最大容量是多少?
  • O+P
  • 2O+1
  • 2P+1
  • 2O-1
设stack1的容量是O,stack2的容量是P,(O>P),将stack1作为存储空间,stack2作为输出的缓冲空间。
1、将P个元素push到stack1中;
2、再将该P个元素pop到stack2中;(此时出栈的顺序就是队列前P个元素的出栈顺序)
3、将P+1个元素push到stack1中;
4、将P个元素pop到stack2中,先将stack1中剩余的元素pop,然后依次pop出stack2中的元素。
所以最终实现队列的最大容量是2P+1
发表于 2019-09-02 16:37:37 回复(5)
看到这个题,我们就要想到栈和队列的不同,所谓用两个栈实现一个队列是指,我们要实现队列的“尾插”和“头删”操作。首先,假如我们要插入一些数据“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)
短板效应+1。
发表于 2019-11-15 10:36:11 回复(0)
C 先压入p个进去s2存储栈,再压入p个入s2存储栈,最后pop出s1的最后一个元素,算出最大队列容量
发表于 2019-07-01 11:31:59 回复(0)
入栈操作分两步 ①往O中放入p个,将全部压入P中 ②往O中放入p+1个 因此,总容量为2p+1个 如果还不懂,可以看看出栈操作: 出栈操作分四步走 ❶P里面全出 ❷O里面出p个到P ❸出O中仅存的一个 ❹P里面全出
发表于 2019-12-13 11:40:08 回复(0)

有点像汉诺塔

发表于 2019-10-09 11:55:23 回复(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)