什么是栈、队列及如何用C语言实现顺序栈---嵌入式入门

经过前面表的讲解，我相信各位对数据结构已经有了一个初步的认识了，那么今天我们将继续数据结构内容的讲解，与表相对应的就是栈，这是在表的基础上实现的，只不过加了限制条件，那到底加了什么限制条件呢，那就跟随博主的脚步一起去探索一下吧。

1、栈和队列

1.1 基本概念

• 栈是一种先进后出，后进先出的数据结构

比如我们在编辑文档的时候，需要撤销到某一步去，是不是只能先撤销上一步执行的，才能去撤销上上步执行的，这就是先进后出，后进先出

• 队列是一种先进先出，后进后出的数据结构

这种就更常见了，就比如我们去餐厅吃饭，是不是需要排队，先排的人先点餐，也就是先进先出，后进后出了 。

1.2 栈、队列和表的区别

• 栈和队列是一种特殊的表状结构
• 栈和队列只能在指定的位置插入和删除
• 表状结构可以在任意位置插入和删除

2、栈

2.1 基本概念

栈顶：允许入栈和出栈的一端称为栈顶

栈底：不允许入栈和出栈的一端称为栈底

栈针（Stack Pointer）：指向栈顶位置的指针或下标

增栈：栈向高地址增长

减栈：栈向低地址增长

空栈：栈针指向入栈位置（一个可用的空闲位置），称为空栈

满栈：栈针指向栈顶位置（最后一个入栈的元素的位置），称为满栈

入栈（压栈/Push）：将数据插入栈顶元素的位置

出栈（弹栈/Pop）：将数据从栈顶元素位置取出

2.2 栈的分类

所以我们根据是否是空栈还是满栈，以及增长的方向可以分为以下常见的四种栈

• 空增栈
• 满增栈
• 空减栈
• 满减栈

2.3 顺序栈的实现

2.3.1四种栈类型的区别

在讲解顺序栈之前，我们先来讲解一下满栈和空栈的区别吧

然后具体到满增栈和空增栈的区别：

top：栈针的位置

maxSize：栈空间大小

满增栈和满减栈的区别：

空增栈和空减栈的区别：

好了，以上就是四种栈的一个主要区别，我们理解之后，就开始来实现顺序栈吧：

2.3.2 顺序栈结构体的创建

typedef int DataType;
typedef strcut SeqStack {
DataType *data;
int top;
int maxlen;
}SeqStack;

2.3.3 顺序栈的创建

我们在此就用满增栈来创建实现：

SeqStack *CreateSeqStack(int maxLen) {
SeqStack *tmpStack = NULL;
tmpStack = malloc(sizeof(SeqStack));
if(tmpStack == NULL) {
perror("malloc tmpStack failed");
return NULL;
}
tmpStack->data = malloc(maxLen * sizeof(DataType));
if(tmpStack->data == NULL) {
perror("malloc tmpStack->data failed");
free(tmpStack);
tmpStack = NULL;
return NULL;
}
tmpStack->top = -1;
tmpStack->maxlen = maxLen;

return tmpStack;
}

2.3.4 销毁顺序栈

int DestroySeqStack(SeqStack **Stack) {
free((*Stack)->data);
free(*Stack);
*Stack = NULL;
return 0;
}

2.3.5 判断栈空/栈满

栈空：

int IsEmptySeqStack(SeqStack *Stack) {
return Stack->top == -1 ? 1 : 0;
}

栈满：

int IsFullSeqStack(SeqStack *Stack) {
return Stack->top == Stack->maxlen – 1 ? 1 : 0;
}

2.3.6 入栈

int PushSeqStack(SeqStack *Stack, DataType tmpData) {
if(IsFullSeqStack(Stack)) {
printf("栈满，无法入栈\\n");
return -1;
}
Stack->data[++top->top] = tmpData;
return 0;
}

2.3.7 出栈

int PopSeqStack(SeqStack *Stack, DataType *outData) {
if(IsEmptySeqStack(Stack)) {
printf("栈空，无法出栈\\n");
return -1;
}

*outData = Stack->data[Stack->top–];

return 0;
}

以上就是对顺序栈实现的全过程的一个讲解了，都不是很难，我们只要清楚进出栈的逻辑关系，就很好创建一个顺序栈了，那么大家可以在思考思考，总结总结，下次我们将学习链栈的相关只是，可以想想链栈如何去实现，和我们之前学的链表的哪种形式是一样的呢？下次见！