在python中实现堆栈和队列而不使用任何模块的最佳方法是什么?

2024-05-13 00:21:38 发布

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

我已经尝试了collections.dequequeue.Lifoqueue来实现堆栈和队列,虽然它们都很好,但我想从头开始实现它。那么,根据时间和空间的复杂性,哪种方法是最好的?我已经尝试过通过单链表和python列表函数来实现它。还有比这更好的方法吗


Tags: 方法函数列表队列queue堆栈时间空间
1条回答
网友
1楼 · 发布于 2024-05-13 00:21:38

这是队列。我评论了每个操作的时间复杂性

class QueuesArray:
    def __init__(self):
        self._data=[]
    def __len__(self): # O(1)
        return len(data)
    def isempty(self): # O(1)
        return len(self._data)==0
    def enqueue(self,e): #O(1)
        self._data.append(e)
        return e
    def dequeue(self): # O(1)
        if self.isempty():
            return ValueError("")
        return self._data.pop(0) # O(1)
    def first(self): # O(1)
        if self.isempty():
            print ('Queue is empty')
        return self._data[0]

下面是堆栈:

class StacksArray:
    def __init__(self):
        self._data=[]
    def __len__(self): # O(1)
        return len(self._data)
    def isempty(self): # O(1)
        return len(self._data)==0
    def push(self,e): # O(1)
        self._data.append(e)
        return e
    def pop(self): # O(1)+O(1)
        if self.isempty(): # O(1)
            print('stack is empty')
            raise IndexError
        else:
            return self._data.pop() # O(1)
    def top(self): # O(1)+O(1)
        if self.isempty(): # O(1)
            print('stack is empty')
            raise IndexError
        return self._data[-1] # O(1)

相关问题 更多 >