当前位置:首页 » 《资源分享》 » 正文

栈和队列<数据结构 C版>

1 人参与  2024年09月05日 19:26  分类 : 《资源分享》  评论

点击全文阅读


目录

栈(Stack)

栈的结构体

初始化

销毁

入栈

判空

出栈

取栈顶元素

获取栈个数

测试:

队列(Queue)

队列的结构体

单个结点

队列

初始化

销毁

入队列,队尾

判空

出队列,队头

取队头数据

取队尾数据(非标准操作)

获取队列个数

测试:


栈(Stack)

栈是一种特殊的线性表,其只允许在特定的一端进行插入和删除操作。

进行插入和删除操作的一端叫做栈顶

另一端称为栈底

栈中的数据元素遵循后进先出LIFO(Last In First Out )的原则

压栈:栈的插入操作也被称为进栈、入栈,入数据在栈顶。

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

因为栈只在一端进行操作,所以栈的实现使用数组更加优越。


栈的结构体

//重命名,方便统一修改typedef int STDataType;typedef struct stack {STDataType* arr;int capacity;//栈的容量int top;//栈顶位置(有效元素个数)}ST;

初始化

//初始化void STInit(ST* ps) {assert(ps);//不能传入NULLps->arr = NULL;ps->capacity = ps->top = 0;}

销毁

//销毁void STDestory(ST* ps) {assert(ps);//不能传入NULLif (ps->arr) {//防止对NULL指针的引用(即栈为空的情况)free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;}

入栈

//入栈void STPush(ST* ps, STDataType x) {assert(ps);if (ps->capacity == ps->top) {//若空间不足int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//若栈容量为0,给定初始值,否则以两倍大小增长STDataType* p = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (!p) {//申请失败,直接返回perror("realloc fail!");exit(1);}ps->arr = p;ps->capacity = newcapacity;//改变原容量大小}ps->arr[ps->top++] = x;//先给栈顶赋值,在加加}

判空

//判空bool STEmpty(ST* ps) {assert(ps);return ps->top == 0;//返回bool值,直接返回比较运算符的返回值}

出栈

//出栈void STPop(ST* ps) {assert(ps && !STEmpty(ps));//不能传入NULL && 栈为空ps->top--;//出栈,让栈顶减减}

取栈顶元素

//取栈顶元素STDataType STTop(ST* ps) {assert(ps && !STEmpty(ps));//不能传入NULL && 栈为空return ps->arr[ps->top - 1];//返回栈顶元素,让栈顶减减}

获取栈个数

//获取栈有多少元素int STSize(ST* ps) {assert(ps);return ps->top;//直接返回栈顶下标(即元素个数)}

测试:


队列(Queue)

队列也是一种特殊的线性表,其在一端进行插入操作,另一端进行删除操作。

进行插入操作的一端叫做队尾(rear)。

进行删除操作的一端叫做队头(front)。

队列中的数据元素遵循后进先出FIFO(Frist In First Out )的原则

入队:队列的插入操作,一般发生在队尾

出队:队列的删除操作,一般发生在队头

因为队列在头部删除数据,使用数组,移动数据的时间复杂比较高,所以使用链表更优越。


队列的结构体

单个结点
//重命名,方便统一修改typedef int QDataType;//队列单个结点结构typedef struct QueueNode {QDataType data;//数据struct QueueNode* next;//下一个结点}QN;
队列
//队列结构typedef struct queue {QN* front;//队头QN* rear;//队尾int size;//结点数}Q;

初始化

//初始化队列void QueueInit(Q* pq) {assert(pq);pq->front = pq->rear = NULL;pq->size = 0;}

销毁

//销毁void QueueDestory(Q* pq) {assert(pq);assert(!QueueEmpty(pq));//队列为空,不用销毁QN* pcur = pq->front;while (pcur) {QN* next = pcur->next;free(pcur);//依次释放每一个结点pcur= next;}pq->rear = pq->front = NULL;//置队头队尾pq->size = 0;}

入队列,队尾

//入队列,队尾void QueuePush(Q* pq, QDataType x) {assert(pq);QN* node = (QN*)malloc(sizeof(QN));//开辟一个新结点if (!node) {//防止为空perror("malloc fail!");exit(1);}node->data = x;//data元素node->next = NULL;//next指针if (pq->front == NULL) {//若队列为空,队头队尾都要改变pq->front = pq->rear = node;}else {//若不为空,则改变尾结点指向pq->rear->next = node;pq->rear = node;}pq->size++;//队列元素++}

判空

//判空bool QueueEmpty(Q* pq) {assert(pq);return pq->size == 0;}

出队列,队头

//出队列,队头void QueuePop(Q* pq) {assert(pq);assert(!QueueEmpty(pq));//不能为空if (pq->front->next == NULL) {//若只有一个元素,队尾的指向也要发生改变free(pq->front);pq->front = pq->rear = NULL;}else {//若有多个元素,只用改变队头指向QN* del = pq->front;pq->front = pq->front->next;free(del);del = NULL;}pq->size--;}

取队头数据

//取队头数据QDataType QueueFront(Q* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->front->data;}

取队尾数据(非标准操作)

//取队尾数据QDataType QueueRear(Q* pq) {assert(pq);assert(!QueueEmpty(pq));return pq->rear->data;}

获取队列个数

//队列有效个数int QueueSize(Q* pq) {assert(pq);return pq->size;}

测试:


点击全文阅读


本文链接:http://zhangshiyu.com/post/155914.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1