C语言数据结构——栈和队列_c语言栈和队列
赞
踩
目录
前言
本篇文章主要带领大家深入了解栈和队列以及相关实现。
一、栈
1.1 栈的概念和结构
栈：栈是一种特殊的线性表，其只允许在一端进行插入和删除的操作，而进行插入删除操作的一端叫栈顶，另一端叫栈底。所以栈中的数据也遵从后进先出原则。
压栈：从栈顶压入数据的操作叫做压栈，也称为进栈或者出栈
出栈：从栈顶删除数据的操作叫做出栈
1.2 栈的实现
栈的实现一般使用数组或者是链表，相对而言，使用数组的优势更大，因为数组尾插尾删的效率高，相当契合栈的要求，而链表尾删需要遍历链表效率相比数组就低了许多。
接下来我们就用数组实现动态栈
1.2.1 栈的创建及其初始化
栈的创建：栈的结构体成员有三个，分别代表数组，栈顶，栈容
- // 支持动态增长的栈
- typedef int STDataType;
- typedef struct Stack
- {
- STDataType* _a;
- int _top; // 栈顶
- int _capacity; // 容量
- }Stack;
栈的初始化：我们先开辟4个空间的数组，然后给栈顶，容量赋值
- // 初始化栈
- void StackInit(Stack* ps)
- {
- assert(ps);
- STDataType* ptr = (STDataType*)malloc(4 * sizeof(STDataType));
- if (ptr == NULL)//检查开辟是否成功
- {
- perror("malloc");
- exit(-1);
- }
- ps->_a = ptr;
- ps->_top = 0;
- ps->_capacity = 4;
- }
1.2.2 入栈/出栈
入栈：入栈需要先检查容量，如果容量满了，就用realloc进行扩容，然后在插入数据即可
- // 入栈
- void StackPush(Stack* ps, STDataType data)
- {
- assert(ps);
- if (ps->_top == ps->_capacity)
- {
- STDataType* ptr =realloc(ps->_a,ps->_capacity*2*sizeof(STDataType));
- if (ptr == NULL)//检查开辟是否成功
- {
- perror("malloc");
- exit(-1);
- }
- ps->_a = ptr;
- ps->_capacity = ps->_capacity * 2;
- }
- ps->_a[ps->_top] = data;
- ps->_top++;
- }
出栈：出栈就很简单了，只需检查栈里是否有数据，无数据则无法删除，然栈顶--即可。
- // 出栈
- void StackPop(Stack* ps)
- {
- assert(ps);
- assert(StackEmpty(ps));
- ps->_top--;
- }
1.2.3 获取栈顶元素
这个需要注意的是，top指向的是栈顶元素的下一个位置，所以想要获取栈顶元素，需要的下标是top-1
- // 获取栈顶元素
- STDataType StackTop(Stack* ps)
- {
- assert(ps);
- assert(StackEmpty(ps));
-
- return ps->_a[ps->_top - 1];
- }
1.2.4 检查栈是否为空
只需返回top即可，如果top为0则为空
- // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
- bool StackEmpty(Stack* ps)
- {
- assert(ps);
- return ps->_top;
-
- }
1.2.5 销毁栈
释放数组即可
- // 销毁栈
- void StackDestroy(Stack* ps)
- {
- assert(ps);
- free(ps->_a);
- ps->_a = NULL;
- ps->_capacity = 0;
- ps->_top = 0;
- }
二、队列
2.1 队列的概念及结构
队列：只允许在一端进行插入，在另一端进行删除的特殊线性表，插入的一端叫队尾，删除的一端叫队头，遵从先进先出原则。
2.2 队列的实现
队列一般可以用数组或者链表实现，使用链表的结构更优一些，因为队列需要用到尾插头删，链表的头删和尾插都比数组要优秀。
下面就用链表实现队列
2.2.1 队列结构的创建及初始化
结构的创建：首先是创建链表的节点空间，然后在创建两个指针分别指向链表头和尾，再创建一个size记录队列的有效数据
- typedef int QDataType;
- typedef struct QueueNode
- {
- QDataType data;
- struct QueueNode* next;
- }QNode;
-
- typedef struct Queue
- {
- QNode* head;
- QNode* tail;
- int size;
- }Queue;
初始化：头尾指针置空，size置为0
- //初始化
- void QueueInit(Queue* pq)
- {
- assert(pq);
- pq->head = pq->tail = NULL;
- pq->size = 0;
- }
2.2.2 插入删除数据
插入数据：先给要插入的数据开辟一个新节点，然后只需要考虑一些第一次插入的特殊情况，其他按照链表的尾插即可
- //插入数据
- void QueuePush(Queue* pq, QDataType x)
- {
- assert(pq);
- QNode* newcode = (QNode*)malloc(sizeof(QNode));
- if (newcode == NULL)
- {
- perror("malloc");
- exit(-1);
- }
-
- if (pq->head == NULL)
- {
- newcode->data = x;
- newcode->next = NULL;
- pq->head = pq->tail = newcode;
- pq->size++;
- }
- else
- {
- newcode->data = x;
- newcode->next = NULL;
- pq->tail->next = newcode;
- pq->tail = pq->tail->next;
- pq->size++;
- }
- }
删除数据：需要检查是否为空，为空则无法删除，和链表头删类似
- //删除数据
- void QueuePop(Queue* pq)
- {
- assert(pq);
- assert(QueueEmpty(pq));
- QNode* cur = pq->head->next;
- free(pq->head);
- pq->head = cur;
- pq->size--;
-
- }
2.2.3 读取头尾数据
读取头数据：直接读取head指向的数据即可
- //读取头个数据
- QDataType QueueFront(Queue* pq)
- {
- assert(pq);
- assert(QueueEmpty(pq));
- return pq->head->data;
- }
读取尾数据：读取tail指向的数据即可
- //读取最后一个数据
- QDataType QueueBack(Queue* pq)
- {
- assert(pq);
- assert(QueueEmpty(pq));
- return pq->tail->data;
- }
2.2.4 判断是否为空
head和tail为空则为空
- //判断是否为空
- bool QueueEmpty(Queue* pq)
- {
- assert(pq);
- return pq->head && pq->tail;
- }
2.2.5 判断存储数据的数量
返回size即可
- //判断数据的数量
- int QueueSize(Queue* pq)
- {
- assert(pq);
- assert(QueueEmpty(pq));
- return pq->size;
- }
2.2.6 销毁队列
一个空间一个空间释放即可
- //释放空间
- void QueueDestroy(Queue* pq)
- {
- assert(pq);
- while (pq->head)//一个节点一个节点释放
- {
- QNode* cur = pq->head->next;
- free(pq->head);
- pq->head = cur;
- }
- pq->head = NULL;
- pq->tail = NULL;
- pq->size = 0;
- }
总结
以上就是今天要讲的内容，希望铁子们可以有所收货。
