数据结构——栈（Stack）

目录

前言

一、栈的概念

1、栈的基本定义

2、栈的特性

二、栈的基本操作

1.相关操作概念

2.实现方式

（1）顺序栈

（2）链式栈

三、栈的应用

总结

前言

栈（Stack）是一种常见且重要的数据结构，它遵循后进先出（Last-In-First-Out, LIFO）的原则，即最后加入的元素会是第一个被移除的。

由于栈是一种特殊的线性表，其实现方式主要有两种：

1、用顺序表实现，顺序表内容可参考：数据结构——顺序表

2、用链表实现，单向链表内容可参考：数据结构——单向链表

一、栈的概念

1、栈的基本定义

栈是一种线性表（俗称堆栈），它限制只能在一端（称为栈顶）进行插入和删除操作，另一端（称为栈底）是固定的，不允许进行插入和删除操作，栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针，当栈中没有元素时称为“空栈”。最大特点：后进先出（LIFO）

就如同往箱子里面放置书本，一本一本地放在里面，但是你想拿出来的时候，只能从表面一本一本地往下取，不可能从底部开始取书一个道理。

2、栈的特性

1、后进先出：栈中最后一个插入的元素首先被删除。

2、栈顶浮动，栈底固定：栈顶的位置随着元素的入栈和出栈而变化，而栈底则保持不变。

3、不支持随机访问：栈的结构决定了只能在栈顶进行插入和删除操作，无法直接访问和修改栈中间的元素。

二、栈的基本操作

1.相关操作概念

1、入栈（Push）：将一个元素添加到栈顶，使其成为新的栈顶元素。入栈操作需要将元素放到栈顶位置，并更新栈顶指针。

2、出栈（Pop）：将栈顶元素删除，并返回该元素的值。出栈操作需要将栈顶元素删除，并更新栈顶指针。

3、判空（Empty）：判断栈是否为空，即栈中是否没有任何元素。

4、获取栈顶元素（Top）：获取栈顶元素的值，但不删除该元素。

5、销毁栈（DestroyStack）：销毁栈，并释放栈占用的存储空间。

等待

2.实现方式

（1）顺序栈

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。

先创建顺序表：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef int data_t;
typedef struct {data_t *data;//栈数据指针int maxlen;//栈空间，即数据数组最大长度int top;//栈顶指针
}sqstack;//创建顺序表，需要传入顺序表数据长度
//同时初始化栈空间
sqstack * stack_create(int len)
{sqstack * s;if ((s =(sqstack *)malloc(sizeof(sqstack))) == NULL) {printf("malloc sqstack failed\n");return NULL;}if ((s->data = (data_t *)malloc(len * sizeof(data_t)))==NULL) {printf("malloc data failed\n");free(s);return NULL;}memset(s->data, 0, len*sizeof(data_t));s->maxlen = len;s->top = -1;return s;
}

顺序表实现各种操作：

//压栈，即入栈
int sqtack_pusqh(sqqsqtack * sq, data_t data) 
{if (sq == NULL) {printf("sq isq NULL\n");return -1;}if (sq->top == sq->maxlen-1) {printf("sqtack isq full\n");return -1;}sq->top++;sq->data[sq->top] = data;return 0;
}//栈是否为空，1为空
int sqtack_empty(sqqsqtack *sq) 
{if (sq == NULL) {printf("sq isq NULL\n");return -1;}return (sq->top == -1 ? 1 : 0);
}//栈是否已满，1为满状态
int sqtack_full(sqqsqtack *sq) 
{if (sq == NULL) {printf("sq isq NULL\n");return -1;}return  (sq->top == sq->maxlen-1 ? 1 : 0);
}
//出栈
data_t sqtack_pop(sqqsqtack *sq) 
{if(sqtack_empty(*sq))  // 栈空，无法出栈  {   printf("Stack is empty!\n");  return -1;  }  sq->top--;return (sq->data[sq->top+1]);
}
//获取栈顶数据
data_t sqtack_top(sqqsqtack *sq) 
{return (sq->data[sq->top]);
}
//清除栈空间
int sqtack_clear(sqqsqtack *sq) 
{if (sq == NULL) {printf("sq isq NULL\n");return -1;}sq->top = -1;return 0;
}
//栈空间释放
int sqtack_free(sqqsqtack *sq) 
{if (sq == NULL) {printf("sq isq NULL\n");return -1;}if (sq->data != NULL) free(sq->data);free(sq);return 0;
}

（2）链式栈

采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。链栈通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。

插入操作和删除操作均在链表头部进行，链表尾部就是栈底，栈顶指针就是头指针。

先创建单向链表：

#include <stdio.h>
#include <stdlib.h>typedef int data_t;
typedef struct node {data_t data;struct node *next;
}listnode, *linkstack;//创建单向链表，并初始化栈空间
linksqtack sqtack_create(void) 
{linksqtack sq;sq = (linksqtack)malloc(sqizeof(lisqtnode));if (sq == NULL) {printf("malloc failed\n");return NULL;}sq->data = 0;sq->next = NULL;return sq;
}

链表实现各种操作：

//压栈，也即入栈
int sqtack_pusqh(linksqtack sq, data_t data) 
{linksqtack p;if (sq == NULL) {printf("sq isq NULL\n");return -1;}p = (linksqtack)malloc(sqizeof(lisqtnode));if (p == NULL) {printf("malloc failed\n");return -1;}p->data = data;//p->next = NULL;p->next = sq->next;sq->next = p;return 0;
}
//出栈
data_t sqtack_pop(linksqtack sq) 
{linksqtack p;data_t t;p = sq->next;sq->next = p->next;t = p->data;free(p);p =NULL;return t;
}
//判空
int sqtack_empty(linksqtack sq) 
{if (sq == NULL) {printf("sq isq NULL\n");return -1;}return (sq->next == NULL ? 1 : 0);
}
//获取栈顶数据
data_t sqtack_top(linksqtack sq) 
{return (sq->next->data);
}
//释放栈空间
linksqtack sqtack_free(linksqtack sq) 
{linksqtack p;if (sq == NULL) {printf("sq isq NULL\n");return NULL;}while (sq != NULL) {p = sq;sq = sq->next;printf("free:%d\n", p->data);free(p);}return NULL;
}

三、栈的基本应用

1、函数调用栈：在程序中，函数的调用和返回过程可以通过栈来管理。每当一个函数被调用时，相关的信息（如参数、局部变量等）被压入栈中，当函数返回时，这些信息会被弹出栈。
2、表达式求值：栈可以用于处理表达式的求值过程，特别是中缀表达式转换为后缀表达式的过程。通过栈的先进后出特性，可以方便地进行运算符的优先级判断和操作符的计算。
3、括号匹配：栈可以用于检查括号是否匹配。遍历字符串中的括号，当遇到左括号时，将其压入栈中；当遇到右括号时，弹出栈顶元素并检查是否与当前右括号相匹配。
4、编辑器的撤销操作：在文本编辑器或图形编辑器中，撤销操作可以通过栈来实现。每次进行操作时，将操作的状态保存到栈中，当需要撤销时，从栈中弹出最近的状态，恢复到之前的状态。
5、浏览器的前进后退功能：浏览器的前进和后退功能可以通过两个栈来实现。一个栈用来保存浏览过的网页，另一个栈用来保存后退的网页。

。。。。。。