1.栈简介

栈：也称为堆栈。一种线性表数据结构，是一种只允许在表的一端进行插入和删除操作的线

性表。

把栈中允许插入和删除的一端称为「栈顶（top）」；另一端则称为「栈底（bottom）」。当表

中没有任何数据元素时，称之为「空栈」。

堆栈有两种基本操作：「插入操作」和「删除操作」。

• 栈的插入操作又称为「入栈」或者「进栈」。

• 栈的删除操作又称为「出栈」或者「退栈」。

栈是一种「后进先出（Last In First Out）」的线性表，简称为 「LIFO 结构」。

根据堆栈的定义，每次删除的总是堆栈中当前的栈顶元素，即最后进入堆栈的元素。而在进栈时，最先

进入堆栈的元素一定在栈底，最后进入堆栈的元素一定在栈顶。

2.栈的基本操作

栈的基本操作如下：

• 初始化空栈：创建一个空栈，定义栈的大小 size，以及栈顶元素指针 top。

1. 判断栈是否为空：当堆栈为空时，返回 True。当堆栈不为空时，返回 False。一般只用于栈中删除

操作和获取当前栈顶元素操作中。

• 判断栈是否已满：当堆栈已满时，返回 True，当堆栈未满时，返回 False。一般只用于顺序栈中插

入元素和获取当前栈顶元素操作中。

• 插入元素（进栈、入栈）：相当于在线性表最后元素后面插入一个新的数据元素。并改变栈顶指针

top 的指向位置。

• 删除元素（出栈、退栈）：相当于在线性表最后元素后面删除最后一个数据元素。并改变栈顶指针

top 的指向位置。

• 获取栈顶元素：相当于获取线性表中最后一个数据元素。与插入元素、删除元素不同的是，该操作

并不改变栈顶指针 top 的指向位置。

3.栈的顺序存储与链式存储

和线性表类似，栈有两种存储表示方法：「顺序栈」和 「链式栈」。

• 「顺序栈」：即堆栈的顺序存储结构。利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，

同时使用指针 top 指示栈顶元素在顺序栈中的位置。

• 「链式栈」：即堆栈的链式存储结构。利用单链表的方式来实现堆栈。栈中元素按照插入顺序依次

插入到链表的第一个节点之前，并使用栈顶指针 top 指示栈顶元素，top 永远指向链表的头节点位

置。

3.1栈的顺序存储

栈最简单的实现方式就是借助于一个数组来描述堆栈的顺序存储结构。在 Python 中我们可以借助列

表 list 来实现。这种采用顺序存储结构的堆栈也被称为「顺序栈」。

3.1.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]。

1. 插入元素（进栈、入栈）：先判断堆栈是否已满，已满直接抛出异常。如果堆栈未满，则在

self.stack 末尾插入新的数据元素，并令 self.top 向右移动 1 位。

• 删除元素（出栈、退栈）：先判断堆栈是否为空，为空直接抛出异常。如果堆栈不为空，则先让

self.top 向左移动 1 位，然后再删除当前堆栈元素。

3.1.2栈的顺序存储实现代码

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 ]

3.2栈的链式存储

堆栈的顺序存储结构保留着顺序存储分配空间的固有缺陷，即在栈满或者其他需要重新调整存储空间时

需要移动大量元素。为此，堆栈可以采用链式存储方式来实现。在 Python 中我们通过构造链表节点

Node 的方式来实现。这种采用链式存储结构的堆栈也被称为「链式栈」。

3.2.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。

3.2.2栈的链式存储实现代码

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

4.栈的应用

栈基本应用于两个方面：

（1）使用栈可以很方便的保存和取用信息，因此常被用作算法和程序中的辅助存储结构，临时保存信息，供后面操作中使用。

例如：操作系统中的函数调用栈，浏览器中的前进、后退功能。

（2）堆栈的后进先出规则，可以保证特定的存取顺序。

例如：翻转一组元素的顺序、铁路列车车辆调度。