详解顺序栈

站长

2024年04月12日 23:04 · 阅读数 9

顺序栈的定义及其特点；

详解顺序栈

定义

顺序栈是一种线性数据结构，具有特定的操作规则。它可以被看作是一种受限的线性表，只允许在表的一端进行插入和删除操作，这一端被称为栈顶，另一端被称为栈底。栈遵循先进后出（Last-In-First-Out，LIFO）的原则，即最后插入的元素最先被删除。

特点

先进后出（Last-In-First-Out，LIFO）：栈遵循先进后出的原则，即最后插入的元素最先被删除，而最先插入的元素最后被删除。
限制性：栈是一种受限的线性数据结构，只允许在栈顶进行插入和删除操作，而不能在栈的中间或底部进行操作。
栈顶和栈底：栈的一端被称为栈顶，另一端被称为栈底。栈顶是唯一可以进行插入和删除操作的位置，而栈底是不可移动的。
快速插入和删除：由于栈只允许在栈顶进行插入和删除操作，因此插入和删除操作的时间复杂度为O(1)，即常数时间。
有限容量：栈的容量是有限的，即栈的大小是固定的。当栈的容量达到上限时，继续进行入栈操作会导致栈溢出。
后进先出的应用场景：栈的先进后出特性使其在某些问题的解决中非常有用，例如表达式求值、函数调用的内存管理、逆波兰表达式、深度优先搜索（DFS）等。

栈的运算

结构体

typedef int DataType;


typedef struct
{
	DataType *data;         /* 堆空间 */
	int maxsize;
	int top;		/* 栈顶指针 */
}SeqStack;

初始化

申请空间对堆空间和最大数量、栈顶指针进行赋值

	S->data = (DataType*)malloc(sizeof(DataType)*MaxSize);

C语言数组指针（指向数组的指针）详解

获取最大个数申请内存空间，对栈顶指针和最大个数进行赋值

/* 1. 初始化 */
int init(SeqStack *S, int MaxSize)
{
	/*申请内存空间*/
	S->data = (DataType*)malloc(sizeof(DataType)*MaxSize);

	if(!S->data)
	{
		printf("内存申请错误，初始化失败！[10001]\n");
		return 10001;
	}
	S->maxsize = MaxSize;
	S->top = -1;
	return 0;
}

入栈

入栈（Push）是栈的基本运算之一，它用于将元素添加到栈的顶部，使其成为新的栈顶元素。

/* 2. 进（入）栈 */
int push(SeqStack *S, DataType x)
{
	/*是否满？*/
	if(full(S))
	{
		printf("栈已满！10002\n");
		return 10002;
	}

	S->top++;			/*移动指针*/
	S->data[S->top] = x;/*放入数据*/
	return 0; /*OK*/
}

出栈

检查栈是否为空、获取栈顶元素、更新栈顶指针或索引的步骤。

/* 3. 出栈 */
int pop(SeqStack *S, DataType *x)
{
	/*是否空？*/
	if(empty(S))
	{
		printf("栈为空！10003\n");
		return 10003;
	}

	*x = S->data[S->top];	/*栈顶元素赋值给x*/
	S->top--;				/*移动栈顶指针*/	

	return 0;
}

取栈顶元素

获取栈顶元素的值，但不删除。这个操作可以用于查看栈顶的元素，但不会对栈的结构进行修改。

/* 4. 取栈顶元素 */
int get_top(SeqStack *S, DataType *x)
{
	/*是否空？*/
	if(empty(S))
	{
		printf("栈为空！10003\n");
		return 10003;
	}

	*x = S->data[S->top];	/*栈顶元素赋值给x*/

	return 0;
}

栈为空？

检查栈是否为空，即栈中是否没有任何元素。这个操作可以用于判断栈是否为空，根据返回结果来决定后续的操作。

/* 5. 栈为空？*/
int empty(SeqStack *S)
{
	return (S->top == -1)?1:0;
}

栈满?

判断栈是否满可以通过比较栈的当前大小和最大容量

/* 6. 栈满？*/
int full(SeqStack *S)
{
	return (S->top == S->maxsize - 1)?1:0;
}

