第3课数据结构基础（二）¶

栈¶

栈是一种特殊的线性表，但是他对于其中数据进行操作进行了一些限制。在一个栈中，所有的操作只能发生在栈顶，所以我们只能在栈顶中压入元素和弹出元素。请看下面的示意图：

stack

栈有三个最基本最核心的操作：入栈（Push）、出栈（Pop）和查看栈顶元素(Peek)。从上面的示意图中，可以看到栈有一个非常鲜明的特点：就是最后进入栈中的元素在出栈的过程中是最先被弹出的。所以栈也叫做先进后出(FILO, First In Last Out)表。

在生活中，我们也可以看到不少类似栈的例子。比如在打开一箱子书时，我们先取出的书一定是最后放入的书；比如手枪的弹夹中的子弹，最先发射出的子弹一定是最装入弹夹的子弹;比如在取盘子时，先取出的盘子是最后叠起来的盘子。

stack_example_gun

栈的实现¶

下面的python代码给出了一个栈class的基本框架。我们设定这个栈中储存的元素是整型的，并且它最多能容纳capacity个元素。

class Stack:
    def __init__(self, capacity: int):
    # 这是栈的构造方法，一般我们会给栈设置一个容量，表明他能容纳的元素个数。

    def push(self, val: int):
    # 将val压入栈中

    def pop(self) -> int:
    # 将栈顶元素弹出，并且返回

    def peek(self) -> int:
    # 查看栈项元素，并不弹出

    def empty(self) -> bool:
    # 栈是否为空

    def full(self) -> bool:
    # 栈是否已满

栈由于是一种特殊的线性表，所以在实现上，可以用数组或者链表来实现。下面我们使用数组来实现栈。

栈的构造方法¶

我们首先需要一个数组做为存储元素的空间，所以在构造方法中我们需要根据容量构造一个列表。同时我们需要一个变量保存目前栈顶的位置。请看代码：

def __init__(self, capacity: int):
    # 这将生成一个列表，并且其中有capacity个元素
    self.array = list(range(capacity))
    # 当前栈内没有元素，所以栈项的指针设为-1
    self.top = -1

栈是否为空和满¶

def empty(self) -> bool:
    # 当栈顶指针为-1时，栈为空
    return self.top == -1

def full(self) -> bool:
    # 当栈顶指针为列表最后一位时，栈已满
    return self.top ==  len(self.array) - 1

查看栈顶元素¶

def peek(self) -> int:
    # 返回当前栈顶元素。注意当栈是空的时候，我们返回一个None。
    if self.empty():
        return None
    else:
        return self.array[self.top]

压栈操作¶

在压栈操作时，要注意需要检查当前栈是否已满，如果已满则不能压栈。

def push(self, val: int):
    if self.full():
        # 这是一个新的语法，表示程序出错，我们抛出一个错误，这个错误的类型是字符串型。
        raise "The Stack is full."
    else:
        # 首先将栈顶指针往前移动一格，并且在此处赋值
        self.top += 1
        self.array[self.top] = val

出栈操作¶

同样的，在出栈操作时，我们需要注意需要检查当前栈是否已空

def pop(self) -> int:
    if self.empty():
        raise "The stack is empty"

    else:
        # 首先将栈底指针往后移动一格，并且将原栈顶元素返回
        # 注意保存栈顶元素和栈顶变化的顺序
        val = self.array[self.top]
        self.top -= 1
        return val

就这样我们就完成了一个数组版本的栈。下面请大家思考一下，如何用链表来实现一个版本的栈呢？

课堂任务一：¶

已知链表节点类ListNode，请使用链表的方法实现栈。注意，在使用链表实现栈时，可以不设置栈的容量。

class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

class Stack:
    def __init__(self):
        self.head = None

    def push(self, val):
    # 将val压入栈中

    def pop(self):
    # 将栈顶元素弹出，并且返回

    def peek(self):
    #查看栈项元素，并不弹出

    def empty(self):
    # 栈是否为空

    def full(self):
    # 栈是否已满

队列¶

关于队列，大家在生活中已经遇到很多了。比如不管去哪儿，只要人多了，一定会排队。并且排队最重要的特点就是先进先出，后进后出，非常公平。所以关于队列，我们把他叫做先进先出（FIFO, First In First Out)线性表。

同样的，队列也会有下面几个比较重要的核心操作：入队(push_back)，出队(pop_front)与查看队首或者队尾。

下面给出了一个队列的声明。在栈的实现中，我们使用列表来实现了一个栈，下面我们使用链表来实现一个队列。

class Queue:
    def __init__(self, capacity):

    def push_back(self, val):

    def pop_front(self):

    def front(self):

    def empty(self):

    def full(self):

队列的构造函数¶

在构造函数中，因为我们频繁的要使用入队和出队，所以我们保留两个节点，分别指向队列的队首和队尾，同时我们需要设置队列最大的容量。

def __init__(self, capacity):
    self.head = None
    self.tail = None
    self.capacity = capacity
    self.size = 0

初始化时，队列里还没有任何的元素，所以我们需要将当前的size置为0。

检查队列是否为空或者满¶

直接检测当前的队列的size是否为0或者是否为capacity。

def empty(self):
    return self.size == 0

def full(self):
    return self.size == self.capacity

入队¶

注意，入队时，我们要从队尾入队。其次要注意，当队列为空时，要将self.head指向刚增加的节点

def push_back(self, val):
    if self.full():
        raise "The queue is full."

    if self.empty():
        self.head = Node(val)
        self.tail = self.head
    else:
        self.tail.next = Node(val)
        self.tail = self.tail.next

    self.size += 1

出队¶

同样的，出队时我们从队首出。要特别注意，当最后一个元素被弹出时，队尾指针也需要置为None。

def pop_front(self):
    if self.empty():
        raise "The queue is empty."

    temp = self.head
    self.head = self.head.next
    if self.head is None:
        self.tail = None
    self.size -= 1
    return temp.val

查看队首元素和队尾元素¶

这两个就比较简单，直接看代码

def front(self):
    if self.empty():
        return None
    else:
        return self.head.val

def back(self):
    if self.empty():
        return None
    else:
        return self.tail.val

课堂任务二：¶

同样的，请你用链表来实现一个队列。

作业¶

请完成C004 - C005题目

第3课 数据结构基础（二）¶

栈¶