线性表之栈和队列
1.栈的表示和实现
1.1栈的概念及结构
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
1.2栈的实现
- 分析下用链表还是数组实现好？
- 答：都可以
栈顶top给1与-1：
代码实现：
Stack.h头文件：
// Created by zjc on 2024/11/3 21:47#pragma once#include "stdio.h"
#include "stdbool.h"
#include "stdlib.h"
#include "assert.h"typedef int STDataType;typedef struct Stack{// 一般使用动态，不使用静态STDataType * a;// 表示栈顶int top;int capacity;
}ST;// 0.初始化
void StackInit(ST * ps);// 0.销毁
void StackDestory(ST * ps);// 栈一定是在栈顶操作
// 1.入栈
void StackPush(ST * ps,STDataType x);// 删除栈顶元素
// 2.出栈
void StackPop(ST * ps);// 3.取栈顶数据
STDataType StackTop(ST * ps);// 4.求数据个数
int StackSize(ST * ps);// 5.判断是否为空,bool判断真假
bool StackEmpty(ST * ps);
Stack.c接口设置：
- 初始化：
#include "Stack.h"// 0.初始化
void StackInit(ST * ps){// 正常结构体的地址给我，是不能为空的assert(ps);// 开辟空间：先开辟4个intps->a = (STDataType*)malloc(sizeof(STDataType)*4);if(ps->a == NULL){ // 表示未分配成功printf("malloc fail\n");exit(-1);}// 容量,可以存4个数据ps->capacity =4;// 栈顶开始为0，指向的是栈顶元素的下一个ps->top = 0;
}
- 销毁：
// 0.销毁
void StackDestory(ST * ps){// 正常结构体的地址给我，是不能为空的assert(ps);// 释放psfree(ps->a);ps->a = NULL;// 同时将容量和栈顶置为0ps->top = ps->capacity = 0;
}
- 入栈：
// 1.入栈
void StackPush(ST * ps,STDataType x){assert(ps);// 容量满了就需要扩容if(ps->top == ps->capacity){// 直接扩容2倍STDataType * tmp = (STDataType*)realloc(ps->a,ps->capacity*2*sizeof(STDataType));// 如果扩容失败if(tmp == NULL){printf("realloc fail\n");// 终止程序exit(-1);}else{// 分配成功，赋值给ps->aps->a = tmp;// 容量变成原来2倍ps->capacity *= 2;}}// 插入一个元素，然后栈顶++ps->a[ps->top] = x;ps->top++;/** 如果之前top在栈顶，就要先++在放数据*/
}
- 出栈：
// 2.出栈
void StackPop(ST * ps){assert(ps);// 栈空了,调用pop,直接终止程序报错assert(ps->top > 0);// 直接减减ps->top--;
}
- 取栈顶数据：
// 3.取栈顶数据
STDataType StackTop(ST * ps){assert(ps);// 栈空了，调用pop,直接中止程序报错assert(ps->top > 0);return ps->a[ps->top-1];
}
- 求数据个数：
// 4.求数据个数
int StackSize(ST * ps){assert(ps);return ps->top;
}
- 判断是否为空：
// 5.判断是否为空,bool判断真假
bool StackEmpty(ST * ps){assert(ps);// 等于0则为真，为空；不等于0则为假不为空return ps->top == 0;
}
Test.h测试文件：
// Created by zjc on 2024/11/3 21:47
#include "Stack.h"int main() {ST st;// 初始化// 注意需要传指针(地址)，结构体是值传递StackInit(&st);StackPush(&st,1);StackPush(&st,2);StackPush(&st,3);// 入栈3个在出栈2个StackPop(&st);StackPop(&st);StackPush(&st,4);StackPush(&st,5);// 在入2个StackPush(&st,1);StackPush(&st,2);// 如果不为NULL就去取栈顶的数据while(!StackEmpty(&st)){printf(" %d", StackTop(&st));// 栈是不能随便遍历的// 取栈顶元素后出栈StackPop(&st);}printf("\n");// 销毁StackDestory(&st);return 0;
}
2.队列的表示和实现
2.1队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出
FIFO(First In First Out)入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头。
2.2队列的实现
实现方式：链表
头文件Queue.h：
// Created by zjc on 2024/11/5 16:31#pragma once#include "stdio.h"
#include "stdbool.h"
#include "stdlib.h"
#include "assert.h"typedef int QDataType;// 链式结构:表示队列
typedef struct QueueNode {struct QueueNode *next;QDataType data;
} QNode;// 队列结构：队头指针和队尾指针结构体
typedef struct Queue {QNode *head;QNode *tail;
} Queue;// 0.初始化
void QueueInit(Queue *pq);// 0.销毁
void QueueDestory(Queue *pq);// 1、队尾入
void QueuePush(Queue *pq, QDataType x);// 2.队头出
void QueuePop(Queue *pq);// 3.取队头数据
QDataType QueueFront(Queue *pq);// 4.取队尾数据
QDataType QueueBack(Queue *pq);// 5.取数据的个数
int QueueSize(Queue *pq);// 6.判断是否为空
bool QueueEmpty(Queue *pq);
Queue.c文件：
#include "Queue.h"// 0.初始化
void QueueInit(Queue *pq) {assert(pq);// 最开始将队首指针和队尾指针初始化为空pq->head = pq->tail = NULL;
}
1.队尾入
// 1.队尾入
void QueuePush(Queue *pq, QDataType x) {assert(pq);// 搞一个新节点QNode *newnode = (QNode *) malloc(sizeof(QNode));if (newnode == NULL) {printf("malloc fail\n");exit(-1);}// 对新开的节点初始化一下newnode->data = x;newnode->next = NULL;// 如果尾指针都是空的，那么就把节点给它if (pq->tail == NULL) {pq->head = pq->tail = newnode;} else {// 不是空，有节点就连接到节点的后面pq->tail->next = newnode;// 将tail移动到最后pq->tail = newnode;}
}
2.队头出
// 2.队头出
void QueuePop(Queue *pq) {assert(pq);// 判断队列是不等于空的assert(pq->head);// 分为一个节点和多个节点// 这里表示就只有一个节点了,释放掉后将tail和head都置为空// 防止野指针tailif (pq->head->next == NULL) {free(pq->head);pq->head = pq->tail = NULL;} else {// 保留head的下一个QNode *next = pq->head->next;free(pq->head);pq->head = next;}
}
3.判断空
// 3.判断是否为空:等于空则返回true否则false
bool QueueEmpty(Queue *pq) {assert(pq);return pq->head == NULL;
}
4.取队头数据
// 4.取队头数据
QDataType QueueFront(Queue *pq) {assert(pq);// 可以最后添加判断头是否为空,尾空则不调用assert(pq->head);// 直接返回头中的数据return pq->head->data;
}
5.取队尾数据
// 5.取队尾数据
QDataType QueueBack(Queue *pq) {assert(pq);assert(pq->head);return pq->tail->data;
}
6.取数据的个数
// 6.取数据的个数
int QueueSize(Queue *pq) {assert(pq);int size = 0;QNode *cur = pq->head;while (cur) {++size;cur = cur->next;}return size;
}
7.销毁
// 7.销毁
void QueueDestory(Queue *pq) {assert(pq);QNode *cur = pq->head;while (cur) {// 将下一个存储起来QNode *next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;
}
Test.c文件：
// Created by zjc on 2024/11/5 16:32
#include "Queue.h"void TestQueue(){Queue q;QueueInit(&q);QueuePush(&q,1);QueuePush(&q,2);// 出队列之前printf(" %d\n", QueueFront(&q));// 中途出一个QueuePop(&q);// 出队列之后printf(" %d\n", QueueFront(&q));QueuePush(&q,3);QueuePush(&q,4);while(!QueueEmpty(&q)){// 取队头数据，然后删除队头printf(" %d", QueueFront(&q));// 队头出,也是需要边删边出QueuePop(&q);}// printf("%d", QueueFront(&q));QueueDestory(&q);
}int main(){TestQueue();return 0;
}