顺序栈：即堆栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时使用指针top指示栈顶元素在顺序栈中的位置。
链式栈：即堆栈的链式存储结构。利用单链表的方式来实现堆栈。栈中元素按照插入顺序依次插入到链表的第一个节点之前，并使用栈顶指针top指示栈顶元素，top永远指向链表的头节点位置。

1.1.1 堆栈的基本操作

栈作为一种线性表来说，理论上应该具备线性表所有的操作特性，但由于「后进先出」的特殊性，所以针对栈的操作进行了一些变化。尤其是插入操作和删除操作，改为了入栈（push）和出栈（pop）。

堆栈的基本操作如下：

初始化空栈：创建一个空栈，定义栈的大小 size，以及栈顶元素指针 top。
判断栈是否为空：当堆栈为空时，返回 True。当堆栈不为空时，返回 False。一般只用于栈中删除操作和获取当前栈顶元素操作中。
判断栈是否已满：当堆栈已满时，返回 True，当堆栈未满时，返回 False。一般只用于顺序栈中插入元素和获取当前栈顶元素操作中。
插入元素(进栈、入栈)：相当于在线性表最后元素后面插入一个新的数据元素。并改变栈顶指针 top 的指向位置。
删除元素(出栈、退栈)：相当于在线性表最后元素后面删除最后一个数据元素。并改变栈顶指针 top 的指向位置。
获取栈顶元素：相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是，该操作并不改变栈顶指针 top 的指向位置。

1.2 堆栈的顺序存储实现

堆栈最简单的实现方式就是借助于一个数组来描述堆栈的顺序存储结构。在 Python 中我们可以借助列表 list 来实现。这种采用顺序存储结构的堆栈也被称为 「顺序栈」。

1.2.1 堆栈的顺序存储基本描述

这里self.top指向栈顶元素所在位置。

初始化空栈：使用列表创建一个空栈，定义栈的大小 self.size，并令栈顶元素指针 self.top 指向 -1，即 self.top = -1。
判断栈是否为空：当 self.top == -1 时，说明堆栈为空，返回 True，否则返回 False。
判断栈是否已满：当 self.top == self.size - 1，说明堆栈已满，返回 True，否则返回返回 False。
获取栈顶元素：先判断队列是否为空，为空直接抛出异常。不为空则返回 self.top 指向的栈顶元素，即 self.stack[self.top]。
插入元素(进栈、入栈) ：先判断队列是否已满，已满直接抛出异常。如果队列未满，则在 self.stack 末尾插入新的数据元素，并令 self.top 向右移动 1 位。
删除元素(出栈、退栈)：先判断队列是否为空，为空直接抛出异常。如果队列不为空，则令 self.top 向左移动 1 位，并返回 self.stack[self.top]。

python代码实现：

class Stack:
    # 初始化空栈
    def __init__(self, size=100):
        self.stack = []
        self.size = size
        self.top = -1    
        
    # 判断栈是否为空
    def is_empty(self):
        return self.top == -1
    
    # 判断栈是否已满
    def is_full(self):
        return self.top + 1 == self.size
    
    # 入栈操作
    def push(self, value):
        if self.is_full():
            raise Exception('Stack is full')
        else:
            self.stack.append(value)
            self.top += 1
    
    # 出栈操作
    def pop(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            self.top -= 1
            self.stack.pop()
    
    # 获取栈顶元素
    def peek(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            return self.stack[self.top]

1.3 堆栈的链式存储实现

堆栈的顺序存储结构保留着顺序存储分配空间的固有缺陷，即在栈满或者其他需要重新调整存储空间时需要移动大量元素。为此，堆栈可以采用链式存储方式来实现。在 Python 中我们通过构造链表节点 Node 的方式来实现。这种采用链式存储结构的堆栈也被称为 「链式栈」。

1.3.1 堆栈的链式存储基本描述

这里self.top指向栈顶元素所在位置。

初始化空栈：使用列表创建一个空栈，并令栈顶元素指针 self.top 指向 None，即 self.top = None。
判断栈是否为空：当 self.top == None 时，说明堆栈为空，返回 True，否则返回 False。
获取栈顶元素：先判断队列是否为空，为空直接抛出异常。不为空则返回 self.top 指向的栈顶节点，即 self.top.value。
插入元素(进栈、入栈)：创建值为 value 的链表节点，插入到链表头节点之前，并令栈顶指针 self.top 指向新的头节点。
删除元素(出栈、退栈)：先判断队列是否为空，为空直接抛出异常。如果队列不为空，则令 self.top 链表移动 1 位，并返回 self.top.value。

python代码实现：

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        
class Stack:
    # 初始化空栈
    def __init__(self):
        self.top = None
    
    # 判断栈是否为空
    def is_empty(self):
        return self.top == None
    
    # 入栈操作
    def push(self, value):
        cur = Node(value)
        cur.next = self.top
        self.top = cur
    
    # 出栈操作
    def pop(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            cur = self.top
            self.top = self.top.next
            del cur
    
    # 获取栈顶元素
    def peek(self):
        if self.is_empty():
            raise Exception('Stack is empty')
        else:
            return self.top.value

二、堆栈的应用

堆栈是算法和程序中最常用的辅助结构，其的应用十分广泛。堆栈基本应用于两个方面：

使用堆栈可以很方便的保存和取用信息，因此常被用作算法和程序中的辅助存储结构，临时保存信息，供后面操作中使用。例如：操作系统中调用栈，浏览器中函数调用栈，浏览器中的前进、后退功能。
堆栈的后进先出规则，可以保证特定的存取顺序。例如：翻转一组元素的顺序、铁路列车车辆调度。

总结

栈的顺序存储结构中，存在着共享栈，共享栈是让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶共享空间的中间延伸，共享栈更好利用了存储空间，两个栈空间相互调节；
栈的链式存储结构是采用单链表实现，并规定所有操作都是在单链表的表头进行，优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。

码农公寓

前言

一、堆栈简介

1.1 堆栈的顺序存储与链式存储