理解python中的堆栈和队列

2024-03-29 13:29:49 发布

您现在位置:Python中文网/ 问答频道 /正文

所以我得到了这个问题。考虑使用标准操作集的堆栈和队列类。使用Stack和Queue类,在调用mysteryFunction之前和调用mysteryFunction之后,它们中包含哪些项?

代码如下:

def mysteryFunction(s, q):
    q.enqueue('csc148')
    q.enqueue(True)
    q.enqueue(q.front())
    q.enqueue('abstract data type')

    for i in range(q.size()):
        s.push(q.dequeue())

    while not s.is_empty():
        q.enqueue(s.pop())


if __name__ == '__main__':
    s=Stack()
    q=Queue()

#About to call mysteryFunction
#What are contents of s and q at this point?
    mysteryFunction(s, q)
#mysteryFunction has been called.
#What are contents of s and q at this point?

我在理解面向对象编程时遇到了困难,因为我对这个主题还不熟悉。有没有链接可以分解堆栈和队列以及它们的作用?


Tags: andof标准队列queuestack堆栈contents
3条回答

一般来说,堆栈是后进先出,队列是后进先出。

在Python中,可以使用collections模块来测试堆栈和队列:

>>> from collections import deque
>>> stack = deque()
>>> stack.append(10)
>>> stack.append(20)
>>> stack.append(30)
>>> stack
deque([10, 20, 30])
>>> stack.pop()           # LIFO
30
>>> stack.pop()
20
>>> 
>>> queue = deque()
>>> queue.append(10)
>>> queue.append(20)
>>> queue.append(30)
>>> queue
deque([10, 20, 30])
>>> queue.popleft()       # FIFO
10
>>> queue.popleft()
20

要逐行测试此任务,以下是任务中使用的类(deque周围的包装器)的实现:

from collections import deque

class Queue(deque):
    enqueue = deque.append
    dequeue = deque.popleft
    def front(self):
        return self[-1]
    def size(self):
        return len(self)

class Stack(deque):
    push = deque.append
    def is_empty(self):
        return not self

有关详细信息,请参见以下链接:

Stack
Queue

从视觉上看,这两种数据结构可以通过以下方式看到:

堆栈:

Stack visual

说明:

这种数据结构有很多变化。然而,简单地说,正如我们在提供的图像中所观察到的,当您添加到这个数据结构时,您将放置在已经存在的内容之上,当您删除时,您也将从顶部获取。你可以把它看作是一堆书,从上往下一个一个地看。

排队

Queue visual

说明:

在这个特定的数据结构上也有一些变化,但是用简单的术语来说——正如您在提供的图像中看到的那样,当您向这个数据结构添加新元素时,新元素会进入开头,当您从要删除的列表中删除它的最后一个元素时。你可以把它想象成你在一家商店排队,站在很多人后面等着轮到你到柜台付款。

相关问题 更多 >