首页 > 其他分享 >栈和队列

栈和队列

时间:2023-08-16 21:03:07浏览次数:28  
标签:struct 队列 元素 链表 int 线性表

栈和队列

1,栈(stack)

栈是限定仅在表尾进行插入或者删除操作的线性表

栈  :线性表

->

一对一的关系

-》

数组

链表

栈是有限制的线性表(阉割版的线性表)

栈更重要的是一种思想

先进后出,后进先出

 

在程序设计或算法中,会经常用到这种思想

“撸串”

“死胡同堵车”

“压子弹”

 

栈顶(top):进行插入或者删除的那一端

栈尾(bottom):不允许进行插入或者删除的一端

 

栈的基本操作:

类型的实现

数组

链表

 

操作的实现

常用的操作

initStack:初始化栈

clearStack :清空栈 -》把栈的所有元素都干掉

destroyStack:销毁一个栈

pop:出栈

push:入栈(压栈)

不是很常用的操作

getTop:获取栈顶元素,但是不出栈

stackIsEmtpy:判断栈是否为空

stackLength:栈的长度

 

(1)顺序栈:用顺序结构的线性表来实现栈

顺序结构的线性表 -》 数组

 

栈顶和栈尾分别对应数组的哪一端比较好?

 

栈顶是经常要进行插入或者删除的,那么怎么方便你就怎么选

 

经过分析:选择a[n-1]这端做完栈顶,a[0]端作为栈尾

 

-》

typedef int ElemType;//栈元素的类型

#define MAX_ELEM_NUM 100

struct sqStack

{

ElemType stack[MAX_ELEM_NUM];//用来保存数据

int top;//栈顶元素在stack中的下标

}

typedef struct sqStack STACK;

 

 

(2)链式栈:用链式的线性表来实现栈

链式的线性表 -> 链表

typedef int ElemType;

struct node  //定义了一个新的类型,叫做 struct node

{

ElemType data;//存储数据        -》数据域

struct node * next;//存储下一个元素的地址,因为下一个

//元素和当前元素是一个类型,所以他的类型是

//struct node *      next ->指针域

};

typedef struct node NODE;//给struct node取一个别名NODE

 

struct stack  //<-这是我们声明的新类型  “头结点”

{

//这个头结点的成员变量,不是确定的,是按你的需求增加

//你觉得这个链表中,哪些信息对你比较重要或者经常用到

//你就保存它

int nodeNum;//用来保存链表中的节点的个数

NODE * first;//指向栈顶元素

NODE * last;//指向栈尾元素

//.......按需增加

};

typedef struct stack STACK;

 

first和last哪端作为栈顶比较好?

对于插入而言:头插和尾插都很方便

对于删除而言:删除first和删除last哪个方便?

删除first比较简单

->

采用first作为栈的栈顶

 

 

作业:

输入一个整数,然后倒序输出这个整数的各位数字,用栈实现

12345

->

5 4 3 2 1

 

设输入序列1、2、3、4,则下述序列中()不可能是出栈序列。

 

A. 1、2、3、4                      B. 4、 3、2、1

 

C. 1、3、4、2                      D.4、1、2、3  

 

 

1、若入栈序列是 a, b, c, d, e,则不可能的出栈序列是()。

 

(A) edcba(B)decba(C)dceab (D)abcde

 

 

2,        队列

 

栈和队列_链表

 

队列(Queue)是一种先进先出,后进后出的线性表。

它只允许在表的一端进行插入,在另一端进行删除。

队尾:允许插入的一端叫做队尾

对头:允许删除的一端叫队头

 

“排队”

队列更重要的是一种思想,“先进先出”

 

队列的实现

队列类型的实现

(1)顺序队列:用顺序结构的线性表来实现队列

“环形数组”

开辟一段连续的地址空间用来保存队列中的每一个元素 Q[]

定义两个变量,保存两个重要的信息:

1,d :队头元素的下标(打饭的阿姨的位置)

 

2,e : 下一个入队元素的下标

(下一位打饭的同学要加入的位置,其实就是当前队列队尾的下一个)

 

typedef int ElemType;//队列元素的类型

#define QUEUE_MAX_NUM 100

typedef struct SqQueue

{

ElemType queue[QUEUE_MAX_NUM];

int d;//队头下标

int e;//下一个队尾的下标

int num;//队列中元素的个数(当前排队的人数)

}SqQueue;

 

 

 

 

(2)链式队列:用链式结构的线性表来实现队列

链表

"带头结点的单向链表"

 

typedef int ElemType;//队列的元素

struct node

{

ElemType data;

struct node * next;

}

 

typedef struct node NODE;

typedef struct LkQueue

{

NODE * first;//指向队头元素

NODE * last;//指向队尾

int num;//队列中元素的个数

}LkQueue;

 

first指向队头,last指向队尾。因为队头要删除节点,作为单向链表而言,last作为对头的话,极不方便

 

设计好,实现起来就会轻松

设计不好,很麻烦

 

操作的实现

initQueue:初始化队列

clearQueue:清空一个队列

destroyQueue:销毁一个队列

EnQueue:入队

DeQueue:出队

 

getHead:返回队头元素

queueIsEmpty:是否为空

queueLength:返回队列元素的个数,即队列的长度

-----------------------------------------------------------

我们知道,线性表(链表,栈和队列),都是一个具有相同属性的数据

