数据结构 栈和队列
正文开始
1. 栈
1.1 栈的概念及结构
栈是线性表的一种，这种数据结构只允许在固定的一端进行插入和删除元素的操作，进行数据插入和删除的一端称为栈顶，另一端称为栈底。
这种数据结构的操作方式可以类比为弹匣，存取子弹只能在固定的一端（图源网络，侵删）
栈对应的两个操作：
- 压栈：栈的插入操作，又叫进栈/压栈/入栈，插入的数据在栈顶。
- 出栈：栈的删除操作，删除的数据同样在栈顶。
栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则
1.2 栈的实现
下面我们通过c语言来实现栈的结构以及相关操作。
实现栈的结构，我们可以通过顺序表或链表来实现，相对而言通过顺序表实现更好一些，因为顺序表对于尾部的操作效率更高一些。
对于栈我们提供出栈、入栈、判空等接口，下面来看具体代码：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int STDataType;
//通过顺序表来实现栈
typedef struct Stack {
STDataType* _a;
int _top;//栈顶
int _capacity;//容量
}Stack;
//初始化栈
void StackInit(Stack* ps) {
assert(ps);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
//检查空间是否足够
void CheckCapacity(Stack* ps)
{
if (ps->_top == ps->_capacity)
{
int NewCapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
STDataType* NewA = (STDataType*)realloc(ps->_a, sizeof(STDataType) * NewCapacity);
if (NewA == NULL)
{
perror("realloc fail");
}
ps->_capacity = NewCapacity;
ps->_a = NewA;
}
}
//入栈
void StackPush(Stack* ps, STDataType data) {
assert(ps);
CheckCapacity(ps);
*(ps->_a + ps->_top) = data;
ps->_top++;
}
//出栈
void StackPop(Stack* ps)
{
assert(ps && ps->_top > 0);
ps->_top--;
}
//获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps && ps->_top > 0);
return *(ps->_a + ps->_top - 1);
}
//获取栈中有效元素个数
int StatckSize(Stack* ps) {
assert(ps);
return ps->_top;
}
//检测栈是否为空，若为空则返回非零结果
//若不为空则返回0
int StackEmpty(Stack* ps) {
return ps->_top == 0;
}
//输出栈
void PrintStack(Stack* ps)
{
for (int i = 0; i < ps->_top; i++)
{
printf("%d ", *(ps->_a + i));
}
printf("\n");
}
//销毁栈
void StackDestroy(Stack* ps) {
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
}
值得注意的是，关于_top的指向问题，有两种情况：
- _top指向栈顶元素：初始化时应将_top指向 -1 的位置，因为它若指向 0 的位置，无法判断它是否为空。
- _top指向栈顶元素的下一个位置：初始化时应将_top指向 0 的位置，这样就代表栈为空。上述代码就是按照这种方式的实现的。
2. 队列
2.1 队列的概念及结构
队列：一种只允许在一端进行插入数据操作，在另一端进行删除数据操作的线性表，队列符合先进先出FIFO(First In First Out)
这种数据结构可以类比为排队出门，先进队伍的先出门。
队列对应的两个操作：
- 入队列：进行插入操作的一端称为队尾。
- 出队列：进行删除操作的一端称为队头。
2.2 队列的实现
队列也可以通过顺序表或链表来实现，相对而言使用链表更优一些，因为使用顺序表在队头出队列时效率较低。
下面我们通过c语言来实现对应的结构和相关操作：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int QDataType;
// 链式结构：表示队列的节点
typedef struct QListNode
{
struct QListNode* _next;// 指针域
QDataType _data; // 数据
}QNode;
// 在处理队列时，需要用到队列的队头指针和队尾指针
// 所以直接将描述一个队列的信息封装到一个结构体中
// 这样在处理队列时，只需要一个结构体变量就足够了
// 队列的结构
typedef struct Queue
{
QNode* _front; // 队头
QNode* _rear; // 队尾
int size; // 节点个数
}Queue;
// 初始化队列
void QueueInit(Queue* q) {
assert(q);
q->_front = q->_rear = NULL;
q->size = 0;
}
// 申请节点
QNode* QListBuyNode(QDataType x)
{
QNode* newNode = (QNode*)malloc(sizeof(QNode));
if (newNode == NULL)
{
perror("malloc fail");
exit(1);
}
newNode->_data = x;
newNode->_next = NULL;
return newNode;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* newNode = QListBuyNode(data);
if (q->size == 0)
{
q->_front = q->_rear = newNode;
}
else {
q->_rear->_next = newNode;
q->_rear = q->_rear->_next;
}
q->size++;
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q && q->size);
if (q->size == 1)
{
free(q->_front);
q->_front = q->_rear = NULL;
}
else {
QNode* PopNode = q->_front;
q->_front = q->_front->_next;
free(PopNode);
PopNode = NULL;
}
q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q) {
assert(q && q->size);
return q->_front->_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q) {
assert(q && q->size);
return q->_rear->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q) {
assert(q);
return q->size;
}
// 检测队列是否为空
// 如果为空返回非零结果
// 如果非空返回0
int QueueEmpty(Queue* q) {
assert(q);
return q->size == 0;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
assert(q);
while (q->_front) {
QueuePop(q);
}
q->_front = NULL;
q->_rear = NULL;
}
完
原文地址：https://blog.csdn.net/qq_67140973/article/details/143620557
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！