堆栈和队列

• 堆栈
• 队列

堆栈

特点：LIPO，后进先出
操作：

• 推Push：将项添加到堆栈的顶部，隐藏堆栈上已经存在的任何项
• Pop：从堆栈顶部移除一个项目，并将此值返回给调用者
• peak：返回栈顶元素

堆栈既可以用数组，也可以用链表来实现。

对于python，没有LinkedList这种基本数据结构，需要重新实现。
可以用List方便地实现stack。

注：我们把List最后一个元素作为栈顶元素。因为这样数组操作都是O(1)。

class ArrayStack(object):
    # 数组实现堆栈
    def __init__(self):
        self._data = []
    def __len__(self):
        return len(self._data)
    def is_empty(self):
        return len(self._data) == 0
    # O(1)
    def push(self, element):
        self._data.append(element)
    # O(1)
    def top(self):
        if self.is_empty():
            raise ValueError(' Stack is empty! ' )
        return self._data.pop()
    # O(1)
    def pop(self):
        if self.is_empty():
            raise ValueError(' Stack is empty! ' )
        return self._data.pop()
     def printStack(self):
            for i in range(len(self._data)):
                print(self._data[i], end = ' ')
            print()

队列

• 先进先出（FIFO)
• 操作
  • Enqueue（insert)：将一个项目添加到队列的末尾
  • Dequeue(remove)：从队列前面移除一个项目

队列可以通过循环数组或链表轻松实现

class ArrayQueue:
    DEFAULT_CAPACITY = 10
    def __init__(self):
        self._data = [None] * ArrayQueue.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0
    def __len__(self):
        return self._size
    def is_empty(self):
        return self._size == 0
    def first(self):
        if self.is_empty():
            raise ValueError( 'Queue is empty' )
        return Self._data[self._front]
    def dequeue(self):
        if self.is_empty():
            raise ValueError( 'Queue is empty' )
        answer = self._data[self._front]
        self._data[self._front] = None
        self._front = (self._front + 1) % len(self._data)
        self._size -= 1
        return answer
    def enqueue(self, e):
        if self._size == len(self._data):
            self._resize(2 * len(self._data))
        pos = (self._front + self._size) % len(self._data)
        self._data[pos] = e
        self._size += 1
    def resize(self, cap):
        old = self._data
        self._data = [None] * cap
        walk = self._front
        for k in range(self._size):
            self._data[k] = old[walk]
            walk = (1 + walk) % len(old)
        self._front = 0
    def printQueue(self):
        for i in range(self._size):
            pos = (self._front + self._size - 1 - i) % len(self._data)
            print(self._data[pos], end = ' ')
         print()

python内置的堆栈和队列

from collections import deque

可以理解为双端队列，支持堆栈和队列的操作。deque = stack + queue

支持操作：

• append
• appendleft
• pop
• popleft
• …

题目练习

1.使用堆栈实现队列
两个堆栈。一个堆栈进行push，一个堆栈进行pop。当pop堆栈为空，把push的堆栈所有元素压入用于pop的堆栈。

2.使用队列实现堆栈

3.最小栈

进一步对存储空间进行优化

4.一个数组实现两个stack
stack1往前；stack2往后。

5.一个数组实现三个stack
一个数组分成三个空间使用。
空间上不连续 ，用链表优化

6.堆栈排序
额外使用一个stack，画一画就知道。