4. 栈(Stack)
二十二画程序员 229 4

完整示例代码请移步至GitHub | Gitee

如有错误,还请指正

微信扫描下方二维码,一起学习更多计算机基础知识。

4. 栈(Stack)


前面已经介绍过了两种线性表——顺序存储结构的顺序表和链式存储结构的链表,也介绍了如何对其进行基本增删改查操作。这两种线性表的增加和删除可以在表的任意位置进行操作,比如链表的头插法和尾插法。

下面介绍一种特殊的线性表——栈。

4.0. 什么是栈?

栈,我们在日常生活中经常会听到一个与之相关的词语——栈道。什么是栈道?指沿悬崖峭壁修建的一种道路。李白诗《蜀道难》中的“天梯石栈相勾连”就是指这种栈:

4. 栈(Stack)

这种栈道的特点是很窄、很险,上图的栈仅能容纳一人,只能通过一侧进来和出去。在上图中,如果最左边的人想要出去,就得等右边的人全走了,他才能走。也即,最先进来的最后出去,最后进来的最先出去。

栈的英文是 Stack,本义是“一堆成叠的”。比如一堆成叠的书:

4. 栈(Stack)

在这叠书中,放书和拿书都从上面,要想拿到底下那个最大的,就得先把上面的几个小的先拿掉。也即,先放的书最后才能拿,最后放的书可以最先拿。

有了这两个实际的例子,我们心中对“栈”这个数据结构就有了一个“形状”了。

首先,栈是一个线性表,所以它得具有以下特点:

  • 线性表由若干元素组成,用来存储信息。
  • 元素之间有顺序。
  • 除了首元素(只有一个直接后继元素)和尾元素(只有一个直接前驱元素)外,其它元素都有且仅有一个直接前驱元素和一个直接后继元素。

其次,栈是一个受限的线性表,受限之处为:

  • 只能在一端进行操作(增删改查等)

根据以上总结的特点,我们可以画出栈的示意图,由于只能在一端进行操作,所以我们可以将其画为只有一个开口的“容器”:

4. 栈(Stack)

进行插入和删除操作的那一端称为栈顶(表尾),另一端称为栈底(表头)。

栈有两种重要的操作——入栈(压栈)和出栈(弹栈)。

所谓入栈(压栈),即栈的插入操作,由于栈的只能从栈顶插入元素的特性,所以插入元素看起来是将元素给“压入”栈。

4. 栈(Stack)

所谓出栈(弹栈),即栈的删除操作,由于栈的只能从栈顶删除元素的特性,所以删除元素看起来是将元素给“弹出”栈,弹出的元素必定是栈顶元素。

4. 栈(Stack)

栈的只能在一端操作的特性,导致栈具有一个非常特殊的特点,下图中的栈,元素入栈的顺序为:1、2、3、4,但是元素出栈的顺序则为:4、3、2、1。

4. 栈(Stack)

也即,先入栈的后出栈(First In Last Out, FILO),后入栈的先出栈(Last In First Out, LIFO),这是栈作为一种受限的线性表的非常重要的特性。

总结一下:栈是一种只能在表尾操作的后入先出的受限的线性表。

4.1. 栈的实现思路

栈虽然是一种受限的线性表,但线性表有的一些基本特性,栈也具备。在前面已经介绍过了线性表的顺序存储结构(数组实现)和线性表的链式存储结构(链表实现),栈也可以使用这两种方式来实现得到顺序栈链栈

4.1.0. 数组实现——顺序栈

分析一下栈的结构就可以知道栈有三个必要结构:

  • 用来存储数据的数组—— data[]
  • 用来表示线性表的最大存储容量的值——MAXSIZE
  • 用来标识栈顶元素的栈顶下标—— top

有的书上规定栈顶下标 top 是栈顶元素的下一个元素的下标,我们这里规定:栈顶下标是栈顶元素的下标。两种均可,无伤大雅。

栈顶下标还可以表示栈的当前长度。

4. 栈(Stack)

使用 C 语言的结构体实现如下:

为了方便起见,这里的栈只存储整数

#define MAXSIZE 5 //栈的最大存储容量

/*顺序栈的结构体*/
typedef struct {
    int data[MAXSIZE]; //存储数据的数组
    int top; //栈顶下标
}

4.1.1. 链表实现——链栈

首先我们得先了解单链表的具体原理及实现,详细介绍见【2. 链式存储结构的线性表】

链栈的结构和顺序栈的结构有所不同,其必要结构如下:

  • 链表的基本单元结点 —— StackNode
    • 结点的数据域—— data
    • 结点的指针域—— next
  • 指向链表头的头指针 —— head
  • 指向栈顶元素的栈顶指针 —— top

为了方便起见,我们可以再添加一个栈的长度—— length

前面说了,栈是一种只能在表尾操作的后入先出的受限的线性表。放在链表中,就是只在链表尾或链表头操作。那么是选择链表尾还是链表头呢?

上面已经列出了链栈的必要结构,其中包括了两个指针:头指针和栈顶指针。我们可以把这两个指针合二为一,即使用链表的头指针作为栈的栈顶指针,如此一来,链栈的操作就需要放在链表头进行,即借用链表头插法和头删法完成栈的 pushpop

4. 栈(Stack)

顺序栈的容量是固定的,而链栈的容量则不是固定的。在这里,我们使用不带头结点的链表来实现栈。

代码实现如下:

/*链栈结点的结构体*/
typedef struct StackNode {
    int data; //数据域
    StackNode *next; //指针域
} StackNode;
/*栈的结构体*/
typedef struct {
    StackNode *top; //栈顶指针
    int length; //栈的长度
} StackLink;