销毁

销毁栈是指将栈的内存空间释放，并将栈恢复到初始状态。

为了防止在释放内存空间后，紧接着访问内存空间带来的错误，需要在free后，将指针指向NULL

c语言的free函数与内存空间释放

/* 7. 销毁*/
int destroy(SeqStack *S)
{
	free(S->data);
	return 0;
}

栈的应用

十进制转换为二进制

首先，代码定义了一个名为d_to_b的函数，该函数接受一个整数参数d，表示要转换为二进制的十进制数。
在函数内部，声明了一个名为S的SeqStack类型的变量，用于存储二进制数的每一位。
接下来，使用init(&S, 32)函数初始化栈S，设置栈的最大容量为32，以便存储最多32位的二进制数。
然后，进入一个循环，条件是d不等于0。在循环中，执行以下操作：
- 将d除以2的余数（即d % 2）压入栈S中，用于存储二进制数的每一位。
- 将d除以2的商（即d / 2）赋值给d，用于下一次迭代。
- 重复上述步骤，直到d变为0，即已经将十进制数转换为二进制数并将其存储在栈S中。
接下来，使用另一个循环来依次弹出栈S中的元素，并将它们打印出来。这样做的目的是按正确的顺序将二进制数的每一位输出。
最后，使用destroy(&S)函数销毁栈S，释放内存。

/*十进制转换为二进制*/
int d_to_b(int d)
{
	SeqStack S;
	int b;

	/*初始化栈*/
	init(&S,32);

	/*d不为0，余数进栈*/
	while(d)
	{
		push(&S, d % 2);
		d /= 2;
	}
	
	/*依次出栈*/
	while(!empty(&S))
	{
		pop(&S,&b);
		printf("%d", b);
	}

	/*销毁栈*/
	destroy(&S);
}

后缀表达式计算

这段代码使用了一个顺序栈（SeqStack）来实现后缀表达式的计算。它首先初始化一个栈，然后读取用户输入的后缀表达式。接下来，它遍历表达式的每个字符，并根据操作符进行相应的计算。最后，从栈中取出计算结果并输出。

/*后缀表达式计算*/
int expression()
{
	SeqStack S;
	int i;
	int op1, op2;	
	int x;

	char exp[20]; /*后缀表达式*/

	init(&S, 10);

	printf("请输入一个后缀表达式(eg. 56+):");
	scanf("%s", exp);

	for(i=0;i<strlen(exp);i++)
	{
		switch(exp[i])
		{
		case '0':
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':
			/*入栈*/
			push(&S, exp[i]-48);
			break;
		case '+':
			/*出2个*/
			pop(&S, &op1);
			pop(&S, &op2);
			x = op1 + op2;
			push(&S, x);
			break;
		case '-':
			/*出2个*/
			pop(&S, &op1);
			pop(&S, &op2);
			x = op2 - op1;
			push(&S, x);
			break;
		case '*':
			pop(&S, &op1);
			pop(&S, &op2);
			x = op1 * op2;
			push(&S, x);
			break;
		case '/':
			pop(&S, &op1);
			pop(&S, &op2);
			x = op2 / op1;
			push(&S, x);
			break;
		}
	}
	pop(&S, &x);
	printf("计算结果为：%s = %d\n", exp, x);
	destroy(&S);
}

栈的实现

完整代码

项目结构

    main.c
    seqstack.c
    seqstack.h

项目文件

main.c

getchar() 跳过scanf问题

#include <stdio.h>
#include <string.h>

#include "seqstack.h"

/*十进制转换为二进制*/
int d_to_b(int d);

/*后缀表达式计算*/
int expression();

