栈
栈遵循后进先出的原则
image.png
S是一个抽象数据类型，表示栈
- S.push() : 向栈顶添加元素；
- S.pop() ：移除栈顶元素，并返回栈顶元素，如果栈为空，则返回错误；
- S.top() ：在不移除栈顶元素的条件下，返回栈顶元素；如果栈为空，则返回错误；
- S.is_empty:判断栈是否为空；
-
len(S) : 栈的长度
栈方法与列表方法对比：
dui
python中用列表实现栈
class ArrayStack:
"""LIFO Stack implementation using a Python list as underlying storage."""
def __init__(self):
"""Create an empty stack."""
self._data = [] # nonpublic list instance
def __len__(self):
"""Return the number of elements in the stack."""
return len(self._data)
def is_empty(self):
"""Return True if the stack is empty."""
return len(self._data) == 0
def push(self, e):
"""Add element e to the top of the stack."""
self._data.append(e) # new item stored at end of list
def top(self):
"""Return (but do not remove) the element at the top of the stack.
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise LookupError('Stack is empty')
return self._data[-1] # the last item in the list
def pop(self):
"""Remove and return the element from the top of the stack (i.e., LIFO).
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise LookupError('Stack is empty')
return self._data.pop() # remove last item from list
队列
队列遵循先进先出原则
Q是一个抽象数据类型，表示队列
- Q.enqueue (e) : 向队列顶添加元素；
- Q.dequeue() ：移除队列第一个元素，并返回队列第一个元素，如果队列为空，则返回错误；
- Q.first() ：在不移除队列第一个元素的条件下，返回队列第一个元素；如果队列为空，则返回错误；
- Q.is_empty:判断队列是否为空；
- len(Q) : 队列的长度
用python 实现队列
class ArrayQueue:
"""FIFO queue implementation using a Python list as underlying storage."""
DEFAULT_CAPACITY = 10 # moderate capacity for all new queues
def __init__(self):
"""Create an empty queue."""
self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
self._size = 0
self._front = 0
def __len__(self):
"""Return the number of elements in the queue."""
return self._size
def is_empty(self):
"""Return True if the queue is empty."""
return self._size == 0
def first(self):
"""Return (but do not remove) the element at the front of the queue.
Raise Empty exception if the queue is empty.
"""
if self.is_empty():
raise LookupError('Queue is empty')
return self._data[self._front]
def dequeue(self):
"""Remove and return the first element of the queue (i.e., FIFO).
Raise Empty exception if the queue is empty.
"""
if self.is_empty():
raise LookupError('Queue is empty')
answer = self._data[self._front]
self._data[self._front] = None # help garbage collection
self._front = (self._front + 1) % len(self._data)
self._size -= 1
return answer
def enqueue(self, e):
"""Add an element to the back of queue."""
if self._size == len(self._data):
self._resize(2 * len(self.data)) # double the array size
avail = (self._front + self._size) % len(self._data)
self._data[avail] = e
self._size += 1
def _resize(self, cap): # we assume cap >= len(self)
"""Resize to a new list of capacity >= len(self)."""
old = self._data # keep track of existing list
self._data = [None] * cap # allocate list with new capacity
walk = self._front
for k in range(self._size): # only consider existing elements
self._data[k] = old[walk] # intentionally shift indices
walk = (1 + walk) % len(old) # use old size as modulus
self._front = 0 # front has been realigned
双端队列
D表示双端队列
- D.add_first(e):向双端队列前面插入元素e
- D.add_last(e): 向双端队列后面插入元素e
- D.delete_first():删除双端队列第一个元素
- D.delete_last():删除双端队列最后一个元素
- D.first():返回双端队列的第一个元素
- D.last():返回双端队列的最后一个元素
- D.is_empty():判断双端队列是否为空
-
len(D):返回双端队列的长度
双端队列与Python 标准collections模块中的双端队列比较
网友评论