Python实现栈、队列、与双端队列

栈

栈遵循后进先出的原则

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模块中的双端队列比较