int main(int argc, char* argv[])
{
	SeqStack S;

	int cmd;
	int d;

	DataType x;
	int maxsize;
	char yn;

	
	do
	{
		printf("---------顺序栈演示程序-----------\n");
		printf(" 1. 初始化\n");
		printf(" 2. 入栈\n");
		printf(" 3. 出栈\n");
		printf(" 4. 取栈顶元素\n");
		printf(" 5. 栈是否空？\n");
		printf(" 6. 栈是否满？\n");
		printf(" 7. 销毁栈\n");
		printf(" 8. 栈的应用\n");
		printf(" 9.  帮助\n");
		printf("请选择（0~9,0退出)：");
		scanf("%d", &cmd);
		switch(cmd)
		{
		case 1:
			printf("请输入栈的最大存储空间(MaxSize)：");
			scanf("%d", &maxsize);
			if(!init(&S, maxsize))
			{
				printf("栈已初始化！\n");
			}
			break;
		case 2:
			printf("请输入入栈元素：x=");
			scanf("%d", &x);
			if(!push(&S, x))
			{
				printf("元素【%d】已入栈！\n", x);

			}
			break;
		case 3:
			printf("确定要出栈（出栈后数据不可恢复,y|n,n）？");
			getchar();
			scanf("%c", &yn);
			if(yn == 'y' || yn == 'Y')
			{
				if(!pop(&S, &x))
				{
					printf("栈顶元素【%d】已出栈！\n", x);
				}
			}

			break;
		case 4:
			if(!get_top(&S, &x)){
				printf("栈顶元素【%d】\n", x);
			}

			break; 
		case 5:
			if(!empty(&S)){
				printf("栈内有值的哦！\n");
			} else{
				printf("栈为空的哦！\n");
			}
			break;
		case 6:
			if(full(&S)){
				printf("栈满了哦！\n");
			} else{
				printf("栈没有满,还可以添加值哦！\n");
			} 
			break;	
		case 7:
			if(empty(&S)){
				printf("栈为空的哦！\n");
				break;
			} 
			printf("确定要出栈（出栈后数据不可恢复,y|n）？\n");
			empty(&S);
			getchar(); 
			scanf("%c", &yn);
			if(yn == 'y' || yn == 'Y')
			{
				if(!destroy(&S))
				{
					printf("栈已经全都销毁！\n");
				}
			}
			break;
		case 8:
			do
			{
				printf("----------8.栈的应用------------\n");
				printf(" 1. 十进制转换为二进制\n");
				printf(" 2. 后缀表达式计算\n");			
				printf(" 0. 返回\n");
				printf("请选择：");
				scanf("%d", &cmd);

				if(cmd == 1)
				{
					printf("请输入一个十进制数：");
					scanf("%d", &d);
					printf("二进制为：");
					d_to_b(d);
					printf("\n");
				}

				if(cmd == 2)
				{
					expression();
				}
			}while(cmd!=0);
			cmd = -1;
			break;
		case 9:
		    printf("本程序为顺序栈的演示程序，由曾苗强设计开发。\n对该文章有疑问欢迎交流！\n");
		}

	}while(cmd!=0);

	return 0;
}


/*十进制转换为二进制*/
int d_to_b(int d)
{
	SeqStack S;
	int b;

	/*初始化栈*/
	init(&S,32);

	/*d不为0，余数进栈*/
	while(d)
	{
		push(&S, d % 2);
		d /= 2;
	}
	
	/*依次出栈*/
	while(!empty(&S))
	{
		pop(&S,&b);
		printf("%d", b);
	}

	/*销毁栈*/
	destroy(&S);
}


/*后缀表达式计算*/
int expression()
{
	SeqStack S;
	int i;
	int op1, op2;	
	int x;

	char exp[20]; /*后缀表达式*/

	init(&S, 10);

	printf("请输入一个后缀表达式(eg. 56+):");
	scanf("%s", exp);

	for(i=0;i<strlen(exp);i++)
	{
		switch(exp[i])
		{
		case '0':
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9':
			/*入栈*/
			push(&S, exp[i]-48);
			break;
		case '+':
			/*出2个*/
			pop(&S, &op1);
			pop(&S, &op2);
			x = op1 + op2;
			push(&S, x);
			break;
		case '-':
			/*出2个*/
			pop(&S, &op1);
			pop(&S, &op2);
			x = op2 - op1;
			push(&S, x);
			break;
		case '*':
			pop(&S, &op1);
			pop(&S, &op2);
			x = op1 * op2;
			push(&S, x);
			break;
		case '/':
			pop(&S, &op1);
			pop(&S, &op2);
			x = op2 / op1;
			push(&S, x);
			break;
		}
	}
	pop(&S, &x);
	printf("计算结果为：%s = %d\n", exp, x);
	destroy(&S);
}

