栈
栈是一种运算受限的线性表，是一种先进后出的数据结构，限定只能在一端进行插入和删除操作，允许操作的一端称为栈顶，不允许操作的称为栈底
顺序栈（顺序结构）
顺序栈：用一段连续的存储空间来存储栈中的数据元素，比较常见的是用数组来实现顺序栈
顺序存储结构：1.元素所占的存储空间必须连续（这里的连续是指的逻辑连续，而不是物理连续）
2.元素在存储空间的位置是按逻辑顺序存放的
（图片来源：https://www.cnblogs.com/misterge/p/3427587.html）
顺序栈的实现一般包括如下部分
代码声明部分
#include <stdio.h>
#include <stdlib.h> #define MAX_SIZE 5 /* 栈最大容量 */
#define Empty 0 /* 空 */
#define Full 1 /* 满 */
#define Avail -1 /* 可用 */ typedef struct sta
{
int *top; /* 栈顶指针 */
int *bottom; /* 栈底指针 */
int stack_size; /* 栈的最大容量 */
}stack;
stack Push (stack p); /* 入栈 */
void DisplyStack (stack p); /* 遍历栈中元素 */
stack Pop (stack p); /* 出栈 */
stack InitStack (stack p); /* 初始化栈 */
int StackEmpty (stack p); /* 判断栈是否为空 */
int StackFull (stack p); /* 判断栈是否为满 */
一、栈的声明
第一种：
typedef struct sta
{
int stack[SIZE]; /* 存放栈中元素的一维数组 */
int top; /* 存放栈顶元素的下标 */
}stack;
（这里只用了一个top来指向栈顶的位置，也可以用两个变量base、top来分别指向栈空间栈底位置和栈顶位置）
第二种：（本篇随笔是使用的第二种声明方式）
typedef struct sta
{
int *top; /* 栈顶指针 */
int *bottom; /* 栈底指针 */
int stack_size; /* 栈的最大容量 */
}stack;
二、栈的初始化
/* Function：栈的初始化 */
stack InitStack (stack p)
{
p.bottom = (int *)malloc(p.stack_size * sizeof(int));
if (p.bottom == NULL)
{
printf("初始化栈失败\n");
exit();
}
p.top = p.bottom;
p.stack_size = MAX_SIZE; return p;
}
三、入栈（压栈）
/* Function：入栈 */
stack Push (stack p)
{
int data;
if (StackFull(p) == Full)
{
printf("栈空间已满，无法入栈");
return p;
}
printf("Please input data");
scanf("%d", &data);
*p.top = data;
p.top++; return p;
}
四、出栈
/* Function：出栈 */
stack Pop (stack p)
{
if (StackEmpty(p) == Empty)
{
printf("栈为空栈，无法出栈 ");
return p;
}
p.top--;
printf("出栈元素为：%d\n", *p.top); return p;
}
（栈顶指针指向的位置是栈顶指针的后一个元素，所以在出栈时需要p.top--，才能指向出栈的元素）
五、判断栈是否为空
/* Function：判断栈是否为空 */
int StackEmpty (stack p)
{
if (p.top == p.bottom)
{
return Empty;
}
else
{
return Avail;
}
}
六、判断栈是否为满
/* Function：判断栈是否为满 */
int StackFull (stack p)
{
if (p.top - p.bottom == p.stack_size)
{
return Full;
}
else
{
return Avail;
}
}
七、遍历栈中的元素
/* Function：遍历栈中元素，从栈顶到栈底*/
void DisplyStack (stack p)
{
if (StackEmpty(p) == Empty)
{
printf("栈为空栈，无法遍历\n");
return;
}
printf("栈中元素为：");
printf("顶端[");
while (p.top != p.bottom)
{
p.top--;
printf("%d-", *p.top);
}
printf("]底端\n");
}
顺序栈实现--完整代码
#include <stdio.h>
#include <stdlib.h> #define MAX_SIZE 5 /* 栈最大容量 */
#define Empty 0 /* 空 */
#define Full 1 /* 满 */
#define Avail -1 /* 可用 */ typedef struct sta
{
int *top; /* 栈顶指针 */
int *bottom; /* 栈底指针 */
int stack_size; /* 栈的最大容量 */
}stack;
stack Push (stack p); /* 入栈 */
void DisplyStack (stack p); /* 遍历栈中元素 */
stack Pop (stack p); /* 出栈 */
stack InitStack (stack p); /* 初始化栈 */
int StackEmpty (stack p); /* 判断栈是否为空 */
int StackFull (stack p); /* 判断栈是否为满 */ int main()
{
stack p;
char ch; p.stack_size = MAX_SIZE;
p = InitStack (p); /* 初始化栈 */
printf("Do you want to push to stack?(Y/N)");
scanf(" %c", &ch);
while (ch == 'Y' || ch == 'y')
{
p = Push (p); /* 入栈 */
DisplyStack (p);/* 打印栈中元素 */
printf("Do you want to push to stack?(Y/N)");
scanf(" %c", &ch);
}
printf("Do you want to pop (Y/N)");
scanf(" %c", &ch);
while (ch == 'Y' || ch == 'y')
{
p = Pop (p);
DisplyStack (p);
printf("Do you want to pop (Y/N)");
scanf(" %c", &ch);
} return ;
}
/* Function：判断栈是否为空 */
int StackEmpty (stack p)
{
if (p.top == p.bottom)
{
return Empty;
}
else
{
return Avail;
}
}
/* Function：判断栈是否为满 */
int StackFull (stack p)
{
if (p.top - p.bottom == p.stack_size)
{
return Full;
}
else
{
return Avail;
}
}
/* Function：入栈 */
stack Push (stack p)
{
int data;
if (StackFull(p) == Full)
{
printf("栈空间已满，无法入栈");
return p;
}
printf("Please input data");
scanf("%d", &data);
*p.top = data;
p.top++; return p;
}
/* Function：出栈 */
stack Pop (stack p)
{
if (StackEmpty(p) == Empty)
{
printf("栈为空栈，无法出栈 ");
return p;
}
p.top--;
printf("出栈元素为：%d\n", *p.top); return p;
}
/* Function：栈的初始化 */
stack InitStack (stack p)
{
p.bottom = (int *)malloc(p.stack_size * sizeof(int));
if (p.bottom == NULL)
{
printf("初始化栈失败\n");
exit();
}
p.top = p.bottom;
p.stack_size = MAX_SIZE; return p;
}
/* Function：遍历栈中元素，从栈顶到栈底*/
void DisplyStack (stack p)
{
if (StackEmpty(p) == Empty)
{
printf("栈为空栈，无法遍历\n");
return;
}
printf("栈中元素为：");
printf("顶端[");
while (p.top != p.bottom)
{
p.top--;
printf("%d-", *p.top);
}
printf("]底端\n");
}
栈顶指针的指向有两种方式，一种是指向栈顶元素的后一元素（本文使用的就是这种），另一种是指向栈顶元素，两者在判断栈为空和满的条件、入栈、出栈时栈顶指针的移动有一些差异