欢迎来到博主的专栏——C语言数据结构
博主id：代码小豪
文章目录
- 栈
- 栈的顺序存储结构
- 栈的插入
- 空栈的初始化
- 栈的删除
- 判断空栈
- 读取栈顶元素数据
- 实现顺序栈的所有代码
- 栈的链式存储结构
- 链式栈的初始化
- 链式栈的入栈操作
- 链式栈的出栈操作
- 实现链式栈的所有代码
栈
栈是一个特殊线性表，其只能在表尾进行数据的插入与删除，进行数据的插入与删除的一端称为栈顶 （TOP）。
我们可以将栈想象成一个酸菜坛子，往坛子中开始放菜的时候，坛中的酸菜是从底部开始增加的。
当坛子放满酸菜后，我们开坛取出酸菜，酸菜会从顶部开始减少。
栈的顺序存储结构
前面提到了，栈是一个特殊的线性表，所以栈的储存形式也可以像线性表一样分为两种，一种为顺序存储结构的栈（顺序栈）。
既然顺序栈是用顺序结构实现的，那么就可以用数组来实现顺序栈。
顺序栈的结构声明如下：
typedef int SDataType;
typedef struct SeqStack
{
SDataType val[MAXSIZE];
int TOP;
}SeqStack;
栈的插入
从栈顶插入数据的操作被称为入栈（PUSH）
将数据插入栈顶的位置，然后栈顶的位置往上挪动一位，用于下一次入栈操作。
当栈为空时，栈顶的位置为0.
还有一种空栈的表示方法，由于数组中第一个元素的下标是0，但是空栈就代表着0下标处没有元素，所以空栈时，栈顶的位置为-1.
如果用这个方法表示的空栈，在插入数据时应该先让栈顶往上一步，再插入数据。
void StackPush(SeqStack* stack, SDataType e)
{
if (stack->TOP == MAXSIZE)
{
perror("stack overflow\n");
return;
}
stack->val[stack->TOP] = e;
stack->TOP++;
}
空栈的初始化
将一个新生成的栈传入函数进行初始化，初始化的方法根据入栈的形式而定（TOP为0或TOP为-1）
以前者为例，空栈的初始化的函数为
void StackInit(SeqStack* stack)
{
stack->TOP = 0;
}
栈的删除
从栈顶删除数据的操作称为出栈（POP）
出栈的方式很简单，我们不用将当前栈顶的数据进行处理，只需要将TOP的位置往下移动一格就行。
要注意当栈为空栈时的特殊情况，当栈为空栈时，出栈的操作会导致TOP位于非法的位置，当下次进行入栈操作时，就会发生数组越位的错误发生。
判断空栈
判断空栈的条件需要按照初始化时，栈顶的位置为准，以前者为例
bool StackEmpty(SeqStack* stack)
{
return stack->TOP == 0;
}
如果TOP为0，那么该函数返回值为true。反之为false。
出栈的函数需要调用判断空栈的函数，如下：
void StackPop(SeqStack* stack)
{
if (StackEmpty(stack))
{
perror("stack is empty\n");
return;
}
stack->top--;
}
读取栈顶元素数据
SDataType StackTop(SeqStack* stack)
{
return stack->val[stack->top - 1];
}
实现顺序栈的所有代码
typedef int SDataType;
typedef struct SeqStack
{
SDataType val[MAXSIZE];
int top;
}SeqStack;
void ListStackInit(ListStack* stack)
{
assert(stack);
stack->top = NULL;
stack->lenth = 0;
}
void ListStackPush(ListStack* stack, LDataType e)
{
StackNode* newnode = malloc(sizeof(StackNode));
assert(newnode);
newnode->val = e;
newnode->next = stack->top;
stack->top = newnode;
stack->lenth++;
}
bool ListStackEmpty(ListStack* stack)
{
return stack->top == NULL;
}
void ListStackPop(ListStack* stack)
{
if (!ListStackEmpty(stack))
{
perror("stack is empty\n");
return;
}
StackNode* del = stack->top;
stack->top = stack->top->next;
free(del);
}
LDataType ListStackTop(ListStack* stack)
{
assert(stack);
return stack->top->val;
}
栈的链式存储结构
栈既然是线性表，就可以用链表的形式来实现。
栈是从表尾进行插入和删除，链表可以用尾插\尾删的方法实现出栈和入栈（？）。
可以发现，使用尾删法是不能实现出栈操作的，因为单链表不能将TOP回到上一个数据的位置。
为了解决这个问题，我们将TOP的位置变为链表头，将入栈和出栈的操作用头插\头删法来实现。
链式栈的结构类型如下：
typedef int LDataType;
typedef struct StackNode
{
LDataType val;
struct StackNode* next;
}StackNode;
typedef struct ListStack
{
StackNode* top;
int lenth;
};
链式栈的初始化
链式栈的初始化如下
void ListStackInit(ListStack* stack)
{
assert(stack);
stack->top = NULL;
stack->lenth = 0;
}
链式栈的入栈操作
链式栈入栈使用头插法。代码如下：
void ListStackPush(ListStack* stack, LDataType e)
{
StackNode* newnode = malloc(sizeof(StackNode));
assert(newnode);
newnode->val = e;
newnode->next = stack->top;
stack->top = newnode;
stack->lenth++;
}
链式栈的出栈操作
考虑到链表空栈无法出栈，所以先定义一个判断空栈的函数
bool ListStackEmpty(ListStack* stack)
{
return stack->top == NULL;
}
链式栈出栈使用头删法。代码如下：
void ListStackPop(ListStack* stack)
{
if (ListStackEmpty(stack))
{
perror("stack is empty\n");
return;
}
StackNode* del = stack->top;
stack->top = stack->top->next;
free(del);
}
实现链式栈的所有代码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LDataType;
typedef struct StackNode
{
LDataType val;
struct StackNode* next;
}StackNode;
typedef struct ListStack
{
StackNode* top;
int lenth;
}ListStack;
void ListStackInit(ListStack* stack);
void ListStackPush(ListStack* stack,LDataType e);
void ListStackPop(ListStack* stack);
bool ListStackEmpty(ListStack* stack);
LDataType ListStackTop(ListStack* stack);
void ListStackInit(ListStack* stack)
{
assert(stack);
stack->top = NULL;
stack->lenth = 0;
}
void ListStackPush(ListStack* stack, LDataType e)
{
StackNode* newnode = malloc(sizeof(StackNode));
assert(newnode);
newnode->val = e;
newnode->next = stack->top;
stack->top = newnode;
stack->lenth++;
}
bool ListStackEmpty(ListStack* stack)
{
return stack->top == NULL;
}
void ListStackPop(ListStack* stack)
{
if (ListStackEmpty(stack))
{
perror("stack is empty\n");
return;
}
StackNode* del = stack->top;
stack->top = stack->top->next;
free(del);
}
LDataType ListStackTop(ListStack* stack)
{
assert(stack);
return stack->top->val;
}