seqstack.h

/*
	seqstack.h
	顺序栈
*/

typedef int DataType;


typedef struct
{
	DataType *data; /* 堆空间 */
	int maxsize;
	int top;		/* 栈顶指针 */
}SeqStack;


/* 1. 初始化 */
int init(SeqStack *S, int MaxSize);

/* 2. 进（入）栈 */
int push(SeqStack *S, DataType x);

/* 3. 出栈 */
int pop(SeqStack *S, DataType *x);

/* 4. 取栈顶元素 */
int get_top(SeqStack *S, DataType *x);

/* 5. 栈为空？*/
int empty(SeqStack *S);

/* 6. 栈满？*/
int full(SeqStack *S);

/* 7. 销毁*/
int destroy(SeqStack *S);

seqstack.c

/*
	seqstack.c

*/
#include "seqstack.h"


/* 1. 初始化 */
int init(SeqStack *S, int MaxSize)
{
	/*申请内存空间*/
	S->data = (DataType*)malloc(sizeof(DataType)*MaxSize);

	if(!S->data)
	{
		printf("内存申请错误，初始化失败！[10001]\n");
		return 10001;
	}
	S->maxsize = MaxSize;
	S->top = -1;
	return 0;
}


/* 2. 进（入）栈 */
int push(SeqStack *S, DataType x)
{
	/*是否满？*/
	if(full(S))
	{
		printf("栈已满！10002\n");
		return 10002;
	}

	S->top++;			/*移动指针*/
	S->data[S->top] = x;/*放入数据*/
	return 0; /*OK*/
}

/* 3. 出栈 */
int pop(SeqStack *S, DataType *x)
{
	/*是否空？*/
	if(empty(S))
	{
		printf("栈为空！10003\n");
		return 10003;
	}

	*x = S->data[S->top];	/*栈顶元素赋值给x*/
	S->top--;				/*移动栈顶指针*/	

	return 0;
}

/* 4. 取栈顶元素 */
int get_top(SeqStack *S, DataType *x)
{
	/*是否空？*/
	if(empty(S))
	{
		printf("栈为空！10003\n");
		return 10003;
	}

	*x = S->data[S->top];	/*栈顶元素赋值给x*/

	return 0;
}

/* 5. 栈为空？*/
int empty(SeqStack *S)
{
	return (S->top == -1)?1:0;
}

/* 6. 栈满？*/
int full(SeqStack *S)
{
	return (S->top == S->maxsize - 1)?1:0;
}


/* 7. 销毁*/
int destroy(SeqStack *S)
{
	free(S->data);
	return 0;
}

运行结果

详解顺序栈

小结

顺序栈是一种常见的数据结构，它遵循"后进先出"（LIFO）的原则，即最后入栈的元素最先出栈。栈可以用来解决许多实际问题，并在计算机科学和编程中得到广泛应用

顺序栈的特点：栈是一种线性数据结构，可以通过数组或链表来实现。它具有以下特点：
- 后进先出（LIFO）：最后入栈的元素最先出栈。
- 只能在栈的一端进行插入和删除操作，称为栈顶。
- 栈顶是唯一可以访问和操作的元素。
顺序栈的应用：
- 函数调用：函数调用时使用栈来保存函数的上下文和局部变量。
- 表达式求值：使用栈来处理中缀表达式转换为后缀表达式，并计算后缀表达式的值。
- 浏览器的前进和后退功能：使用栈来保存浏览历史记录。
- 括号匹配：使用栈来检查括号是否匹配。

顺序栈是一种简单而强大的数据结构，它在解决许多问题时非常有用。了解顺序栈的特点、操作和应用场景，以及实现方式和复杂度，对于编程和算法的学习都非常重要。

参考文献

ora.ai

转载自:https://juejin.cn/post/7291186330911244346