iis服务器助手广告广告
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言栈与队列如何定义
  • 752
分享到

C语言栈与队列如何定义

2023-06-30 16:06:15 752人浏览 薄情痞子
摘要

今天小编给大家分享一下C语言栈与队列如何定义的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。栈栈的定义栈是一种线性表,但限定这

今天小编给大家分享一下C语言栈与队列如何定义的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

栈的定义

栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作

C语言栈与队列如何定义

假设栈 【s = (a1,a2,……,an) 】,a1为栈底元素,an为栈顶元素。由于栈只能在栈顶进行插入和删除操作,所以进栈次序依次为【a1,a2,……,an】,出栈次序为【an,……,a2,a1】

由此可见:栈的操作特性可以明显地概括为后进先出

栈类似于线性表,它也有两种对应的存储方式分别为顺序栈和链栈。

顺序栈

顺序栈的定义

Q:什么是顺序栈?

A:采用顺序存储的栈成为顺序栈。它利用一组地址连续的存储单位存放自栈底到栈顶的数据元素,同时附设一个指针(top)来指示当前栈顶的位置。

栈的顺序存储类型可描述为

#define MaxSize 100//定义栈中元素的最大个数typedef struct{SElemtype *base;//栈底指针SElemtype *top;//栈顶指针 int stacksize//栈可用的最大容量 }SqStack;

顺序栈的初始化

Q:什么是顺序栈的初始化?

A:顺序栈的初始化操作就是为顺序栈动态分配一个最大容量为 MaxSize 的数组空间。

实现原理

  1. 为顺序栈动态分配一个最大容量为MAXSIZE的数组

  2. 栈顶指针top初始为base,表示栈为空

  3. stacksize置为栈的最大容量MaxSize

代码演示

