Как проверить, пуста ли очередь, когда мне нужно использовать два стека для формирования очереди? - PullRequest
Новая
       14

Как проверить, пуста ли очередь, когда мне нужно использовать два стека для формирования очереди?

0 голосов
/ 05 мая 2019

Моя домашняя работа должна использовать два стека для создания очереди. Теперь моя очередь может делать то, что задает вопрос, но выдает ошибку, когда тестовый пример использует цикл while для проверки, пуста ли очередь.

'' '

class Queue:
    def __init__(self):
        self.in_stack = Stack()#stack is provided for us
        self.out_stack = Stack()#stack is provided for us
    def is_empty(self):#I think this causes the error 
        if self.called1 == False:
            return True
    def enqueue(self, item):
        self.called1 = True
        self.in_stack.push(item)
    def dequeue(self):
        self.called = True
        while not self.in_stack.is_empty():
            self.out_stack.push(self.in_stack.pop())
        return self.out_stack.pop()
    def size(self):
        if self.called == True:
            return self.out_stack.size()
        else:
            return self.in_stack.size()
'''
'''
#test case
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)
while not q.is_empty():
  print(q.dequeue())
'''
'''
#test result
1#correct
2#correct
3#correct
4#correct
Traceback (most recent call last):
  File "C:\Users\Desktop\12.py", line 48, in <module>
    print(q.dequeue())
  File "C:\Users\Desktop\12.py", line 36, in dequeue
    return self.out_stack.pop()
  File "C:\Users\Desktop\12.py", line 15, in pop
    return self.list.pop()
IndexError: pop from empty list#don't know why it's still pop when the stack is empty
>>> 
'''

1 Ответ

0 голосов
/ 05 мая 2019

Хотя цель упражнения очень сомнительна (запутанный способ злоупотребления структурами данных), вы должны помнить разницу между стеком и очередью.Очередь - это структура «первым пришел - первым вышел», а стек - первым вышел последним.

Если вы вытаскиваете все элементы из одного стека и помещаете их в другой, вы делаете двойную инверсию.И их стеки FILO могут производить поведение FIFO как очередь.Но ...

Вы не можете ничего вытолкнуть во второй стек, если вы начали потреблять предметы, пока он не опустеет.

Так что держите в стеке для входящих элементов.Затем, как только у вас появится извлечение из второго стека, пока он не станет пустым, и тогда и только тогда вы перенесете элементы из стека 1 в стек 2 ... 

def _move_stack(self):
     while not self.in_stack.is_empty():

self.out_stack.push (self.in_stack.pop ()) 

def dequeue(self):

    If out_stack.is_empty():
        self._move_stack()


    return self.out_stack.pop()
...