栈
基于数组的实现
class ArrayStack: def __init__(self) -> None: self.__stack = [] def size(self): return len(self.__stack) def is_empty(self): if self.size() == 0: return True else: return False def push(self, val): self.__stack.append(val) def pop(self): if self.is_empty(): raise IndexError('栈中无数据') else: return self.__stack.pop(-1) def peek(self): if self.is_empty(): raise IndexError('栈中无数据') else: return self.__stack[-1] def to_list(self): return self.__stack
基于链表的实现
class ListNode: def __init__(self, value) -> None: self.val = value self.next = None class ListStack: def __init__(self) -> None: self.__peek = None self.__size = 0 def size(self): return self.__size def is_empty(self): if self.__peek == None: return True else: return False def push(self, val): node = ListNode(val) if self.is_empty(): self.__peek = node else: stack_next = self.__peek self.__peek = node self.__peek.next = stack_next self.__size += 1 def pop(self): if self.is_empty(): raise IndexError('栈中无数据') else: pop_listnode = self.__peek self.__peek = self.__peek.next return pop_listnode.val def peek(self): if self.is_empty(): raise IndexError('栈中无数据') else: return self.__peek.val def to_list(self): lst = [] peek = self.__peek while peek: lst.append(peek.val) peek = peek.next lst.reverse() return lst
两种类型栈的区别
- 时间效率
- 基于数组实现的栈在触发扩容时效率会降低，但由于扩容是低频操作，因此平均效率更高。
- 基于链表实现的栈可以提供更加稳定的效率表现。
- 空间效率
- 基于数组实现的栈可能造成一定的空间浪费。
- 由于链表节点需要额外存储指针，因此链表节点占用的空间相对较大。
- 我们不能简单地确定哪种实现更加节省内存，需要针对具体情况进行分析。
队列
基于数组的实现
class ArrayQueue: def __init__(self) -> None: self.__queue = [] self.__size = 0 def size(self): return self.__size def is_empty(self): if self.size() == 0: return True else: return False def push(self, val): self.__queue.append(val) self.__size += 1 def pop(self): if self.is_empty(): raise IndexError('队列无数据') else: val = self.__queue.pop(0) self.__size -= 1 return val def to_list(self): return self.__queue
基于链表的实现
class ListNode: def __init__(self, value) -> None: self.val = value self.next = None class ListQueue: def __init__(self) -> None: self.__front = None self.__rear = None self.__size = 0 def size(self): return self.__size def is_empty(self): if self.size() == 0: return True else: return False def push(self, value): node = ListNode(value) if self.is_empty(): self.__front = node self.__rear = node else: self.__rear.next = node self.__rear = node self.__size += 1 def pop(self): if self.is_empty(): raise IndexError('队列无数据') else: node = self.__front self.__front = self.__front.next self.__size -= 1 return node.val def to_list(self): lst = [] node = self.__front while node: lst.append(node.val) node = node.next return lst
双向队列
基于数组的实现
class ArrayDeque: def __init__(self) -> None: self.__deque = [] self.__size = 0 def size(self): return self.__size def is_empty(self): if self.size() == 0: return True else: return False def push(self, val, where): if where == 'front': self.__deque.insert(0, val) elif where == 'rear': self.__deque.insert(-1, val) self.__size += 1 def pop(self, where): if self.is_empty(): raise IndexError('队列无数据') else: if where == 'front': val = self.__deque.pop(0) elif where == 'rear': val = self.__deque.pop(-1) self.__size -= 1 return val def to_list(self): return self.__deque
基于链表的实现
class ListNode: def __init__(self, value) -> None: self.val = value self.next = None self.prev = None class ListDeque: def __init__(self) -> None: self.__front = None self.__rear = None self.__size = 0 def size(self): return self.__size def is_empty(self): if self.size() == 0: return True else: return False def push(self, value, where): node = ListNode(value) if self.is_empty(): self.__front = node self.__rear = node else: if where == 'front': self.__front.prev = node node.next = self.__front self.__front = node elif where == 'rear': self.__rear.next = node node.prev = self.__rear self.__rear = node self.__size += 1 def pop(self, where): if self.is_empty(): raise IndexError('队列无数据') else: if where == 'front': node = self.__front.next if node: self.__front.next = None self.__front = node self.__front.prev = None elif where == 'rear': node = self.__rear.prev if node: self.__rear.prev = None self.__rear = node self.__rear.next = None self.__size -= 1 def to_list(self): lst = [] node = self.__front while node: lst.append(node.val) node = node.next return lst
重点回顾
- 栈是一种遵循先入后出原则的数据结构，可通过数组或链表来实现。
- 从时间效率角度看，栈的数组实现具有较高的平均效率，但在扩容过程中，单次入栈操作的时间复杂度会降低至 𝑂(𝑛) 。相比之下，基于链表实现的栈具有更为稳定的效率表现。
- 在空间效率方面，栈的数组实现可能导致一定程度的空间浪费。但需要注意的是，链表节点所占用的内存空间比数组元素更大。
- 队列是一种遵循先入先出原则的数据结构，同样可以通过数组或链表来实现。在时间效率和空间效率的对比上，队列的结论与前述栈的结论相似。
- 双向队列是一种具有更高自由度的队列，它允许在两端进行元素的添加和删除操作。
