博客

堆栈（简称栈）是插入和删除操作都在表的同一端进行的线性表。运行插入和删除元素的一端称为栈顶（top），另一端称为栈底（bottom）。如果堆栈中没有元素，则为空栈。栈是一个后进后出的结构（Last In First Out），简称为LIFO结构。

有几点需要注意：

1.栈本质上还是线性表，只是这个线性表增加了新的限定规则，只能在一端进行插入和删除。

2.栈和线性表一样，也有顺序存储（顺序栈）和链式存储（链式栈）两种结构。

3.栈的插入叫进栈，栈的删除叫出栈

顺序栈

顺序栈是栈的顺序实现。顺序栈是指利用顺序存储结构实现的栈。采用地址连续的存储空间(数组)依次存储栈中数据元素。下面是顺序栈的示意图：

顺序栈有八个操作，分别是初始化，出栈，入栈，是否为空，是否为满，取栈顶元素，取有效元素个数，遍历。

先对堆栈结构体定义：

typedef struct//堆栈结构体定义
{
	int top;//栈顶指针
	int data[MaxSize];//静态数组存放栈中元素
}SqStack;

初始化

根据上面的示意图，初始化只需把栈顶指针指向-1就可以了。

void InitStack(SqStack &S)//初始化栈
{
	S.top = -1;//初始化栈顶指针
}

出栈

1.判断是否为空栈，空栈无法进行出栈操作。

2.先赋值给x再移动栈顶指针，并且是向下移动。

bool Printf(SqStack &S,int &x)//出栈(删除栈顶元素)
{
		if (S.top == -1)//判断是否为空栈
			return false;
		x = S.data[S.top];//让x等于此时栈顶指针所指的元素
		S.top = S.top - 1;//栈顶指针往下移动一位
	return true;
}

入栈

1.判断是否为栈满，栈满无法进行入栈操作。

2.栈顶指针先向上移动，再把输入的数据放进去。

bool Push(SqStack &S)//入栈（在栈顶位置插入元素）
{
	printf("请输入%d个数:", MaxSize);
	for (int i = 0; i < MaxSize; i++)
	{
		if (S.top == MaxSize - 1)//判断栈满了没有
			return false;
		S.top = S.top + 1;//栈顶指针往上移动一位
		scanf("%d", &S.data[S.top]);//把这次输入的元素放入此时栈顶指针指向的位置
	}
		return true;
}

判断栈空

只需要判断栈顶指针指向的是不是-1，因为一开始空栈的时候栈顶指针指向的是-1。

int testStack(SqStack &S)//判断栈空
{
	return (S.top == -1);//空栈返回1，反之返回0。
}

判断栈满

由于栈顶指针指向的是-1，所以一开始放入的位置是0，栈满的时候就会是MaxSize-1，只需判断栈顶指针指向的是不是MaxSize-1就好了。

int IsFull(SqStack &S)//判断栈满
{
	return (S.top == MaxSize-1);//满栈返回1，反之返回0。
}

取栈顶元素

取栈顶元素的操作和一次出栈类似，但是不需要进行栈顶指针的移动。

bool GetTop(SqStack &S)//读取栈顶元素，操作和出栈类似，top不需要减1。
{
	if (S.top == -1)//判断空栈
		return false;
	int x = S.data[S.top];
	printf("栈顶元素是：%d\n", x);
	return true;
}

取有效元素个数

由上面的效果图可知，栈顶指针+1就可以了。

int lenth(SqStack &S)//求有效元素的个数
{
	return S.top + 1;
}

遍历

遍历是进行多次的出栈操作，并把每次出栈的数据打印出来。给出栈操作加上循环和输出即可。

全部代码：

#define _CRT_SECURE_NO_WARNINGS 
#define MaxSize 5
#include<stdio.h>

typedef struct//堆栈结构体定义
{
	int top;//栈顶指针
	int data[MaxSize];//静态数组存放栈中元素
}SqStack;

void InitStack(SqStack &S)//初始化栈
{
	S.top = -1;//初始化栈顶指针
}

int testStack(SqStack &S)//判断栈空
{//只需要判断栈顶指针指向的是不是-1，因为一开始空栈的时候栈顶指针指向的是-1。
	return (S.top == -1);//空栈返回1，反之返回0。
}

int IsFull(SqStack &S)//判断栈满
{
	return (S.top == MaxSize-1);//满栈返回1，反之返回0。
}

bool Push(SqStack &S)//入栈（在栈顶位置插入元素）
{
	printf("请输入%d个数:", MaxSize);
	for (int i = 0; i < MaxSize; i++)
	{
		if (S.top == MaxSize - 1)//判断栈满了没有
			return false;
		S.top = S.top + 1;//栈顶指针往上一位
		scanf("%d", &S.data[S.top]);//把这次输入的元素放入此时栈顶指针指向的位置
	}
		return true;
}

bool GetTop(SqStack &S)//读取栈顶元素，操作和出栈类似，top不需要减1。
{
	if (S.top == -1)
		return false;
	int x = S.data[S.top];
	printf("栈顶元素是：%d\n", x);
	return true;
}

int lenth(SqStack &S)//求有效元素的个数
{
	return S.top + 1;
}

bool Printf(SqStack &S,int &x)//出栈(删除栈顶元素)
{
		if (S.top == -1)//判断是否为空栈
			return false;
		x = S.data[S.top];//让x等于此时栈顶指针所指的元素
		S.top = S.top - 1;//栈顶指针往下移动一位
	return true;
}

void DestroyStack(SqStack &S)//销毁栈
{
	char a;
	getchar();
	printf("是否销毁顺序栈(Y/N):");
	scanf("%c", &a);
	if (a == 'Y')
	{
		printf("销毁成功\n");
		S.top = -1;
	}
	else
		printf("未销毁\n");
}

int main()
{
	int x;
	SqStack S;//声明栈
	InitStack(S);//初始化栈
	Push(S);//入栈
	int a=testStack(S);//判断栈空
	a == 1 ? printf("栈空\n") : printf("栈不是空的\n");
	a = IsFull(S);
	a == 1 ? printf("栈满\n") : printf("栈不满\n");
	GetTop(S);//读取栈顶元素
	int len = lenth(S);
	printf("栈内元素个数：%d\n", len);
	Printf(S,x);//出栈
	DestroyStack(S);//销毁栈
	return 0;
}

输出结果：

如果有什么不懂的，文中有错误的可以私信联系我，非常感谢。

觉得这篇博客对你有帮助的话可以点个赞呀。