初步认识栈和队列

Hello，everyone，今天小编讲解栈和队列的知识！！！

1.栈

1.1栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈， 入数据在栈顶。

出栈：栈的删除操作叫做出栈。 出数据也在栈顶。

1.2栈的实现

栈的实现一般可以使用 数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

1.2.1 头文件的建立

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef  int  datatype;
//这里选用动态数组实现栈，单链表也可以
typedef struct stack {datatype* a;int top;//栈顶int capacity;
}ST;
//栈的初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);
//入栈和出栈
void STPush(ST* pst,datatype x);
void STPop(ST* pst);
//获取栈顶数据
datatype STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//栈的数据个数
int STSize(ST* pst);

1.2.2 函数的实现

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
//栈的初始化和销毁
void STInit(ST* pst){assert(pst);pst->a = NULL;//top指向栈顶数据的下一个位置,可以理解为下标pst->top = 0;//top指向指向栈顶数据，可以理解成栈的数据个数//pst->top=-1;pst->capacity = 0;
}
void STDestory(ST* pst) {assert(pst);free(pst);pst->a = NULL;pst->top = pst->capacity = 0;
}
//容量检查
void Checkcapacity(ST* pst) {assert(pst);if (pst->top == pst->capacity) {int newcapacity = pst->capacity==0?4:pst->capacity * 2;datatype* temp = (datatype*)realloc(pst->a, newcapacity * sizeof(datatype));if (temp == NULL) {perror("relloc fail");return;}pst->a = temp;pst->capacity = newcapacity;}
}
//入栈和出栈
void STPush(ST* pst, datatype x) {assert(pst);Checkcapacity(pst);pst->a[pst->top] = x;pst->top++;
}
void STPop(ST* pst) {assert(pst);assert(pst->top>0);pst->top--;
}
//获取栈顶数据
datatype STTop(ST* pst) {assert(pst);assert(pst->top > 0);return pst->a[pst->top-1];
}
//判空
bool STEmpty(ST* pst) {assert(pst);return pst->top == 0;//表达式判断
}
//栈的数据个数
int STSize(ST* pst) {assert(pst);return pst->top;
}

1.2.3 测试文件

#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
int main() {ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);STPush(&s, 5);printf("%d\n", STTop(&s));STPop(&s);//STPop(&s);printf("%d\n", STTop(&s));while (!STEmpty(&s)) {printf("%d ", STTop(&s));STPop(&s);}STDestory(&s);return 0;
}

2.队列

2.1队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out)

入队列：进行插入操作的一端称为 队尾

出队列：进行删除操作的一端称为 队头

2.2队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.2.1 头文件的建立

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int Qdatatype;
//链式结构表示队列
typedef struct QueueNode {struct QueueNode* next;Qdatatype x;
}Node;
//定义结构体表示队头队尾,后续传参改变队列也很方便，不用传二级指针。
typedef struct Queue {Node* head;Node* tail;int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);// 队尾入队列
void QueuePush(Queue* q, Qdatatype data);// 队头出队列
void QueuePop(Queue* q);// 获取队列头部元素
Qdatatype QueueFront(Queue* q);// 获取队列队尾元素
Qdatatype QueueBack(Queue* q);// 获取队列中有效元素个数
int QueueSize(Queue* q);// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);// 销毁队列
void QueueDestroy(Queue* q);

2.2.2  函数的实现

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
void QueueInit(Queue* q) {assert(q);q->head = NULL;q->tail = NULL;q->size = 0;
}
// 队尾入队列
void QueuePush(Queue* q, Qdatatype data) {assert(q);Node* newnode = (Node*)malloc(sizeof(Node));if (newnode == NULL) {perror("malloc fail");return;}newnode->next = NULL;newnode->x = data;if (q->tail ==NULL) {q->head = q->tail = newnode;}else {q->tail->next = newnode;q->tail = newnode;}q->size++;
}
// 队头出队列
void QueuePop(Queue* q) {assert(q);assert(q->size != 0);//一个节点if (q->head->next == NULL) {free(q->head);q->head = q->tail = NULL;}else {Node* next = q->head->next;free(q->head);q->head = next;}q->size--;
}
// 获取队列头部元素
Qdatatype QueueFront(Queue* q) {assert(q);assert(q->head);return q->head->x;
}
// 获取队列队尾元素
Qdatatype QueueBack(Queue* q) {assert(q);assert(q->tail);return q->tail->x;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q) {assert(q);return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q) {assert(q);return q->size == 0;//为0，返回1，不为0，返回0；
}
// 销毁队列
void QueueDestroy(Queue* q) {assert(q);Node* qcur = q->head;while (qcur) {Node* next = qcur->next;free(qcur);qcur = next;}q->head = q->tail = NULL;q->size = 0;
}

2.2.3  测试文件

#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
int main() {Queue p;QueueInit(&p);QueuePush(&p,1);QueuePush(&p,2);printf("%d\n", QueueFront(&p));QueuePush(&p, 3);QueuePush(&p, 4);printf("%d\n",QueueBack(&p));QueuePop(&p);printf("%d\n", QueueFront(&p));while (!QueueEmpty(&p)){printf("%d ", QueueFront(&p));QueuePop(&p);}printf("\n");return 0;
}

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。

今天内容讲解结束，下次小编将讲解栈和队列的相关习题。

希望各位友友留下三连和评论！！！