的集合。

集合中的元素:必须要是同一类型的?是的

 

那如果我需要用线性表保存不同类型的集合,是不是

就得写多份代码

现在一个项目中,既需要用到保存Int型数据的链表

又需要用到保存char型数据的链表

还需要用到保存double型数据的链表

也就是说需要三个或者多个不同类型的链表

那么是不是得把同一个代码写多份,才能满足

 

 

int double char ...... 

共同点?

我们可以保存他们的地址,因为他们的地址都是四个字节

 

 

作业:

求表达式的值

表达式是以字符串的形式输入

如:

char a[100] = "3+2*8-4*3+5-6+7/2+10-5";

//不考虑括号,运算符只考虑  ,所有的操作数都是int

 

1,创建两个栈s1 ,s2

s1  存操作数的栈

s2  存运算符的栈

 

2,按照要求把这个表达式的操作数和运算符入栈

flag        第一个操作数和第一个运算符直接入栈

 

后面的操作数x怎么处理呢?分两种情况

 

s2的栈顶元素c2与x的后面的运算符c1做比较(比较优先级)

 

如果c2<c1 :x直接入栈

如果c2>=c1:则计算 y c2 x的值 -》当做新的x

(y是s1的出栈元素,c2是s2的出栈元素,y和c2都需要出栈)

 

goto flag (循环什么时候结束?字符串入栈完毕)

 

3,把s1,s2出栈

 

进行运算 -》结果

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

标签:struct,队列,元素,链表,int,线性表
From: https://blog.51cto.com/u_16228319/7113188

相关文章

  • RabbitMq的死信队列
    参考博客:https://blog.csdn.net/weixin_59074080/article/details/130673121https://blog.csdn.net/m0_46979453/article/details/127229005https://zhuanlan.zhihu.com/p/582787597?utm_id=0什么是死信队列正常情况下,一条消息自生产者发布到broke,然后转发到队列中,最后被订阅......
  • 【单调队列】 单调队列的“扫描线”理解
    【单调队列】单调队列的“扫描线”理解  “如果一个选手比你小还比你强,你就可以退役了。”——单调队列的原理比你强,而且比你影响时间更长。某种意义上,数学思维是生活中的思考的延伸。  算法学习笔记(66):单调队列。引用Pecco的算法笔记。  在这里给出一种扫描线......
  • 3.1 C++ STL 双向队列容器
    双向队列容器(Deque)是C++STL中的一种数据结构,是一种双端队列,允许在容器的两端进行快速插入和删除操作,可以看作是一种动态数组的扩展,支持随机访问,同时提供了高效的在队列头尾插入和删除元素的操作。Deque双向队列容器与Vector非常相似,它不但可以在数组尾部插入和删除元素,还可以在......
  • 3.1 C++ STL 双向队列容器
    双向队列容器(Deque)是C++STL中的一种数据结构,是一种双端队列,允许在容器的两端进行快速插入和删除操作,可以看作是一种动态数组的扩展,支持随机访问,同时提供了高效的在队列头尾插入和删除元素的操作。Deque双向队列容器与Vector非常相似,它不但可以在数组尾部插入和删除元素,还可以在......
  • 代码随想录算法训练营第十三天|单调数列:滑动窗口最大值(力扣239.)、优先级队列:前k个高
    单调数列:滑动窗口最大值(力扣239.)给定滑动窗口的范围,求每个滑动窗口范围内的最大值使用单调队列实现对于最大值数字前面的数字不存入数列,对于最大值数字后面的数字存入数列中单调队列中数字的大小呈递减顺序pop(value):如果窗口移除的元素等于单调队列的队口元素,则pop;否则什......
  • Redis专题-队列
    Redis专题-队列首先,想一想Redis适合做消息队列吗?1、消息队列的消息存取需求是什么?redis中的解决方案是什么?无非就是下面这几点:0、数据可以顺序读取1、支持阻塞等待拉取消息2、支持发布/订阅模式3、重新消费4、消息不丢失5、消息可堆积那我们来看看redis怎么满足这些需......
  • 7.5 C/C++ 实现链表队列
    链表队列是一种基于链表实现的队列,相比于顺序队列而言,链表队列不需要预先申请固定大小的内存空间,可以根据需要动态申请和释放内存。在链表队列中,每个节点包含一个数据元素和一个指向下一个节点的指针,头节点表示队头,尾节点表示队尾,入队操作在队尾插入元素,出队操作在队头删除元素,队......
  • 循环队列
    为了避免当只有一个元素时,队头和队尾重合使得处理变得麻烦,所以引入两个指针front和rear。front即队头指针指向队头元素,rear即队尾指针指向队尾元素的下一个元素。这样当front等于rear是,不是队列中有一个元素,而是表示空队列。假设数组长度为5,空队列即初始状态如图所示,front和rear都......
  • 剑指 Offer 09. 用两个栈实现队列
    用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead操作返回-1)示例1:输入:["CQueue","appendTail","deleteHead","deleteHead","deleteHead"][[],[3],......
  • python 实现队列
    官方文档不推荐使用列表因为列表删除第一个元素会把剩余元素向左移一位速度很慢官方推荐的是collections下的deque 记录一下防止忘记 fromcollectionsimportdeque d=deque(‘内容’,maxlength)内容可以是推导式也可以直接写内容内容写在一起比如'123'结果会......