温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

C语言数据结构的栈和队列详解

发布时间:2021-09-17 20:23:42 来源:亿速云 阅读:142 作者:chen 栏目:开发技术

这篇文章主要介绍“C语言数据结构的栈和队列详解”,在日常操作中,相信很多人在C语言数据结构的栈和队列详解问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”C语言数据结构的栈和队列详解”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

目录
    • 数组实现

    • 标题全部代码

      • Stack_array.c

      • Stack_array.h

      • 初始化数组栈

      • 满栈后扩容

      • 是否为空栈

      • 压栈和退栈

  • 链表实现

    • stack_chain.h

      • stack_chain.c

        • 整个压栈流程

          • 整个弹栈流程

            • 出栈情况

            • 队列

              • 队列的实现

                • queue_chain.h

                • queue_chain.c

              • 一个结构体类型用于维护这个队列

                • 概念流程图

                  • 入队列的实现

                    • 出队列的实现

                      • 是否空队

                      栈是一种以后进先出为顺序对对象进行添加或删除的数据结构
                      对栈进行形象记忆就像是桌子上的一堆书或一堆盘。对盘子取或者存盘子,都只能对最上面的书或者盘子进行操作。

                      C语言数据结构的栈和队列详解

                      对于栈而言,只有弹栈才能获取其数据。
                      当我们用C语言实现栈这个数据结构。
                      其实有三种方法实现

                      1,数组

                      2,单链表

                      3,双向链表

                      但是,对于双向链表,实现栈而言过于复杂。
                      可以选择数组或者单链表。

                      数组实现

                      标题全部代码

                      Stack_array.c
                      #include "Stack_array.h"
                      void InitStack(STstack* st)//栈的初始化
                      {
                      	st->top = 0;
                      	st->arr = (STData*)malloc(CAP*sizeof(STData));
                      	st->capacity = CAP;
                      }
                      void StackPush(STstack* st, STData n)//元素入栈
                      {
                      	if (st->top == st->capacity)//判断是否需要扩容
                      	{
                      		StackExpansion(st);
                      	}
                      	st->arr[st->top++] = n;
                      }
                      STData StackPop(STstack* st)//元素退栈
                      {
                      	assert(st);
                      	assert(!StackEmpty(st));//判断是否为空栈
                      	return st->arr[--st->top];
                      }
                      int StackEmpty(STstack* st)//判断栈是否为空
                      {
                      	if (st->top == 0)
                      		return 1;
                      	return 0;
                      }
                      void StackDestory(STstack* st)//销毁栈,防止内存泄漏
                      {
                      	free(st->arr);
                      	st->arr = NULL;
                      }
                      void StackExpansion(STstack* st)//扩容
                      {
                      	STData* tmp = (STData*)realloc((STData*)st->arr, sizeof(STData) * (st->capacity) * 2);
                      	if (tmp == NULL)
                      	{
                      		printf("Exparsion Error\n");
                      		exit(-1);
                      	}
                      	st->arr = tmp;
                      	st->capacity *= 2;
                      }
                      void StackPrint(STstack* st)//打印栈的元素,但前提是要退栈才能得到元素
                      {
                      	while(st->top)
                      	{
                      		STData ret = StackPop(st);
                      		printf("%d ", ret);
                      	}
                      }
                      Stack_array.h
                      #pragma once
                      #define _CRT_SECURE_NO_WARNINGS
                      #include <stdio.h>
                      #include <stdlib.h>
                      #include <assert.h>
                      #define CAP 4
                      typedef int STData;
                      typedef struct Stack//结构体用于维护栈
                      {
                      	int top;//栈顶标记
                      	STData* arr;//栈的指针
                      	int capacity;//栈的容量
                      }STstack;
                      void InitStack(STstack* st);//栈的初始化
                      void StackPush(STstack* st, STData n);//元素入栈
                      STData StackPop(STstack* st);//元素退栈
                      void StackExpansion(STstack* st);//扩容
                      int StackEmpty(STstack* st);//判断栈是否为空
                      void StackDestory(STstack* st);//销毁栈,防止内存泄漏
                      void StackPrint(STstack* st);//打印栈的元素,但前提是要退栈才能得到元素

                      对于数组实现而言。创建一个结构体用于维护整个栈。而其中有一个用于链接创建的数组。

                      typedef int STData;
                      typedef struct Stack//结构体用于维护栈
                      {
                      	int top;//栈顶标记
                      	STData* arr;//栈的指针
                      	int capacity;//栈的容量
                      }STstack;

                      作为数组栈,需要一个动态的数组。则这就需要一个Capacity作为衡量是否需要扩容的标准。而top需要作为入栈元素的位置。
                      当top的值等于Capacity时就意味着栈已经满了。因为数组是从0开始的

                      C语言数据结构的栈和队列详解

                      初始化数组栈

                      在初始化时,要先动态开辟一个数组空间,且,未压栈压入数据元素,其top要设为0.要保证当需要压栈时有明确指定的空间。同时,top的位置要为最后压入数据的下一个下标。

                      void InitStack(STstack* st)//栈的初始化
                      {
                      	st->top = 0;
                      	st->arr = (STData*)malloc(CAP*sizeof(STData));
                      	st->capacity = CAP;
                      }
                      满栈后扩容

                      其Capacity要作为判断是否满栈的标准。且,满栈后要进行扩容(因为是动态数组)。

                      void StackExpansion(STstack* st)//扩容
                      {
                      	STData* tmp = (STData*)realloc((STData*)st->arr, sizeof(STData) * (st->capacity) * 2);
                      	if (tmp == NULL)
                      	{
                      		printf("Exparsion Error\n");
                      		exit(-1);
                      	}
                      	st->arr = tmp;
                      	st->capacity *= 2;
                      }

                      同时,还要每次更改栈的容量,为下一次是否满栈作为标准。

                      是否为空栈
                      int StackEmpty(STstack* st)//判断栈是否为空
                      {
                      	if (st->top == 0)
                      		return 1;
                      	return 0;
                      }

                      其是否为空。也就是top的位置在数组的0下标位。

                      压栈和退栈
                      void StackPush(STstack* st, STData n)//元素入栈
                      {
                      	if (st->top == st->capacity)//判断是否需要扩容
                      	{
                      		StackExpansion(st);
                      	}
                      	st->arr[st->top++] = n;
                      }
                      STData StackPop(STstack* st)//元素退栈
                      {
                      	assert(st);
                      	assert(!StackEmpty(st));//判断是否为空栈
                      	return st->arr[--st->top];
                      }

                      压栈
                      每次压栈,都需要判断是否满栈,并决定是否扩容。
                      同时,当在原先top位置的数位置进行赋值。并之后要将top向后移动一个位置。保证下一次压栈。

                      退栈
                      退栈返回top的上一个位置的元素。同时top向前移动一个位置,不需要free,下次压栈会自动覆盖。

                      链表实现

                      stack_chain.h

                      #include <stdio.h>
                      #include <stdlib.h>
                      #define N 3
                      typedef struct stackele
                      {
                      	int n;
                      	int* point;
                      }sta;
                      sta* top;
                      void initstack(sta* a);//初始化栈
                      void pushstack(sta* a,int num);//入栈
                      //void printstack(sta* a);//打印栈
                      //void fullstack(sta* a);//检查是否满栈的情况
                      void emptystack(sta* a);//检查是否空栈的情况
                      int popstack(sta*a);//出栈

                      stack_chain.c

                      #include "stack_chain.h"
                      void initstack(sta* a)//初始化栈
                      {
                      	top= NULL;
                      }
                      void pushstack(sta* a, int num)//入栈
                      {
                      	sta* p = (sta*)malloc(sizeof(sta));
                      	p->n = num;//新节点赋值
                      	p->point = top;
                      	top = p;
                      }
                      int popstack(sta* a)//出栈
                      {
                      	emptystack(a);//检查是否空栈的情况
                      	int date;
                      	sta* des = top;
                      	top = top->point;
                      	date = des->n;
                      	free(des);
                      	des = NULL;
                      	return date;
                      }
                      void emptystack(sta* a)//检查是否空栈的情况
                      {
                      	if (top == NULL)
                      	{
                      		printf("Stack empty");
                      		exit(0);
                      	}
                      }

                      对于链表实现栈而言,和数组其实差不多。只不够,每次压栈都需要重新动态开辟一个新节点,并且链入栈中。但是,这并不是普通的直接链入。而是需要头插入栈。

                      C语言数据结构的栈和队列详解

                      这样头插入栈,可以方便退栈的时候,可以找到上一个元素。而压栈是不需要什么顺序。每一个压栈节点就是top节点。

                      整个压栈流程

                      C语言数据结构的栈和队列详解

                      void pushstack(sta* a, int num)//入栈
                      {
                      	sta* p = (sta*)malloc(sizeof(sta));
                      	p->n = num;//新节点赋值
                      	p->point = top;
                      	top = p;
                      }

                      整个弹栈流程

                      C语言数据结构的栈和队列详解

                      int popstack(sta* a)//出栈
                      {
                      	emptystack(a);//检查是否空栈的情况
                      	int date;
                      	sta* des = top;
                      	top = top->point;
                      	date = des->n;
                      	free(des);
                      	des = NULL;
                      	return date;
                      }

                      出栈情况

                      尤其要把握一个条件:空栈
                      由于不是数组,且链式结构的特性,是不需要扩容的。即不需要判断满栈的情况。
                      只考虑空栈的条件

                      void emptystack(sta* a)//检查是否空栈的情况
                      {
                      	if (top == NULL)
                      	{
                      		printf("Stack empty");
                      		exit(0);
                      	}
                      }

                      这里空栈的条件是top指针指向NULL时也就是

                      C语言数据结构的栈和队列详解

                      为什么呢?
                      因为每次弹栈的时候,都会free掉top指向的空间然后让top指向下一个节点。就这样不断移动。但是我设计初始化的时候是top= NULL;而且每次压栈都是p->point = top;这就会有一个标准来限定空栈的情况。

                      对于栈而言,其更像是一个递归的具象化。

                      队列

                      C语言数据结构的栈和队列详解

                      这种数据结构就像是银行柜台的取号机,
                      先取号的先去柜台。

                      始终满足先入先出的概念

                      队列的实现

                      queue_chain.h
                      #define _CRT_SECURE_NO_WARNINGS
                      #include <stdio.h>
                      #include <stdlib.h>
                      #include <assert.h>
                      typedef int QUData;
                      typedef struct queue
                      {
                      	QUData data;
                      	struct queue* next;
                      }queue;
                      typedef struct Queue//结构体用于维护队列
                      {
                      	queue* Dequeue;//队头指针
                      	queue* Enqueue;//队尾指针
                      }QUqueue;
                      void InitQueue(QUqueue* qu);//栈的初始化
                      void QueuePush(QUqueue* qu, QUData n);//元素入队
                      QUData QueuePop(QUqueue* qu);//元素出队
                      int QueueEmpty(QUqueue* qu);//判断队列是否为空
                      void QueueDestory(QUqueue* qu);//销毁队,防止内存泄漏
                      void QueuePrint(QUqueue* qu);//打印队列中的元素,但前提是要出队才能得到元素
                      queue_chain.c
                      #include "queue_chain.h"
                      void InitQueue(QUqueue* qu)//队列的初始化
                      {
                      	qu->Dequeue = qu->Enqueue = NULL;
                      }
                      void QueuePush(QUqueue* qu, QUData n)//元素入队
                      {
                      	queue* newcell = (QUData*)malloc(sizeof(QUData));
                      	newcell->data = n;
                      	newcell->next = NULL;
                      	if (qu->Dequeue == NULL)
                      	{
                      		qu->Enqueue = qu->Dequeue = newcell;
                      	}
                      	else
                      	{
                      		qu->Enqueue->next = newcell;
                      		qu->Enqueue = newcell;
                      	}
                      }
                      QUData QueuePop(QUqueue* qu)//元素出队
                      {
                      	if (QueueEmpty(qu))
                      	{
                      		printf("Queue Is Empty");
                      		exit(-1);
                      	}
                      	QUData ret = qu->Dequeue->data;
                      	qu->Dequeue = qu->Dequeue->next;
                      	return ret;
                      }
                      int QueueEmpty(QUqueue* qu)//判断队列是否为空
                      {
                      	if (qu->Dequeue == qu->Enqueue)
                      		return 1;
                      	return 0;
                      }
                      void QueueDestory(QUqueue* qu)//销毁队,防止内存泄漏
                      {
                      	queue* cur = qu->Dequeue;
                      	while (cur)
                      	{
                      		queue* pnext = cur->next;
                      		free(cur);
                      		cur = pnext;
                      	}
                      	qu->Dequeue = qu->Enqueue = NULL;
                      }
                      void QueuePrint(QUqueue* qu)//打印队列中的元素,但前提是要出队才能得到元素
                      {
                      	queue* cur = qu->Dequeue;
                      	while (cur)
                      	{
                      		printf("%d ", cur->data);
                      		cur = cur->next;
                      	}
                      }

                      队 毕竟是先入先出的数据结构。
                      所以要两个指针,
                      qu->Dequeue 指向队头,
                      qu->Enqueue 指向队尾,
                      不然每次都去找队尾是相当浪费时间的。

                      一个结构体类型用于维护这个队列

                      typedef int QUData;
                      typedef struct queue//描述每个队的元素
                      {
                      	QUData data;
                      	struct queue* next;
                      }queue;
                      typedef struct Queue//结构体用于维护队列
                      {
                      	queue* Dequeue;//队头指针
                      	queue* Enqueue;//队尾指针
                      }QUqueue;

                      队头指针负责出队,
                      队尾指针负责入队。

                      概念流程图

                      入队

                      C语言数据结构的栈和队列详解

                      C语言数据结构的栈和队列详解

                      C语言数据结构的栈和队列详解

                      C语言数据结构的栈和队列详解

                      入队列的实现

                      void QueuePush(QUqueue* qu, QUData n)//元素入队
                      {
                      	queue* newcell = (QUData*)malloc(sizeof(QUData));
                      	newcell->data = n;
                      	newcell->next = NULL;
                      	if (qu->Dequeue == NULL)
                      	{
                      		qu->Enqueue = qu->Dequeue = newcell;
                      	}
                      	else
                      	{
                      		qu->Enqueue->next = newcell;
                      		qu->Enqueue = newcell;
                      	}
                      }

                      **当然,入队列在刚开始的时候,头尾指针还是一起指向NULL。
                      当入第一个元素时,那个元素即是第一个元素也是最后一个元素。要独立判断。**这是一个特殊情况。

                      出队

                      C语言数据结构的栈和队列详解

                      C语言数据结构的栈和队列详解

                      C语言数据结构的栈和队列详解

                      出队列的实现

                      QUData QueuePop(QUqueue* qu)//元素出队
                      {
                      	if (QueueEmpty(qu))
                      	{
                      		printf("Queue Is Empty");
                      		exit(-1);
                      	}
                      	QUData ret = qu->Dequeue->data;
                      	qu->Dequeue = qu->Dequeue->next;
                      	return ret;
                      }

                      但是每次出队列都需要判断是否为空队。如果是空队还继续出队会相当于NULL->next ,这是直接报错的。

                      所以还要一个函数判断是否空队。

                      是否空队

                      int QueueEmpty(QUqueue* qu)//判断队列是否为空
                      {
                      	if (qu->Dequeue == qu->Enqueue)
                      		return 1;
                      	return 0;
                      }

                      空队就是相当于回到了初始化的情形

                      qu->Dequeue = qu->Enqueue = NULL;

                      也就是两者都指向同一处,也就是NULL。

                      到此,关于“C语言数据结构的栈和队列详解”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注亿速云网站,小编会继续努力为大家带来更多实用的文章!

                      向AI问一下细节

                      免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

                      AI