4.2. 栈的状态

4.2.0. 顺序栈的状态

顺序栈有三种状态:空栈、满栈、非空非满栈。通过栈顶下标栈的最大容量之间的关系,可以很容易判断出这三种状态。

【空栈】:栈中没有元素。

因为数组下标是从 0 开始的,所以此时栈顶下标 top 的值通常置为 -1,以此表示栈中无元素。

4. 栈(Stack)

【满栈】:栈中元素已满,没有多余容量。

4. 栈(Stack)

从图中可以看出,栈满时满足条件 top = MAXSIZE - 1

【非空非满栈】: 栈不是空栈且容量仍有剩余。

4. 栈(Stack)

此时的栈满足条件 -1 < top < MAXSIZE - 1

4.2.1. 链栈的状态

顺序栈之所以有三种状态,是因为有最大容量这个限制,而链栈的元素不收约束,所以链栈只有空栈和非空栈两种状态。

当为空栈时,栈顶指针和头指针都指向 NULL:

4. 栈(Stack)

4.3. 初始化

所谓初始化,即把栈初始化为空栈的状态。

4.3.0. 顺序栈的初始化

将顺序栈的栈顶下标置为 -1 即可。

/**
 * 顺序栈的初始化:将栈的栈顶下标置为 -1
 * stack: 指向要操作的栈的指针
 */
void init(StackArray *stack)
{
    stack->top = -1;
}

4.3.1. 链栈的初始化

需要将栈顶指针 top (即链表头指针 head)置为 NULL,将栈的长度 length 置为 0

/**
 * 初始化:将栈顶指针置为 NULL,长度置为 0
 * stack: 指向要操作的栈的指针
 */
void init(StackLink *stack)
{
    stack->top = NULL;
    stack->length = 0;
}

4.4. 入栈操作

4.4.0. 顺序栈

入栈前我们要搞清楚一个问题:

由于栈顶下标是栈顶元素的下标,所以在入栈前我们需要先将栈顶下标“上移”,给新入栈的元素腾出位置。然后才能将新元素入栈。

4. 栈(Stack)

在入栈前先检查一下栈是否已满,具体代码实现如下:

/**
 * 入栈操作
 * stack: 指向要操作的栈的指针
 * elem: 要入栈的数据
 * return: 0失败,1成功
 */
int push(StackArray *stack, int elem)
{
    if (stack->top == MAXSIZE - 1) {
        printf("栈已满,无法继续入栈。\n");
        return 0;
    }
    stack->top++;
    stack->data[stack->top] = elem;
    return 1;
}

4.4.1. 链栈

链栈的入栈操作实质为头插法,过程如下:

4. 栈(Stack)

具体代码实现如下:

StackNode *create_node(int elem)
{
    StackNode *new = (StackNode *) malloc(sizeof(StackNode));
    new->data = elem;
    new->next = NULL;
    return new;
}

/**
 * 入栈操作: 本质是单链表的头插法
 * head: 头指针
 * elem: 要入栈的结点的值
 */
void push(StackLink *stack, int elem)
{
    StackNode *new = create_node(elem);
    // 链表的头插法
    new->next = stack->top;
    stack->top = new;
    //栈长度加一
    stack->length++;
}

4.5. 出栈操作

4.5.0. 顺序栈

出栈操作和入栈操作刚好相反,即先将元素出栈,然后将栈顶下标“下移”。

4. 栈(Stack)

出栈前先检查栈是否为空栈,具体代码实现如下:

/**
 * 出栈操作
 * stack: 指向要操作的栈的指针
 * elem: 指向保存变量的指针
 * return: 0失败,1成功
 */
int pop(StackArray *stack, int *elem)
{
    if (stack->top == -1) {
        printf("栈空,无元素可出栈。\n");
        return 0;
    }
    *elem = stack->data[stack->top];
    stack->top--;
    return 1;
}

4.5.2. 链栈

链栈的出栈操作实质为头删法,即从链表头删除结点,过程如下:

4. 栈(Stack)

出栈前先检查栈是否为空栈,具体代码实现如下:

/**
 * 出栈操作: 本质是头删法
 * stack: 指向要操作的栈的指针
 * elem: 指向保存变量的指针
 * return: 0失败,1成功
 */
int pop(StackLink *stack, int *elem)
{
    if (stack->length == 0) {
        printf("栈空,无元素可出栈。\n");
        return 0;
    }
    // top_node 指向栈顶结点
    StackNode *top_node = stack->top;
    //保存栈顶结点的值
    *elem = top_node->data;
    //栈顶指针下移
    stack->top = top_node->next;
    //释放 top_node
    free(top_node);
    stack->length--;
    return 1;
}

4.6. 遍历栈

这里以打印栈为例来介绍如何遍历栈。

4.6.1. 顺序栈

顺序栈的遍历本质是在遍历数组,一个 for 循环即可搞定。

/**
 * 打印栈
 * stack: 要打印的栈
 */
void output(StackArray stack)
{
    if (stack.top == -1) {
        printf("空栈。\n");
        return;
    }
    for (int i = stack.top; i >= 0; i--) {
        printf("%d ", stack.data[i]);
    }
    printf("\n");
}

4.6.1. 链栈

链栈的遍历本质是在遍历链表,借助一个辅助指针从栈顶开始进行 whilefor 循环即可。

/**
 * 打印栈
 * stack: 要打印的栈
 */
void output(StackLink *stack)
{
    if (stack->length == 0) {
        printf("空栈。\n");
        return;
    }
    StackNode *p = stack->top;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
评论区

索引目录