栈

简介

栈（stack），有些地方称为堆栈，是一种容器，一种线性表数据结构，它的特点在于只能允许在容器的一端（称为栈顶端指标，英语：top）进行插入数据（英语：push）和删除数据（英语：pop）的运算。

由于栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。

我们把栈中允许插入和删除的一段称为栈顶(top)；另一端则称为栈底(bottom)。当容器中没有任何数据元素时，称之为空栈。

栈有两种基本操作：【插入操作】和【删除操作】。

栈的插入操作又称为【入栈】或者【进栈】
栈的删除操作又称为【出栈】或者【退栈】

我们可以从两个方面来解释一下栈的定义：

第一个方面是「线性表」。

栈首先是一个线性表，栈中元素具有前驱后继的线性关系。栈中元素按照a1,a2,…,an的次序依次进栈。栈顶元素为an。

第二个方面是「后进先出原则」。

根据堆栈的定义，每次删除的总是堆栈中当前的栈顶元素，即最后进入堆栈的元素。而在进栈时，最先进入堆栈的元素一定在栈底，最后进入堆栈的元素一定在栈顶。也就是说，元素进入堆栈或者退出退栈是按照「后进先出（Last In First Out）」的原则进行的。

栈的基本操作

栈的基本操作如下：

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

栈的顺序存储和链式存储

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

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

在描述堆栈的顺序存储与链式存储具体实现之前，我们先来看看堆栈具有哪些基本操作。

栈的顺序存储

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

堆栈顺序存储基本描述

我们约定self.top指向栈顶元素所在位置。

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

栈的顺序存储实现代码

class Stack:
    # initial blank 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,val):
        if self.is_full():
            raise Exception("Stack is full")
        else:
            self.top += 1
            self.stack.append(val)
    
    # 出栈操作
    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]

栈的链式存储实现

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

栈的链式存储基本描述

我们约定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。

栈的链式存储实现代码

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

        
class Stack:
    # initial blank stack
    def __init__(self):
        self.top = None
        
    # 判断栈是否为空
    def is_empty(self):
        return self.top == None
    
    # 入栈
    def push(self, val):
        cur = Node(val)
        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