精华内容
下载资源
问答
  • 队列中元素的删除
    千次阅读
    2019-11-06 16:33:07

    队列中可以用一级指针或者二级指针来进行元素的删除操作,若采用一级指针时,需找到删除元素的前一个元素,然后将删除元素的前一个元素的指针指向删除元素的后一个元素,然后再将要删除的元素delete;若采用二级指针,先移动指针的地址到要删除的元素位置 ppointer = &(pointer) ,注意不要直接更改二级指针的值*ppointer = pointer, 这样做会将前边的元素也一起删除。

    更多相关内容
  • 队列(Quene)的特征就是“先进先出”,队列把所有操作限制只能在线性结构的两端”进行,更具体一点:添加元素必须在线性表尾部进行,而删除元素只能在线性表头部进行。 先抽象接口IQuene namespace 栈与队列 { ...
  • 队列是一种列表,不同的是队列只能在末尾插入元素,队首删除元素。队列用于存储按顺序排列的数据。先进先出。这点和栈不一样,,最后入栈的元素反被优先处理。可以将队列想象成银行排队办理业务的人,排队...
  • 客服电话排队 键盘输入 各种被敲击到的键会进入到一个队列 记事本软件等的输出 把字符流按照队列顺序显示记事本,比如你敲击的是god,显示的就也是god,而不是dog,哈哈哈,先进先出 队列的抽象数据类型 ADT ...


    队列是一种FIFO(first in first out)线性表,它和栈一样,本质是线性表,但是不同的是他只允许在一端插入,另一端输出。

    允许插入的一端叫做队尾,允许删除的一端叫做队头。总是删除队头元素,插入总是插入到队尾。这无疑是一种非常符合人类生活习惯的数据结构,所以很好学。
    在这里插入图片描述
    虽然符合人类生活习惯,但是在程序设计中也一样用的极其频繁,下面是一些例子

    queue的应用举例(用了先进先出的排队思想的都算)

    • 电脑的鼠标操作
      在这里插入图片描述
      我有!原来如此!
    • 客服电话排队
      在这里插入图片描述
    • 键盘输入
      各种被敲击到的键会进入到一个队列
    • 记事本软件等的输出
      把字符流按照队列顺序显示在记事本中,比如你敲击的是god,显示的就也是god,而不是dog,哈哈哈,先进先出

    队列的抽象数据类型

    ADT Queue 
    Data//元素具有相同数据类型,相邻元素具有前驱后继关系。
    Operation
    	InitQueue(*Q);//建立一个空队列
    	DestroyQueue(*Q);//若Q存在,则销毁
    	ClearQueue(*Q);
    	QueueEmpty(*Q);
    	GetHead(*Q, *e);//把队头元素存入e
    	EnQueue(*Q, e);//把新元素插入到Q中
    	DeQueue(*Q, *e);//删除Q的队头元素,用e返回其值
    	QueueLength(*Q);
    endADT
    

    头尾相接的顺序存储结构:循环队列

    队列也是线性表,所以和栈一样,也有顺序存储结构和链式存储结构两种。

    顺序存储结构还是要用数组实现,但是并不是像栈那样简单地使用,而是要做成一个循环的队列。因为栈只在一端插入或删除,所以直接用数组,把数组为0那端作为栈底就妥了。

    但是如果简单地用数组直接实现队列,则数组索引较大的一端是队尾,这样便于插入新元素时直接插在数组下一个空位,则数组索引为0那边是队头,继续思考你就会发现问题了。队尾增加元素确实还比较方便的,时间复杂度是O(1)。但是队头元素的删除呢?如果我们假设只能把数据存在数组的前n个位置,则每次删除队头元素,就需要把所有后续元素往前移动一个位置,时间复杂度是O(n),如下图。
    在这里插入图片描述

    为了不移动后续所有元素,我们取消元素必须一直存在前N个位置的假设,而是用一个头指针front指向队头元素,和一个尾指针rear指向队尾元素的下一个内存位置。这样的话,删除队头元素只需要改变front指针,时间复杂度也变成O(1)了。插入到队尾只需要改一下rear指针,当然时间复杂度还是O(1)。

    如果rear指向队尾元素,则队列长度为1时,front和rear指向同一个位置,重合了,这样不便于处理,我们不希望front和rear指向同一个位置
    在这里插入图片描述

    你以为这样子的队列就丝滑完美了吗?不,还有问题。你想,不断删除队头结点会使得front指针不断后移,而rear指针不变。这时候用来实现队列的数组的前端有很多空位。如果这时候再往队列中不断添加新元素,知道队尾达到了数组的长度,这时候rear指针不断增大,直到指向数组后面那个内存位置,如上图右边,就不能再增加新元素了(这叫做假溢出),否则就会内存越界,可是明明数组的前端还有很多空位可用啊。

    为了解决假溢出,我们不要让rear指针指向数组后方内存,本身这样做也是很危险的,一般只有迫不得已才这样做,而让rear指针指向数组的头部,索引为0处,这样形成一个环,头尾相接,则可以利用数组前端空位。也永远不会出现指针指向不明的问题。

    所以,经过上面一番问题的出现和解决,我们设计出了顺序存储结构的队列:循环队列。我们也理解了为什么队列用顺序结构存储时必须是循环的,而栈不是。

    空队列和满队列中,front和rear重合

    让rear指针指向队尾元素的下一个位置,还是会有两种情况下,front会和rear相等:

    • 空队列:front == rear == someValue(我之前以为是NULL,后来发现并不是!因为使用数组实现,所以这里的front和rear指针实际是数组下标,是整数,所以不会是NULL)
    • 满队列: front == rear == someValue
      在这里插入图片描述
      由于空队列时俩指针也不是NULL,而是某个整数(数组下标),那怎么解决这个问题呢?有两个办法,都是用多用点空间的办法来换取两指针重合的情况判断。

    办法一:加一个标志变量flag

    设置一个标志变量flag,当标志为0且俩指针重合,则是空队列。这用了额外的一个字节,因为我们一般不会只分配一个比特,虽然表示这个标志位只需要一个比特。

    • 空队列:front == rear && flag == 0
    • 满队列:front == rear && flag == 1

    办法二:改变满队列的定义(用更多)

    满队列会遇到front和rear重合是因为我们把数组的空间全用完了。如果我们省出一个位置不用,即还剩一个位置为空时我们就认为队列已经满了,不能再插入新元素了,那么两个指针在满队列下也不会重合了。

    这样一来,就只有空队列会让两个指针重合了

    无需利用外部变量,直接利用队列本身就可以实现,所以这种办法用的更多。后面我们也只实现这种办法。

    如下图,左右都是新方案的满队列。用一个数组位置来换取指针重合的唯一性。

    在这里插入图片描述

    队列是否满的判断条件

    从上图可以看到,rear可能比front大,也可能比front小。满队列时,二者的差值可能是1,也可能是N-1(N是数组长度)。

    可以确定的是,如果rear比front大且队列为满,则一定是上图左边这种满队列情况,一大就大一整圈。front一定指向第一个位置(front = 0),而rear一定指向最后一个位置(rear = N - 1)
    r e a r = f r o n t + N − 1 = N − 1 rear = front+N - 1 = N - 1 rear=front+N1=N1

    如果rear比front小且队列为满,则一定是上图右边这样,rear比front小1
    r e a r = f r o n t − 1 rear = front - 1 rear=front1

    综合这两种情况可以发现,队列满一定有
    ( r e a r + 1 ) % N = f r o n t (rear + 1) \% N = front (rear+1)%N=front

    队列长度

    另外,不考虑队列是否为满,如果 r e a r > f r o n t rear>front rear>front,则队列长度为 r e a r − f r o n t rear - front rearfront,如上图左子图。
    如果 r e a r < f r o n t rear<front rear<front,则队列长度f分为两段,一段为 N − f r o n t N - front Nfront,另一端为 r e a r rear rear,如上图右子图。所以队列长度是
    N − f r o n t + r e a r N - front + rear Nfront+rear

    综合这两种情况,队列长度的通用公式则为:
    ( r e a r − f r o n t + N ) % N (rear - front + N) \% N (rearfront+N)%N

    总结来说,如果队列中数据元素的类型占用空间比较大,比如是某个类的对象,这个类有很多私有数据成员,则适合用第一种办法,如果队列中存储的数据的类型是int等类型,占用内存和1字节差不多的,对内存又不是特别严苛,就可以使用第二种办法。

    循环队列顺序存储结构相关代码

    队列结点的结构体

    Typedef struct
    {
    	ElemType data[SIZE];
    	int front;//无论数据类型是什么,指针类型都是整型
    	int rear;
    }SqQueue;
    

    初始化

    Status InitQueue(SqQueue * Q)
    {
    	Q->front = Q->rear = 0;
    	return OK;//使用数组,没有要求自己分配数组的内存,所以不需要malloc
    }
    

    求队列长度

    int QueueLength(SqQueue * Q)
    {
    	return (Q->rear - Q->front + SIZE) % SIZE;
    }
    

    入队列操作

    Status EnQueue(SqQueue * Q, ElemType e)
    {
    	if ((Q->rear + 1) % SIZE == Q->front)
    		return ERROR;//已满
    	Q->data[Q->rear] = e;
    	if (Q->rear == SIZE - 1)
    		Q->rear = 0;
    	else
    		++(Q->rear);
    	return OK;	
    }
    

    改变尾指针的那段代码可以简化为如下:

    Status EnQueue(SqQueue * Q, ElemType e)
    {
    	if ((Q->rear + 1) % SIZE == Q->front)
    		return ERROR;//已满
    	Q->data[Q->rear] = e;
    	Q->rear = (Q->rear + 1) % SIZE;
    	return OK;	
    }
    

    出队列操作

    Status DeQueue(SqQueue * Q, ElemType * e)
    {
    	if (Q->rear == Q->front)
    		return ERROR;//空
    	*e = Q->data[Q->front];
    	Q->front = (Q->front + 1) % SIZE;
    	return OK;
    }
    

    到此为止,我们学会了队列的顺序存储结构,用数组实现的循环队列,可以通过上面几个基本函数看到循环队列的时间复杂度还是很不错,入队,出队,返回队长度,初始化的时间复杂度全都是O(1)。

    但是他再好,也是顺序结构,即要底层要用数组实现,那么只要用数组就一定会有数组的缺点:需要提前设置数组长度,长度固定后不能改。这使得循环队列的灵活性差了一些,存的项最多就N-1个(有一个空着,为了使得满队列时两指针不重合,只有空队列才重合)。

    要让长度灵活,当然还是要选择链表,动态实时地分配,随用随分配内存,十分方便。

    队列的链式存储结构:链队列

    本质上就是线性表的单链表,只是他只能尾进头出罢了。

    front指针指向头结点(链表喜欢设置一个头结点以使得空队列和普通队列处理统一),rear指针指向最后一个结点(和循环队列不同)。
    在这里插入图片描述
    在这里插入图片描述

    队列的结点

    typedef struct QNode
    {
    	ElemType data;
    	struct QNode * next;
    }QNode, *QueuePtr;//这里写两个则struct不能是匿名的,且第一个和结构名一样.QueuePtr即QNode *
    

    队列的链表结构

    typedef struct
    {
    	QueuePtr front, rear;//只有队头队尾指针
    }LinkQueue;
    

    入队操作

    Status EnQueue(LinkQueue * Q, ElemType e)
    {
    	//不用判断是否已满,因为是链表
    	(QueuePtr) q = (QueuePtr)malloc(sizeof(ONode));\
    	if (!q)
    		return ERROR;//分配失败,或者写exit(OVERFLOW);
    	q->data = e;
    	q->next = NULL;
    	Q->rear->next = q;
    	Q->rear = q;
    	return OK;
    }
    

    出队操作

    Status DeQueue(LinkQueue * Q, ElemType * e)
    {
    	QNode * q;
    	if (Q->front == Q->rear)
    		return ERROR;//空
    	*e = Q->front->next->data;
    	q = Q->front->next;
    	Q->front = Q->front->next;
    	free(q);
    	return OK;
    }
    
    展开全文
  • 队列是一种列表,不同的是队列只能在队尾插入元素,队首删除元素。队列用于存储按顺序排列的数据,先进先出,这点和栈不一样(后入先出)。,最后入栈的元素反而被优先处理。我们现在可以把队列想象对我们去...
  •  队列就是只能在一端插入,而另一端删除的线性表,故队列又称为先进先出队列 队列类型有哪些? 循环队列和顺序队列  队列的存储实现方式有哪些? 顺序存储(数组)和链式存储(链表),此博文描述的是数组的实现...
  • 第 4 章 队列 4.1 知识点分析 1 队 列的基 本概念 1队列是一种特殊的只能在表的两端进行插入或删除操作的线性表允许插入元素的 一端称为队尾允许删除元素的一端称为队首 2队列的逻辑结构和线性表相同其最大特点是 ...
  • i=1,2,n, n0} 数据关系 R1{ ,ai > | ai-1, ai D, i=2,n} 约定其中a1 端为队列头 an 端为队列尾 基本操作 3.4 队列的类型定义 } ADT Queue 队列是一种先进先出的线性表只能在表头删除在表尾插入操作系统的作业排队...
  • 数据结构与算法—队列详解

    千次阅读 2019-08-16 01:18:41
    栈和队列是一对好兄弟,前面我们介绍过数据结构与算法—栈详解,那么栈的机制相对简单,后入先出,就像进入一个狭小的山洞,山洞只有一个出口,只能后进先出(外面的先出去)。而队列就好比是一个隧道,后面的人跟着...

    前言

    • 栈和队列是一对好兄弟,前面我们介绍过数据结构与算法—栈详解,那么栈的机制相对简单,后入先出,就像进入一个狭小的山洞,山洞只有一个出口,只能后进先出(在外面的先出去)。而队列就好比是一个隧道,后面的人跟着前面走,前面人先出去(先入先出)。日常的排队就是队列运转形式的一个描述!
    • 所以队列的核心理念就是:先进先出!
    • 队列的概念:队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头
    • 同时,阅读本偏文章最好先弄懂顺序表的基本操作栈的数据结构!学习效果更佳!
      在这里插入图片描述

    队列介绍

    基本属性

    队头front:

    • 删除数据的一端。对于数组从后面插入更容易,前面插入较困难,所以一般用数组实现的队列队头在前面。(删除直接index游标前进,不超过队尾即可)。而对于链表。插入删除在两头分别进行那么头部(前面)删除尾部插入是最方便的选择。

    队尾rear:

    • 插入数据的一端,同上,在数组和链表中通常均在尾部位置。当然,其实数组和链表的front和rear还有点小区别,后面会具体介绍。

    enQueue(入队):

    • 队尾rear插入元素

    deQueue(出队):

    • 对头front删除元素

    普通队列

    按照上述的介绍,我们很容易知道数组实现的方式。用数组模拟表示队列。要考虑初始化,插入,问题。
    在这里插入图片描述

    • 初始化:数组的front和rear都指向0.
    • 入队:队不满数组不越界,先队尾位置传值,再队尾下标+1
    • 出队:队不空,先取队头位置元素,在队头+1,

    但是很容易发现问题每个空间域只能利用一次。造成空间极度浪费。并且非常容易越界
    在这里插入图片描述

    循环队列

    针对上述的问题。有个较好的解决方法!就是对已经申请的(数组)内存重复利用。这就是我们所说的循环队列。

    而数组实现的循环队列就是在逻辑上稍作修改。我们假设(约定)数组的最后一位的下一个index是首位。因为我们队列中只需要front和tail两个指标。不需要数组的实际地址位置相关数据。和它无关。所以我们就只需要考虑尾部的特殊操作即可。

    • 初始化:数组的front和rear都指向0.
    • 入队:不满,先队尾位置传值,再rear=(rear + 1) % maxsize;
    • 出队:队不空,先取队头位置元素,front=(front + 1)%maxsize;
    • 是否为空:return rear == front;
    • 大小:return (rear+maxsize-front)%maxsize;

    这里面有几个大家需要注意的,就是指标相加如果遇到最后需要转到头的话。可以判断是否到数组末尾位置。也可以直接+1求余。其中maxsize是数组实际大小。
    在这里插入图片描述

    链式实现

    对于链表实现的队列,要根据先进先出的规则考虑头和尾的位置

    我们知道队列是先进先出的,对于链表,我们能采用单链表尽量采用单链表,能方便尽量方便,同时还要兼顾效率

    • 方案一 如果队头设在链表尾,队尾设在链表头。那么队尾进队插入在链表头部插入没问题。容易实现,但是如果队头删除在尾部进行,如果不设置尾指针要遍历到队尾,但是设置尾指针删除需要将它指向前驱节点那么就需要双向链表。都挺麻烦的。

    • 方案二但是如果队头设在链表头,队尾设在链表尾部,那么队尾进队插入在链表尾部插入没问题(用尾指针可以直接指向next)。容易实现,如果队头删除在头部进行也很容易,就是我们前面常说的头节点删除节点

    • 所以我们最终采取的是方案2的带头节点,带尾指针的单链表!

    主要操作为:

    • 初始化:
    public class listQueue<T> {
    	static class node<T> {
    		T data;// 节点的结果
    		node next;// 下一个连接的节点
    		public node() {}
    		public node(T data) {
    			this.data = data;
    		}
    	}
    	node front;//相当于head 带头节点的
    	node rear;//相当于tail/end
    	public listQueue() {
    		front=new node<T>();
    		rear=front;
    	}
    
    • 入队:rear.next=va;rear=va;(va为被插入节点)
      在这里插入图片描述
    • 出队:队不空,front.next=front.next.next;经典带头节点删除
      在这里插入图片描述
    • 是否为空:return rear == front;
    • 大小:节点front遍历到rear的个数。

    具体实现

    数组实现

    package 队栈;
    
    public class seqQueue<T> {
    	private T data[];// 数组容器
    	private int front;// 头
    	private int rear;// 尾
    	private int maxsize;// 最大长度
    
    	public seqQueue(int i)// 设置长为i的int 型队列
    	{
    		data = (T[]) new Object[i+1];
    		front = 0;
    		rear = 0;
    		maxsize = i+1;
    	}
    
    	public int  lenth() {
    		return (rear+maxsize-front)%maxsize;
    	}
    	public boolean isempty() {
    		return rear == front;
    	}
    
    	public boolean isfull() {
    		return (rear + 1) % maxsize == front;
    	}
    
    	public void enQueue(T i) throws Exception// 入队
    	{
    		if (isfull())
    			throw new Exception("已满");
    		else {
    			data[rear] = i;
    			rear=(rear + 1) % maxsize;
    		}
    	}
    
    	public T deQueue() throws Exception// 出队
    	{
    		if (isempty())
    			throw new Exception("已空");
    		else {
    			T va=data[front];
    			front=(front+1)%maxsize;
    			return va;
    		}
    	}
    
    	public String toString()// 输出队
    	{
    		String va="队头: ";
    		int lenth=lenth();
    		for(int i=0;i<lenth;i++)
    		{
    			va+=data[(front+i)%maxsize]+" ";
    		}
    		return va;
    	}
    
    }
    

    链式实现

    package 队栈;
    
    public class listQueue<T> {
    	static class node<T> {
    		T data;// 节点的结果
    		node next;// 下一个连接的节点
    		public node() {}
    		public node(T data) {
    			this.data = data;
    		}
    	}
    	node front;//相当于head 带头节点的
    	node rear;//相当于tail/end
    	public listQueue() {
    		front=new node<T>();
    		rear=front;
    	}
    	public int  lenth() {
    		int len=0;
    		node team=front;
    		while(team!=rear)
    		{
    			len++;team=team.next;
    		}
    		return len;
    	}
    	public boolean isempty() {
    		return rear == front;
    	}
    	public void enQueue(T value) // 入队.尾部插入
    	{
    		node va=new node<T>(value);
    		rear.next=va;
    		rear=va;
    	}
    
    	public T deQueue() throws Exception// 出队
    	{
    		if (isempty())
    			throw new Exception("已空");
    		else {
    			T va=(T) front.next.data;
    			front.next=front.next.next;
    			return va;
    		}
    	}
    	public String toString()
    	{
    		node team=front.next;
    		String va="队头: ";
    		while(team!=null)
    		{
    			va+=team.data+" ";
    			team=team.next;
    		}
    		return va;
    	}
    }
    
    

    測試

    在这里插入图片描述

    总结

    • 对于队列来说数据结构相比栈复杂一些,但是也不是很难,搞懂先进先出然后就用数组或者链表实现即可。
    • 对于数组,队尾tail指向的位置是空的,而链表的front(head一样)为头指针为空的,所以在不同结构实现相同效果的方法需要注意一下。
    • 对于双向队列,大家可以自行了解,双向队列两边均可插入删除,能够实现堆栈公用等更加灵活调用的结果。(参考java的ArrayDeque).并且现在的消息队列等很多中间件都是基于队列模型延申。所以学会队列很重要!
    • 最后,笔者水平有限,如果有纰漏和不足之处还请指出。另外,如果感觉不错可以点个赞,关注个人公众号bigsai 更多经常与你分享,关注回复数据结构获取精心准备的数据结构和算法资料多份!
      在这里插入图片描述
    展开全文
  • 题目:用队列实现栈 解题思路: 完整代码实现: 题目链接: 225. 用队列实现栈 - 力扣(LeetCode) (leetcode-cn.com) 题目:用队列实现栈 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的...

    目录

    一. 225. 用队列实现栈

    题目链接:

    题目:用队列实现栈

    题目讲解:

     完整代码实现:

    二.232. 用栈实现队列

     题目链接:

    题目:

    题目讲解:

    完整代码实现:

    三.622. 设计循环队列

     题目链接:

    题目:

    题目讲解:

    完整代码实现:


    一. 225. 用队列实现栈

    题目链接:

    225. 用队列实现栈 - 力扣(LeetCode) (leetcode-cn.com)

    题目:用队列实现栈

    请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

    实现 MyStack 类:

    void push(int x) 将元素 x 压入栈顶。
    int pop() 移除并返回栈顶元素。
    int top() 返回栈顶元素。
    boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
     

    注意:

    你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
    你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
     

    示例:

    输入:
    ["MyStack", "push", "push", "top", "pop", "empty"]
    [[], [1], [2], [], [], []]
    输出:
    [null, null, null, 2, 2, false]

    解释:
    MyStack myStack = new MyStack();
    myStack.push(1);
    myStack.push(2);
    myStack.top(); // 返回 2
    myStack.pop(); // 返回 2
    myStack.empty(); // 返回 False
     

    提示:

    1 <= x <= 9
    最多调用100 次 push、pop、top 和 empty
    每次调用 pop 和 top 都保证栈不为空

    题目讲解:

    前提是先有各种队列函数供使用!

    0.先创建一个结构体 MyStack (这个结构体变量就是我们创建的“栈”),“栈”中包含q1,q2两个队列,核心思想是:q1,q2中保持一个队列存储数据,另外一个队列空着;要出栈时,空队列用来倒数据,下面有出栈示意图(因为 队列是先进先出,栈是先进后出,所以主要是出栈需要改造)

    
    typedef struct {
        Queue q1;
        Queue q2;
    } MyStack;
    

     出栈示意图:假设开始q1中有1,2,5三个值,q2为空队列 ; 最终q1前N-1个数据给q2,最后一个数据删掉,实现了栈的后进先出(或者先进后出)

    逐个分析“栈”对应功能的函数:

    1.创建栈:先开辟一块 MyStack 类型的空间并赋值给 指针pst,同时断言检查是否为NULL,再把此空间中的两个队列变量q1和q2都用队列初始化函数进行初始化,并返回这个地址pst

    MyStack* myStackCreate() {
        MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
        assert(pst);
        QueueInit(&pst->q1);
        QueueInit(&pst->q2);
        return pst;
    }

    2.入栈: q1和q2一个是空的队列,一个是存数据的队列,方便后面出栈,通过 QueuePush 队列插入函数(相当于单链表尾插) 将数据给到不为空的队列中,因为刚开始都是空队列,所以给q1或q2都行,当其中一个为非空队列时,再次尾插就会尾插到这个非空队列中

    void myStackPush(MyStack* obj, int x) {
        assert(obj);
        if(!QueueEmpty(&obj->q1))
        {
            QueuePush(&obj->q1,x);
        }
        else
        {
            QueuePush(&obj->q2,x);
        }
    }


    3.出栈:把不为空的队列的数据前N-1导入另一个空队列,最后剩下的一个删掉。

     前面先找出空队列 emptyQ 和非空队列 nonEmptyQ ,讲空队列的前N-1个数据导入另一个空队列,最后剩下的一个删掉。

    int myStackPop(MyStack* obj) {
        assert(obj);
        Queue* emptyQ=&obj->q1;
        Queue* nonEmptyQ=&obj->q2;
        if(!QueueEmpty(&obj->q1))
        {
            emptyQ=&obj->q2;
            nonEmptyQ=&obj->q1;
        }
        while(QueueSize(nonEmptyQ)>1)
        {
        QDataType front=QueueFront(nonEmptyQ);
        QueuePush(emptyQ,front);
        QueuePop(nonEmptyQ);
        }
        QDataType top=QueueFront(nonEmptyQ);
        QueuePop(nonEmptyQ);
        return top;
    }

     4.找"栈"的栈顶:即最后一个结点的值,哪个队列不为空,就返回哪个队列的末尾节点的值。

    int myStackTop(MyStack* obj) {
        assert(obj);
        if(!QueueEmpty(&obj->q1))
        {
            return QueueBack(&obj->q1);
        }
        else
        {
            return QueueBack(&obj->q2);
        }
    }

     5.判断“栈”是否为空:只要q1和q2两个队列全为空队列就返回true

    bool myStackEmpty(MyStack* obj) {
        assert(obj);
        return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    }

    6.释放“栈”:销毁q1,q2两个队列,并free“栈”的地址空间即可

    
    void myStackFree(MyStack* obj) {
        assert(obj);
        QueueDestory(&obj->q1);
        QueueDestory(&obj->q2);
        free(obj);
    }

     完整代码实现:

    typedef int QDataType;
    
    typedef struct QueueNode
    {
    	QDataType data;
    	struct QueueNode* next;
    }QNode;
    
    typedef struct Queue
    {
    	QNode* head;
    	QNode* tail;
    }Queue;
    
    void QueueInit(Queue* pq);
    
    void QueueDestory(Queue* pq);
    
    void QueuePush(Queue* pq, QDataType x);
    
    void QueuePop(Queue* pq);
    
    bool QueueEmpty(Queue* pq);
    
    size_t QueueSize(Queue* pq);
    
    QDataType QueueFront(Queue* pq);
    
    QDataType QueueBack(Queue* pq);
    
    
    void QueueInit(Queue* pq)
    {
    	assert(pq);
    	pq->head = NULL;
    	pq->tail = NULL;
    }
    
    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;
    	
    }
    
    void QueuePush(Queue* pq, QDataType x)
    {
    	assert(pq);
    	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    	assert(newnode);
    	newnode->next = NULL;
    	newnode->data = x;
    
    	if (pq->tail == NULL)
    	{
    		assert(pq->head==NULL);
    		pq->head = pq->tail = newnode;
    	}
    		
    	else
    	{
    		pq->tail->next = newnode;
    		pq->tail = newnode;			//写的时候漏了!!!
    	}
    }
    
    void QueuePop(Queue* pq)
    {
    	assert(pq);
    	assert(pq->head && pq->tail);
    	if (pq->head == pq->tail)
    	{
    		free(pq->head);
    		pq->head = pq->tail = NULL;
    	}
    	else
    	{
    		QNode* next = pq->head->next;
    		free(pq->head);
    		pq->head = next;
    	}
    }
    
    bool QueueEmpty(Queue* pq)
    {
    	assert(pq);
    	//return pq->head == NULL && pq->tail == NULL;
    	return pq->head == NULL;
    }
    
    size_t QueueSize(Queue* pq)
    {
    	assert(pq);
    	size_t size = 0;
    	QNode* cur = pq->head;
    	while (cur)
    	{
    		size++;
    		cur = cur->next;
    	}
    	return size;
    }
    
    QDataType QueueFront(Queue* pq)
    {
    	assert(pq);
    	assert(pq->head);
    	return pq->head->data;
    }
    
    QDataType QueueBack(Queue* pq)
    {
    	assert(pq);
    	assert(pq->tail);
    	return pq->tail->data;
    
    }
    
    //——————————————————————————————————————————————————————以上是队列的操作
    
    typedef struct {
        Queue q1;
        Queue q2;
    } MyStack;
    
    
    MyStack* myStackCreate() {
        MyStack* pst=(MyStack*)malloc(sizeof(MyStack));
        assert(pst);
        QueueInit(&pst->q1);
        QueueInit(&pst->q2);
        return pst;
    }
    
    void myStackPush(MyStack* obj, int x) {
        assert(obj);
        if(!QueueEmpty(&obj->q1))
        {
            QueuePush(&obj->q1,x);
        }
        else
        {
            QueuePush(&obj->q2,x);
        }
    }
    
    int myStackPop(MyStack* obj) {
        assert(obj);
        Queue* emptyQ=&obj->q1;
        Queue* nonEmptyQ=&obj->q2;
        if(!QueueEmpty(&obj->q1))
        {
            emptyQ=&obj->q2;
            nonEmptyQ=&obj->q1;
        }
        while(QueueSize(nonEmptyQ)>1)
        {
        QDataType front=QueueFront(nonEmptyQ);
        QueuePush(emptyQ,front);
        QueuePop(nonEmptyQ);
        }
        QDataType top=QueueFront(nonEmptyQ);
        QueuePop(nonEmptyQ);
            // if(!QueueEmpty(&obj->q2))
            // printf("1111111");
            //     if(!QueueEmpty(&obj->q2))
            // printf("2222222");
        return top;
    }
    
    int myStackTop(MyStack* obj) {
        assert(obj);
        if(!QueueEmpty(&obj->q1))
        {
            return QueueBack(&obj->q1);
        }
        else
        {
            return QueueBack(&obj->q2);
        }
    }
    
    bool myStackEmpty(MyStack* obj) {
        assert(obj);
        return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
    }
    
    void myStackFree(MyStack* obj) {
        assert(obj);
        QueueDestory(&obj->q1);
        QueueDestory(&obj->q2);
        free(obj);
    }
    

    二.232. 用栈实现队列

     题目链接:

    232. 用栈实现队列 - 力扣(LeetCode) (leetcode-cn.com)

    题目:

    请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):

    实现 MyQueue 类:

    void push(int x) 将元素 x 推到队列的末尾
    int pop() 从队列的开头移除并返回元素
    int peek() 返回队列开头的元素
    boolean empty() 如果队列为空,返回 true ;否则,返回 false
    说明:

    你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    你所使用的语言也许不支持栈。你可以使用 list 或者 deque(双端队列)来模拟一个栈,只要是标准的栈操作即可。
     

    示例 1:

    输入:
    ["MyQueue", "push", "push", "peek", "pop", "empty"]
    [[], [1], [2], [], [], []]
    输出:
    [null, null, null, 1, 1, false]

    解释:
    MyQueue myQueue = new MyQueue();
    myQueue.push(1); // queue is: [1]
    myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
    myQueue.peek(); // return 1
    myQueue.pop(); // return 1, queue is [2]
    myQueue.empty(); // return false
     

    提示:

    1 <= x <= 9
    最多调用 100 次 push、pop、peek 和 empty
    假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)

    题目讲解:

    前提是先有各种 栈函数 供使用!

    0.这是第一题的兄弟题,跟上面操作差不多,唯一不同是不用来回倒数据(下面核心思想讲),这里也是先创建一个结构体 MyQueue (这个结构体变量就是我们创建的“队列”),“队列”中包含 pushST ,popST两个队列,核心思想是:因为 队列是先进先出,栈是先进后出,所以肯定主要还是改造 "出队列" ,把pushST中的数据拿到popST中是倒序,再出栈达到删除原顺序第一个数据的目的,即出队列的操作。

    typedef struct {
        ST pushST;
        ST popST;
    } MyQueue;
    

    1.创建“队列”函数:malloc一块MyQueue的空间obj (这个结构体变量就是我们创建的“队列”),初始化其中的两个栈,并返回这个“队列”的地址。

    MyQueue* myQueueCreate() {
        MyQueue* obj=( MyQueue*)malloc(sizeof( MyQueue));
        assert(obj);
        StackInit(&obj->pushST);
        StackInit(&obj->popST);
        return obj;
    }

    2.“队列”插入函数:就直接往pushST中插入就行了

    void myQueuePush(MyQueue* obj, int x) {
        assert(obj);
        StackPush(&obj->pushST, x);
    }

    3.“队列”删除函数:如果popST中无数据就不能删数据,需要从pushST中拿数据,当pushST中有数据才能拿,如果pushST中有数据 1,2,3,4,先用 StackTop(&obj->pushST) 找到pushST中的尾数据 4,再通过 StackPush(&obj->popST, StackTop(&obj->pushST)); 把这个数据放到popST中,再用 StackPop(&obj->pushST); 删掉pushST里的尾数据 4,一直这样重复到pushST中数据拿完,此时popST中数据就是4,3,2,1,输出并删除pushST的尾数据 1 就达到了删除原顺序 1,2,3,4 中的首数据1,进而达到了出队列的效果 。(如下动图所示)

    int myQueuePop(MyQueue* obj) {
        assert(obj);
        if(StackEmpty(&obj->popST))
        {
            while(!StackEmpty(&obj->pushST))
            {
                StackPush(&obj->popST, StackTop(&obj->pushST));
                StackPop(&obj->pushST);
    
            }
        }
        int front =StackTop(&obj->popST);
        StackPop(&obj->popST);
        return front;
    }
    

    如果一直出队列,删除1->删除2->删除3->删除4,删完了,如果又用 myQueuePush 添加了数据(例如5,6,7,8),就依旧把pushST中的数据出栈到popST中,再输出删除popST中的尾数据(如下动图)

     上图就相当于

     如果pushST也没数据,if条件进去后不进while条件,就结束了。

     4.找“队列”头数据函数:如果popST空,也要从pushST拿数据,跟上面函数操作一样,最后返回popST尾数据,相当于原顺序数据的头数据。

    int myQueuePeek(MyQueue* obj) {
            assert(obj);
        if(StackEmpty(&obj->popST))
        {
            while(!StackEmpty(&obj->pushST))
            {
                StackPush(&obj->popST, StackTop(&obj->pushST));
                StackPop(&obj->pushST);
            }
        }
        return StackTop(&obj->popST);
    }
    

    5.判断“队列是否为空”函数:两个栈都是空,则整个“队列”就为空。

    bool myQueueEmpty(MyQueue* obj) {
        assert(obj);
        return StackEmpty(&obj->pushST)&& StackEmpty(&obj->popST);
    }

    6.释放函数:销毁两个栈,最后因为  myQueueCreate() 函数malloc的obj结构体空间,最后也要free(obj);

    void myQueueFree(MyQueue* obj) {
        assert(obj);
        StackDestory(&obj->pushST);
        StackDestory(&obj->popST);
        free(obj);
    }

    完整代码实现:

    typedef int STDataType;
    typedef struct Stack
    {
    	STDataType* a;
    	int top;
    	int capacity;
    }ST;
    
    void StackInit(ST* ps);
    void StackDestory(ST* ps);
    void StackPush(ST* ps, STDataType x);
    void StackPop(ST* ps);
    bool StackEmpty(ST* ps);
    int StackSize(ST* ps);
    STDataType StackTop(ST* ps);
    
    void StackInit(ST* ps)
    {
    	assert(ps);
    	ps->a = NULL;
    	ps->capacity =  0;
    	ps->top = 0;
    }
    
    void StackDestory(ST* ps)
    {
    	assert(ps);
    	free(ps->a);
    	ps->a = NULL;
    	ps->capacity = ps->top = 0;
    }
    
    void StackPush(ST* ps, STDataType x)//入栈	复盘
    {
    	assert(ps);
    	if (ps->top == ps->capacity)
    	{
    		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		ps->a = (STDataType*)realloc(ps->a,sizeof(STDataType)*newcapacity);
    		if (ps->a == NULL)
    		{
    			printf("realloc fail\n");
    			exit(-1);
    		}
    		ps->capacity = newcapacity;
    	}
    	ps->a[ps->top] = x;
    	ps->top++;
    }
    
    void StackPop(ST* ps)	//StackTop+StackPop => 出栈
    {
    	assert(ps);
    	assert(ps->top>0);
    	--ps->top;
    }
    
    bool StackEmpty(ST* ps)
    {
    	assert(ps);
    	//if (ps->top > 0)
    	//	return false;
    	//else
    	//	return true;
    	return ps->top == 0;
    }
    
    STDataType StackTop(ST* ps)
    {
    	assert(ps);
    	assert(ps->top > 0);
    	return ps->a[ps->top - 1];
    }
    
    int StackSize(ST* ps)
    {
    	assert(ps);
    	return ps->top;
    }
    
    
    //————————————————————————————————————————————————————————————————以上是栈操作
    
    typedef struct {
        ST pushST;
        ST popST;
    } MyQueue;
    
    
    MyQueue* myQueueCreate() {
        MyQueue* obj=( MyQueue*)malloc(sizeof( MyQueue));
        assert(obj);
        StackInit(&obj->pushST);
        StackInit(&obj->popST);
        return obj;
    }
    
    void myQueuePush(MyQueue* obj, int x) {
        assert(obj);
        StackPush(&obj->pushST, x);
    }
    
    int myQueuePop(MyQueue* obj) {
        assert(obj);
        if(StackEmpty(&obj->popST))
        {
            while(!StackEmpty(&obj->pushST))
            {
                StackPush(&obj->popST, StackTop(&obj->pushST));
                StackPop(&obj->pushST);
    
            }
        }
        int front =StackTop(&obj->popST);
        StackPop(&obj->popST);
        return front;
    }
    
    int myQueuePeek(MyQueue* obj) {
            assert(obj);
        if(StackEmpty(&obj->popST))
        {
            while(!StackEmpty(&obj->pushST))
            {
                StackPush(&obj->popST, StackTop(&obj->pushST));
                StackPop(&obj->pushST);
            }
        }
        return StackTop(&obj->popST);
    }
    
    bool myQueueEmpty(MyQueue* obj) {
        assert(obj);
        return StackEmpty(&obj->pushST)&& StackEmpty(&obj->popST);
    }
    
    void myQueueFree(MyQueue* obj) {
        assert(obj);
        StackDestory(&obj->pushST);
        StackDestory(&obj->popST);
        free(obj);
    
    }

    三.622. 设计循环队列

     题目链接:

    622. 设计循环队列 - 力扣(LeetCode) (leetcode-cn.com)

    题目:

    设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

    循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

    你的实现应该支持如下操作:

    MyCircularQueue(k): 构造器,设置队列长度为 k 。
    Front: 从队首获取元素。如果队列为空,返回 -1 。
    Rear: 获取队尾元素。如果队列为空,返回 -1 。
    enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
    deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
    isEmpty(): 检查循环队列是否为空。
    isFull(): 检查循环队列是否已满。
     

    示例:

    MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
    circularQueue.enQueue(1);  // 返回 true
    circularQueue.enQueue(2);  // 返回 true
    circularQueue.enQueue(3);  // 返回 true
    circularQueue.enQueue(4);  // 返回 false,队列已满
    circularQueue.Rear();  // 返回 3
    circularQueue.isFull();  // 返回 true
    circularQueue.deQueue();  // 返回 true
    circularQueue.enQueue(4);  // 返回 true
    circularQueue.Rear();  // 返回 4

    题目讲解:

    0. 次循环队列有数组和单链表两个底层结构,该选哪一个呢?

    答:选数组较好。实际上两者各有优劣,其实都差不多,

    选数组的原因:

    数组的优点:(也是单链表的缺点)   因为tail只能指向末尾数据的下一个地址,如果要找尾结点数据时,单链表找tail的上一个节点很费劲,数组就只需要tail-1就能找到。

    数组的缺点:(也是单链表的优点)    如果是数组结构,当tail到最后一个节点时,为了成为循环队列结构,需要手动让tail=0,单链表就不用手动赋值。

    0.0 创建结构体 MyCircularQueue ,包含数组队列int* a,整形front代表队列头部的角标,tail代表队列尾部的角标,k代表能存几个数据

    typedef struct {
        int* a;
        int front;
        int tail;
        int k;
    } MyCircularQueue;

     接下来逐一分析我们创建的循环队列对应的各个函数:

    1.创建循环队列函数:开辟一个循环队列的结构体的空间,地址名叫obj,通过下面动态图①发现:最开始front=tail=0,每增加一个数据,tail++,当增加k个(假设k=4)数据时,tail又不得不回到角标0处,此时front=tail=0,这样空列表和慢列表无法区分,(图②)为了避免空和满混淆,多开一个空间,front == tail时是空,tail的下一个位置是front就是满

    MyCircularQueue* myCircularQueueCreate(int k) {
        MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
        obj->a=(int*)malloc(sizeof(int)*(k+1));
        obj->front=obj->tail=0;
        obj->k=k;
        return obj;
    }

     图①

     图②

     

     2.入“队列”函数:“队列”结构体:

    typedef struct {

        int* a;

        int front;

        int tail;

        int k;

    } MyCircularQueue;

    通常是将value赋给数组队列的最后一个值,然后tail++即可,但是也应考虑 满队列 和 tail走到头(obj->tail=k)两种情况:满队列应提前用 myCircularQueueIsFull(obj) 判断队列是否满的函数,如果是true,说明队列已满,返回布尔值false说明添加失败;当tail走到头,obj->tail==obj->k 成立,就将tail置为0,达到队列循环的作用,否则就是正常情况,直接obj->tail++即可。最终返回布尔值true说明添加成功。

    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
        assert(obj);
        obj->a[obj->tail]=value;
        if(myCircularQueueIsFull(obj))
            return false;
        if(obj->tail==obj->k)
            obj->tail=0;
        else
            obj->tail++;
            return true;
    }

     3.“队列”删除函数:队列是头删,正常情况是质疑删一个,obj->front++即可,但要考虑到“空队列”和front走到头 两种情况:提前利用下面的判空函数 myCircularQueueIsEmpty(obj) ,如果此函数为true,说明队列为空,不能再删除,return false,表明删除失败;front走到头时,即obi->front==obj->k成立,就把front置为0,达到循环的目的,否则为正常情况,直接obj->front++即可,只要删除成功,就return true。

    bool myCircularQueueDeQueue(MyCircularQueue* obj) {
        assert(obj);
        if(myCircularQueueIsEmpty(obj))
            return false;
        if(obj->front==obj->k)
        {
            obj->front=0;
        }
        else
        {
            obj->front++;
        }
        return true;
    }

    4.查找“队列”头部数值的函数:如果是空队列就返回-1(题目要求),不空就返回数组队列头部的那个值。

    int myCircularQueueFront(MyCircularQueue* obj) {
        assert(obj);
        if( myCircularQueueIsEmpty(obj))
            return -1;
        return obj->a[obj->front];
    }

    5.查找“队列”尾部数值的函数:如果是空队列就返回-1(题目要求),因为tail是最后一个数据的下一个结点的地址,所以不空也有两种情况:如果obj->tail是整个队列的第一个数据的角标,那他的上一个数据就是尾数据,因为当obj->tail=obj->k时,再添加数据,tail因为循环又要回到头部,即obj->tail=0,这个情况就直接返回尾数据 obj->a[obj->k] 即可。否则就是正常情况,返回tail位置的上一个值即可。

    int myCircularQueueRear(MyCircularQueue* obj) {
        assert(obj);
        if( myCircularQueueIsEmpty(obj))
            return -1;
        if(obj->tail==0)
            return obj->a[obj->k];
        else
            return obj->a[obj->tail-1];
    }

    6.检查“队列”是否为空函数:当front和tail相等时,说明队列为空。

    bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
        assert(obj);
        return obj->front==obj->tail;
    }

    7.检查“队列”是否已满 函数:正常情况是:当tail的下一个位置的角标和front相等时,即为满队列。但考虑特殊情况 obj->tail=obj->k 时,tail的下一个位置是头坐标,所以就是obj->tail=obj->k的同时obj->front=0,也是满队列的情况。要考虑全!

    bool myCircularQueueIsFull(MyCircularQueue* obj) {
        assert(obj);
        if(obj->tail==obj->k && obj->front==0)
            return true;
        return obj->tail+1==obj->front;
    }
    

    8.释放“队列” 函数:释放两个空间,分别是结构体“队列”中的数组a,其实就是结构体obj本身的空间也要释放。

    void myCircularQueueFree(MyCircularQueue* obj) {
        assert(obj);
        free(obj->a);
        free(obj);
    }

    完整代码实现:

    typedef struct {
        int* a;
        int front;
        int tail;
        int k;
    } MyCircularQueue;
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj);
    bool myCircularQueueIsFull(MyCircularQueue* obj);
    
    MyCircularQueue* myCircularQueueCreate(int k) {
        MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
        obj->a=(int*)malloc(sizeof(int)*(k+1));
        obj->front=obj->tail=0;
        obj->k=k;
        return obj;
    }
    
    bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
        assert(obj);
        obj->a[obj->tail]=value;
        if(myCircularQueueIsFull(obj))
            return false;
        if(obj->tail==obj->k)
            obj->tail=0;
        else
            obj->tail++;
            return true;
    }
    
    bool myCircularQueueDeQueue(MyCircularQueue* obj) {
        assert(obj);
        if(myCircularQueueIsEmpty(obj))
            return false;
        if(obj->front==obj->k)
        {
            obj->front=0;
        }
        else
        {
            obj->front++;
        }
        return true;
    }
    
    int myCircularQueueFront(MyCircularQueue* obj) {
        assert(obj);
        if( myCircularQueueIsEmpty(obj))
            return -1;
        return obj->a[obj->front];
    }
    
    int myCircularQueueRear(MyCircularQueue* obj) {
        assert(obj);
        if( myCircularQueueIsEmpty(obj))
            return -1;
        if(obj->tail==0)
            return obj->a[obj->k];
        else
            return obj->a[obj->tail-1];
    }
    
    bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
        assert(obj);
        return obj->front==obj->tail;
    }
    
    bool myCircularQueueIsFull(MyCircularQueue* obj) {
        assert(obj);
        if(obj->tail==obj->k && obj->front==0)
            return true;
        return obj->tail+1==obj->front;
    }
    
    void myCircularQueueFree(MyCircularQueue* obj) {
        assert(obj);
        free(obj->a);
        free(obj);
    }

    展开全文
  • 队列是一种先入先出的数据结构(FIFO),只允许前端(front)删除后端(rear)插入。容量为capacity大小的内存,只能存capacity-1的元素,其中rear的位置始终为空。 本文实现的队列,功能如下: 1 获取元素内容 ...
  • 数据结构习题——栈和队列(二)

    千次阅读 2021-06-06 18:32:30
    对于队列只能在 队尾 插入和 队头 删除元素。 2. 队列 是被限定为只能表的一端进行插入运算,表的另一端进行删除运算的线性表。 3. 具有n个单元的循环队列,队满时共有 n-1 个元素。 4. 带表头结点的空...
  • 队列-Java实现队列数据结构

    千次阅读 2020-03-18 18:05:37
    1、队列的基本概念 队列(queue)是一种特殊的线性表,特殊之处在于它只允许表的前端(front)进行删除操作, ...在队列中插入一个队列元素称为入队,从队列中删除一个队列元 素称为出队。因为队列只允许一...
  • java数据结构——队列

    千次阅读 2019-02-21 17:12:33
    上一篇博客我们拒了羽毛球筒的例子来类比栈这种数据结构,这次我们用排队这种模型来类比我们接下来要说的数据结构——队列
  • 数据结构:栈和队列(Stack & Queue)【详解】

    万次阅读 多人点赞 2021-02-18 19:52:33
    首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作。 栈顶(Top):线性表允许进行插入删除的那一端。 栈底(Bottom):固定的,不允许进行插入和删除的另一端。 空栈:不含任何元素的空表。 栈...
  • 数据结构之线性表栈队列

    千次阅读 2020-02-20 18:24:06
    数据结构之线性表栈队列、实现方式和顺序表示、栈和队列的共同点和不同点
  • * 第3章 栈和队列 教学内容 3.1 栈的表示和操作的实现 3.2 栈的应用举例 3.3 队列的的表示和操作的实现 3.3.1 队列的定义和特点 a1...逻辑结构 只能在表的一端队尾进行插入另一端队头进行删除运算的线性表 先进先出FI
  • 与日常生活的排队相类似,队列是一种遵循先进先出原则的数据结构。本文主要介绍了队列的定义、利用数组实现队列、利用链表实现队列等内容。
  • 数据结构课件 队列是只允许一端删除另一端插入的线性表。
  • 实际使用,还可以有输出受限的双向队列(即一个端点允许插入和删除,另一个端点只允许插入的双向队列)和输入受限的双向队列(即一个端点允许插入和删除,另一个端点只允许删除的双向队列)。而如果限定双向队列...
  • 数据结构复习(栈和队列

    千次阅读 2021-06-01 22:36:55
    数据结构复习题(3)栈和队列选择题填空题判断题 栈和队列 选择题 1、一个栈的输入序列为:a,b,c,d,e,则栈的不可能输出的序列是( )。 A. a,b,c,d,e B. d,e,c,b,a C. d,c,e,a,b D. e,d,c,b,a 2、判断一个...
  • 数据结构第三章栈与队列

    千次阅读 2021-01-26 16:57:20
    对不带头结点的链队列作出队操作时,不会改变头指针的值。F 1-4 不论是入队列操作还是入栈操作,顺序存储结构上都需要考虑"溢出"情况。T 1-5 队列和栈都是运算受限的线性表,只允许表的两端进行运算。F 1-6 栈...
  • 队列是嵌入式软件常用的一种数据结构。什么是队列呢?今天我们就来聊一聊队列的使用及主要运算。队列只能在一端(队尾)进入数据加入,另一端(队首)进行删除数据结构。
  • 本文所有设计的代码均通过测试,并且功能性方面均实现应有的功能。 设计的代码并非全部公开,部分无关紧要代码并没有贴出来。 如果你也对此感兴趣、也想测试源码的话,可以私聊我,非常欢迎一起探讨学习。 由于...
  • 数据结构 第3章堆栈和队列 引 堆栈和队列也是最常见的数据结构, 算法设计经常使用 堆栈和队列逻辑上同线性表一样 都是线性结构,差别在于:线性表可以 表的任意位置插入和删除元素,而堆栈和 队列只能在表的...
  • 向量栈和队列都是 线性 结构可以向量的 任何 位置插入和删除元素对于栈只能 栈顶 插入和删除元素对于队列只能在 队尾 插入和 队首 删除元素 2. 栈是一种特殊的线性表允许插入和删除运算的一端称为 栈顶 不允许...
  • 第三章 堆栈和队列3.1 堆栈Stack 基本概念抽象数据类型顺序表示和实现链式表示和实现 3.2 堆栈应用 括号匹配问题 3.3... 定义限定只能在表的一端进行插入和删除操作的线性表2. 特点后进先出与线性表相同仍为一对一( 1:
  • 栈和队列的插入、删除等基本操作

    千次阅读 2019-08-22 23:40:54
    栈:是一种特殊的线性表,其只允许其固定的一段进行插入或者删除元素等操作;进行插入或者删除的一段称为栈顶,另一端称为栈顶; 栈的特性: 先进先出 后进后出 栈的构造(C语言实现) 1. 静态栈的构造(栈...
  • 队列是一种只允许一端进行插入操作,而另一端进行删除操作的线性表,简称:FIFO 符合生活习惯:排第一个的优先出列,最后来的排队伍后面     2.循环队列------队列的顺序存储结构 所谓的入队操作,...
  • 数据结构之队列

    千次阅读 多人点赞 2021-08-24 21:22:38
    什么是队列 二.项目创建 三.队列代码实现 1.队列结构体的创建 2.初始化头尾指针 3.队尾入数据 4.队头出数据 5.求队列长度 6.返回队头数据 7.返回队尾数据 8.判断队列是否为空 9.队列销毁 四.总结 五....

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 199,002
精华内容 79,600
关键字:

在队列中只能删除数据

友情链接: LaTeX操作手册.zip