Status InitStack(SqStack &S){//构造一个空栈SS. base=new SElemType[MaxSize];//为顺序栈动态分配一个最大容量为MAxsiniif(!S. base) exit(OVERFLOW);//存储分配失败S. top=S. base;//top初始为base,空栈S. stacksize=MaxSize;//stacksize置为栈的最大容量MaxSizereturn OK;}

顺序栈的入栈

Q:什么是顺序栈的入栈?

A:入栈操作是将新元素进入栈

实现原理

  1. 判断栈是否满了,若满了返回ERROR

  2. 将新元素压入栈,栈顶指针加1

代码演示

Status Push(SqStack&S,SElemType e){//插入元素e为新的栈顶元素if(S.top-S.base==S:stacksize) return ERROR;//栈满 *S. top++=e;   //元素e压入栈顶,栈顶指针加1return OK;}

顺序栈的出栈

Q:什么是顺序栈的出栈?

A:出栈操作是将栈顶元素删除

实现原理

  1. 判断栈是否空,若空则返回ERROR

  2. 栈顶指针减1,栈顶元素出栈

代码演示

Status Pop(SqStack &S,SElemType &e)(//删除S的栈顶元素,用e返回其值if(S.top==S.base) return ERROR;//栈顶指针减1,将栈顶元素赋给e   //栈顶指针减1,将栈顶元素赋给e e=*--S.top;return OK;)

取顺序栈的栈顶元素

Q:如何取顺序栈的栈顶元素?

A:当栈非空时,此操作返回当前栈顶元素的值,栈顶指针保持不变。

实现原理

  1. 判断栈是否空

  2. 返回栈顶元素的值,栈顶指针不变

代码演示

SElemType GetTop (SqStack S){//返回s的栈顶元素,不修改栈顶指针if(S.top!=S.base)         //栈非空    return*(S.top-1);//返回栈顶元素的值,栈顶指针不变)

链栈

采用链式存储的栈称为链栈。链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现。

栈的顺序存储类型可描述为

typedef struct Linknode{ElemType data;//数据域struct Linknode *next;//指针域} *LiStack;

采用链式存储,便于结点的插入与删除。链栈的操作与链表类似,入栈和出栈的操作都在链表的表头进行。

队列

队列的定义

队列是一种线性表,但限定这种线性表只能在表的一端进行插入,在另一端进行删除。允许删除的一端为队头,又称为队首,允许插入的一端为队尾

C语言栈与队列如何定义

队列与生活中的排队一样,最早排队的最先离开,队列的操作特性可以明显地概括为先进先出

队列有两种存储表示,分别为顺序表示与链式表示

队列的顺序表达与实现

队列顺序存储结构

和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次列头到队列尾的元素之外。还需附设两个整型变量【front】和【rear】分别指示队列头元素及队间的位置(后面分别称为头指针和尾指针)。

队列的顺序存储结构表示如下:

#define   MAXSIZE    100//队列容量typedef   struct {   ElemType *base;             //存储空间int front,rear;            //队首,队尾}SqQueue ;

假溢出

C语言栈与队列如何定义

图(1)所示为队列的初始状况。此时有【front == rear == 0】 成立。该条件可以作为队列判空的条件。

但是【rear == MAXSIZE】不能作为队列满的条件。为什么呢?

图(4)队列中只有一个元素,仍满足该条件。这时入队出现上溢出。但是这种溢出并不是真正的溢出,在队列中依然存在可以存放元素的空位置,所以是一种假溢出。

如何解决循环链表的这一缺点呢?

循环队列

Q:什么是循环队列?

A:将顺序队列臆造成一个环状的空间,即把存储队列元素的表从逻辑上视为一个环,称为循环队列。

循环队列的初始化

Q:什么是循环队列的初始化?

A:循环队列的初始化就是动态分配一个预定义大小为 MAXSIZE 的数组空间

????实现原理

  1. 为队列动态分配一个最大容量为MAXSIZE的数组空间

  2. base指向数组空间的首地址

  3. 头指针与尾指针置为零,表示队列为空

???? 代码演示

Status InitQueue ( SqQueue  &Q ){Q.base=new  ElemType[MAXSIZE];if(!Q.base)return OVERFLOW;Q.front=Q.rear=0;return OK;}

循环队列的入队

Q:什么是循环队列的入队?

A:入队操作是指在队尾插入一个新的元素

????实现原理

  1. 判断队列是否满

  2. 满了返回ERROR

  3. 将新元素插入队尾

  4. 队尾指针加一

???? 代码演示

Status EnQueue(SqQueue &Q,ElemType e){    if((Q.rear+1)%MAXSIZE==Q.front)//判满    return ERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;}

循环队列的出队

Q:什么是循环队列的出队?

A:出队操作是删除队头元素

????实现原理

  1. 判断队列是否为空

  2. 为空返回ERROR

  3. 保留队头元素

  4. 队头指针加一

???? 代码演示

Status DeQueue(SqQueue &Q, ElemType &e){    if( Q.rear==Q.front ) return ERROR;//判空e = Q.base[Q.front];Q.front = (Q.front+1)%MAXSIZE;return OK;}

链队列

Q:什么是链队列?

A:队列的链式表示称为链队列。它实际上是一个同时带有队头指针和队尾指针的单链表,头指针指向对头结点,尾指针指向队尾结点。

队列的链式存储如图:

C语言栈与队列如何定义

队列的链式存储类型可描述为:

typedef struct Qnode{       ElemType data;    struct QNode * next;}Qnode,*QueuePtr;                  //结点typedef struct { QueuePtr  front;QueuePtr rear;}LinkQueue;                       //链队

链栈的初始化

Q:什么是链队列的初始化?

A:链栈的初始化操作就是构建一个只有头结点的空队。

实现原理

  1. 生成新结点作为头结点

  2. 队头指针和队尾指针指向该结点

  3. 头指针的指针域置空

代码演示

Status InitQueue(LinkQueue &Q){Q.front=Q.rear=new QNode;p->next=NULL;return OK;}

链栈的入队

实现原理

  1. 为入队元素分配结点空间,用指针p指向

  2. 将新结点数据域置为e

  3. 将新结点插入到队尾

  4. 修改队尾指针为p

???? 代码演示

Status EnQueue(LinkQueue &Q,ElemType e){p=new QNode;//为入队元素分配结点空间,用指针p指向p->data=e;        //将新结点数据域置为ep->next=NULL;Q.rear->next=p;     //将新结点插入到队尾Q.rear=p;//修改队尾指针为preturn OK;}

链栈的出队

实现原理

  1. 判断是否为空,为空返回ERROR

  2. 保留头元素空间,以备释放

  3. 修改头指针的指针域,指向下一结点

  4. 判断出队元素是否是最后一个元素,若是,将队尾指针重新赋值,指向头结点

  5. 释放原队头元素的空间

代码演示

Status DeQueue(LinkQueue &Q,ElemType &e){if(Q.front==Q.rear)//若队列为空,返回ERRORreturn ERROR;QNode *p=Q.front->next;//保留头元素空间,以备释放Q.front->next=p->next;//修改头指针的指针域,指向下一结点    if(Q.rear==p)//判断出队元素是否是最后一个元素,若是,将队尾指针重新赋值,指向头结点Q.rear=Q.front; delete p;//释放原队头元素的空间return OK;}

以上就是“C语言栈与队列如何定义”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注编程网其他教程频道。

--结束END--

本文标题: C语言栈与队列如何定义

本文链接: https://www.lsjlt.com/news/330135.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • C语言栈与队列如何定义
    今天小编给大家分享一下C语言栈与队列如何定义的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。栈栈的定义栈是一种线性表,但限定这...
    99+
    2023-06-30
  • C语言 浅谈栈与队列的定义与操作
    目录栈的定义栈的实现前置初始化栈栈的销毁栈的插入出栈的操作取栈顶元素栈的大小队列的定义队列的基本操作队列的初始化队列的销毁队列的插入队列的删除队列的判空取出队头元素取出队尾元素队列的...
    99+
    2022-11-12
  • C语言栈与队列面试题详解
    目录1、括号匹配问题2、用队列实现栈3、用栈实现队列4、设计循环队列1、括号匹配问题 链接直达: 有效的括号 题目: 思路: 做题前,得先明确解题方案是啥,此题用栈的思想去解决是较...
    99+
    2022-11-13
  • C语言栈和队列如何实现
    这篇文章主要讲解了“C语言栈和队列如何实现”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C语言栈和队列如何实现”吧!一、栈与队列以及双端队列的概念1.1 栈的概念及结构栈:一种特殊的线性表,...
    99+
    2023-06-30
  • C语言栈与队列相互实现详解
    目录一、本章重点二、队列实现栈三、栈实现队列四、解题思路总结一、本章重点 用两个队列实现栈用两个栈实现队列解题思路总结 二、队列实现栈  我们有两个队列:  ...
    99+
    2022-11-13
  • C语言示例代码讲解栈与队列
    目录栈栈的定义顺序栈顺序栈的定义顺序栈的初始化顺序栈的入栈顺序栈的出栈取顺序栈的栈顶元素链栈队列队列的定义队列的顺序表达与实现队列顺序存储结构假溢出循环队列循环队列的初始化循环队列的...
    99+
    2022-11-13
  • C语言栈与队列怎么相互实现
    本篇内容介绍了“C语言栈与队列怎么相互实现”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!一、本章重点用两个队列实现栈用两个栈实现队列解题思路...
    99+
    2023-06-29
  • C语言循环队列与用队列实现栈问题解析
    目录循环队列题目描述题目链接思路分析代码实现用队列实现栈题目描述题目链接思路分析代码实现循环队列 循环队列: 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并...
    99+
    2022-11-13
  • C语言栈与队列面试题实例分析
    本文小编为大家详细介绍“C语言栈与队列面试题实例分析”,内容详细,步骤清晰,细节处理妥当,希望这篇“C语言栈与队列面试题实例分析”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。1、括号匹配问题链接直达:有效的括号题...
    99+
    2023-06-29
  • C语言怎么实现栈和队列
    本文小编为大家详细介绍“C语言怎么实现栈和队列”,内容详细,步骤清晰,细节处理妥当,希望这篇“C语言怎么实现栈和队列”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。什么是栈栈:一种特殊的线性表,其只允许在固定的一端...
    99+
    2023-06-30
  • C语言数据结构之队列的定义与实现
    目录一、队列的性质二、队列的结构三、代码实现头文件功能函数一、队列的性质 上次我们学习栈,了解到栈储存释放数据的方式是:先进后出 而队列与其相反,队列是:先进先出,后进后出。 二、队...
    99+
    2022-11-13
  • python中如何定义栈、队列及双端队列
    这篇文章给大家分享的是有关python中如何定义栈、队列及双端队列的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。1.线性数据结构的定义我们首先学习 4 种简单而强大的数据结构。栈、队列、双端队列和列表都是有序的数...
    99+
    2023-06-22
  • C语言数据结构之队列怎么定义与实现
    今天小编给大家分享一下C语言数据结构之队列怎么定义与实现的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。一、队列的性质上次我们...
    99+
    2023-07-02
  • C语言基于考研的栈和队列
    目录栈栈的基本操作三角矩阵总结栈 栈的基本操作 InitStack(&S):初始化 StackEmpty(S):判空,空则true,非空则fal...
    99+
    2022-11-12
  • C语言超详细讲解栈与队列实现实例
    目录1.思考-12.栈基本操作的实现2.1 初始化栈2.2 入栈2.3 出栈2.4 获取栈顶数据2.5 获取栈中有效元素个数2.6 判断栈是否为空2.7 销毁栈3.测试3.1 测试3...
    99+
    2022-11-13
  • C语言中用栈+队列实现队列中的元素逆置
    下面举例代码: 提到的Q是一个队列,S是一个空栈,实现将队列中的元素逆置的算法 #include<stdio.h> #define MaxSize 10 typedef ...
    99+
    2022-11-13
  • C语言数据结构之栈与队列的相互实现
    目录一、用对列实现栈代码实现二、用栈实现队列代码实现一、用对列实现栈 题干要求: 细节分析:队列是先进先出; 要实现的栈是先进后出。 解题思路:假设:先用一个队列储存数据 N 个,...
    99+
    2022-11-13
  • C语言数据结构之栈与队列怎么相互实现
    本篇内容介绍了“C语言数据结构之栈与队列怎么相互实现”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!一、用对列实现栈题干要求:细节分析:队列是...
    99+
    2023-07-02
  • C语言编程数据结构的栈和队列
    目录栈数组实现标题全部代码Stack_array.cStack_array.h初始化数组栈满栈后扩容是否为空栈压栈和退栈链表实现stack_chain.hstack_chain.c整...
    99+
    2022-11-12
  • C语言近万字为你讲透栈和队列
    目录一、栈与队列以及双端队列的概念1.1 栈的概念及结构1.2 队列的概念及结构1.3 双端队列的概念及结构二、栈的实现和模拟栈2.1 实现一个支持动态增长的栈2.2 数组模拟静态栈...
    99+
    2022-11-13
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作