-
2018-06-04 23:29:23
栈和队列是两种重要的线性结构
栈(stack)
是限定仅在表尾进行插入或删除操作的线性表.表的尾端有特殊含义,成为栈顶,相应的头端成为栈底.栈又被称为后进先出
抽象数据类型队列
和栈是相反的,队列(queue)是先进先出的线性表,它只允许在表的一端进行插入,而在另一端删除元素.这和我们日常中的排队是一致的,最早进入队列的最早离开.在队列中,允许插入的一端叫做队尾,允许删除的一端叫做对头
更多相关内容 -
数据结构复习(栈和队列)
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、判断一个...栈和队列
选择题
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,a2、判断一个循环队列Q(最多n个元素)为满的条件是( )。
A.Q->rear==Q->front
B.Q->rear==Q->front+1
C.Q->front==(Q->rear+1)%n
D.Q->front==(Q->rear-1)%n
设数组Data[n]作为循环队列Q的存储空间,front为队头指针,rear为队尾指针,则执行入队操作的语句为( )。
AQ->rear=(Q->rear+1)%(n+1)
BQ->front=(Q->front+1)%n
CQ->rear=(Q->rear+1)%n
DQ->front=(Q->front+1)%(n+1)
3、设计一个判别表达式中括号是否配对的算法,采用( )数据结构最佳。
A. 顺序表
B. 链表
C. 队列
D. 栈4、带头结点的单链表head为空的判定条件是( )。
A.head==NULL
B.head->next==NULL
C.head->next!=NULL
D.head!=NULL
5、一个栈的输入序列为:1,2,3,4,则栈的不可能输出的序列是( )。
A. 1243
B. 2134
C. 1432
D. 4312
E. 32146、若用一个大小为6的数组来实现循环队列,且当rear和front的值分别为0,3。当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。
A. 1和5
B. 2和4
C. 4和2
D. 5和17、队列的插入操作是在( )。
A. 队尾
B. 队头
C. 队列任意位置
D. 队头元素后8、循环队列的队头和队尾指针分别为front和rear,则判断循环队列为空的条件是( )。
A.front==rear
B.front==0
C.rear==0
D.front=rear+1
9、一个顺序栈S,其栈顶指针为top,则将元素e入栈的操作是( )。
A.*S->top=e;S->top++;
B.S->top++;*S->top=e;
C.*S->top=e
D. S->top=e;
10、表达式a*(b+c)-d的后缀表达式是( )。
A. abcd±
B. abc+d-
C. abc+d-
D. -+*abcd11、将递归算法转换成对应的非递归算法时,通常需要使用( )来保存中间结果。
A. 队列
B. 栈
C. 链表
D. 树12、栈的插入和删除操作在( )。
A. 栈底
B. 栈顶
C. 任意位置
D. 指定位置13、五节车厢以编号1,2,3,4,5顺序进入铁路调度站(栈),可以得到( )的编组。
A. 3,4,5,1,2
B. 2,4,1,3,5
C. 3,5,4,2,1
D. 1,3,5,2,414、判定一个顺序栈S(栈空间大小为n)为空的条件是( )。
A.S->top==0
B.S->top!=0
C.S->top==n
D.S->top!=n
15、在一个链队列中,front和rear分别为头指针和尾指针,则插入一个结点s的操作为( )。
A.front=front->next
B.s->next=rear;rear=s
C.rear->next=s;rear=s;
D.s->next=front;front=s;
16、一个队列的入队序列是1,2,3,4,则队列的出队序列是( )。
A. 1,2,3,4
B. 4,3,2,1
C. 1,4,3,2
D. 3,4,1,217、依次在初始为空的队列中插入元素a,b,c,d以后,紧接着做了两次删除操作,此时的队头元素是( )。
A. a
B. b
C. c
D. d18、正常情况下,删除非空的顺序存储结构的堆栈的栈顶元素,栈顶指针top的变化是( )。
A. top不变
B. top=0
C. top=top+1
D. top=top-119、判断一个循环队列Q(空间大小为M)为空的条件是( )。
A.Q->front==Q->rear
B.Q->rear-Q->front-1==M
C.Q->front+1=Q->rear
D.Q->rear+1=Q->front
20、设计一个判别表达式中左右括号是否配对出现的算法,采用( )数据结构最佳。
A. 线性表的顺序存储结构
B. 队列
C. 栈
D. 线性表的链式存储结构21、当用大小为N的数组存储顺序循环队列时,该队列的最大长度为( )。
A. N
B. N+1
C. N-1
D. N-222、队列的删除操作是在( )。
A. 队首
B. 队尾
C. 队前
D. 队后23、若让元素1,2,3依次进栈,则出栈次序不可能是( )。
A. 3,2,1
B. 2,1,3
C. 3,1,2
D. 1,3,224、循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列中的元素个数是( )。
A. (rear-front+m)%m
B. rear-front+1
C. rear-front-1
D. rear-front循环队列是空队列的条件是( )。
A Q->rear= =Q->front
B (Q->rear+1)%maxsize= =Q->front
C Q->rear= =0
D Q->front= =025、在解决计算机主机和打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个( )结构。
A. 堆栈
B. 队列
C. 数组
D. 线性表26、栈和队列都是( )。
A. 链式存储的线性结构
B. 链式存储的非线性结构
C. 限制存取点的线性结构
D. 限制存取点的非线性结构27、在一个链队列中,假定front和rear分别为队头指针和队尾指针,删除一个结点的操作是( )。
A. front=front->next
B. rear= rear->next
C. rear->next=front
D. front->next=rear28、队和栈的主要区别是( )。
A. 逻辑结构不同
B. 存储结构不同
C. 所包含的运算个数不同
D. 限定插入和删除的位置不同在作退栈运算时应先判别栈是否( )。
A 空
B 满
C 上溢
D 下溢在作进栈运算时,应先判别栈是否( )。
A 空
B 满
C 上溢
D 下溢若栈采用顺序存储方式存储,现两栈共享空间V[1…m],top[1]、top[2]分别代表第1和第2个栈的栈顶,栈1的底在V[1],栈2的底在V[m],则栈满的条件是( )。
A |top[2]-top[1]|=0
B top[1]+1=top[2]
C top[1]+top[2]=m
D top[1]=top[2]一个队列的入列序列是1234,则队列的输出序列是( )。
A 4321
B 1234
C.1432
D 3241以数组Q[0,…,m-1]存放循环队列中的元素,变量rear和qulen分别指示循环队列中队尾的实际位置和当前队列中元素的个数,队列第一个元素的实际位置是( )。
A rear-qulen
B rear-qulen+m
C m-qulen
D 1+(rear+m-qulen)%m已知队列(4,41,5,7,18,26,15),第一个进入队列的元素是4,则第5个出队列的元素是( )。
A 5
B 41
C 18
D 7栈结构通常采用的两种存储结构是( )
A 顺序存储结构和链式存储结构
B 散列方式和索引方式
C 链表存储结构和数组
D 线性存储结构和非线性存储结构设长度为n的链队列单循环链表表示,若只设头指针,则入队操作的时间复杂度为( )
A O(1)
B O(log2n)
C O(n)
D O(n2)在栈中,存取数据的原则是( )
A 先进先出
B 先进后出
C 后进后出
D 随意进出在栈中,出栈操作的时间复杂度是( )
A O(1)
B O(log2n)
C O(n)
D O(n2)在顺序栈中删除一个元素,至少要移动( )元素。
A 0
B 1
C n/2
D n插入和删除只能在一端进行的线性表,称为( )
A 队列
B 循环队列
C 栈
D 循环栈表示一个栈ST(最多元素为m0)为栈空的条件是( )。
AST->top!=0
BST->top==0
C
ST->top!=m0
DST->top==m0
最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是( )
A(rear+1)%n==front
Brear==front
Crear+1==front
D(rear-l)%n==front
链栈与顺序栈相比,比较明显的优点是( )。
A 插入操作更加方便
B 删除操作更加方便
C 不会出现下溢的情况
D 不会出现上溢的情况在作退栈运算时应先判别栈是否( )。
A 空
B 满
C 上溢
D 下溢若栈顶指针指向栈顶元素,当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )
A n-1
B n
C n+1
D n/2以下( )不是队列的基本运算
A 从队尾插入一个新元素
B 从队列中删除第i个元素
C 判断一个队列是否为空
D 读取队头元素的值填空题
向量、栈和队列都是 线性 结构,可以在向量的 ==任何 == 位置插入和删除元素;对于栈只能在 栈顶 == 插入和删除元素;对于队列只能在 == 队尾 == 插入和 == 队首 删除元素。
一个顺序栈一旦被声明,其占用空间的大小( )。
答案:已固定链栈和顺序栈相比,有一个比较明显的缺点,即( )。
答案:通常不会出现栈满的情况用单链表表示的链式队列的队头在链表的( )位置。
答案:链头在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区,主机将要输出的数据依次写入缓冲区中,而打印机则从缓冲区中取出数据打印,该缓冲区应该是
一个( )结构。
答案:队列循环队列 A[m] 存放其元素,用 front 和 rear 分别表示队头及队尾,则循环队列满的条件是( )。
答案:(rear+1)%m=front
在一个栈顶指针为 top 的链栈中,将一个 p 指针所指的结点入栈,应执行( )。
答案:p->next=top; top=p;
在一个栈顶指针为 top 的链栈中删除一个结点时,用 x 保存被删结点的值,则执行( )。
答案:x=top->data; top=top->next;
在一个链队中,设 front 和 rear 分别为队首和队尾指针,则插入 p 所指结点时,应执行( )。
答案:rear->next=p;rear=p;
在链队列中,f 和 r 分别为队头和队尾指针,要把 s 所指结点入队,应执行( )。
答案:r->next=s;r=s;设 top 是一个链栈的栈顶指针,栈中每个结点由一个数据域 data 和指针域 next 组成,设用 x 接收栈顶元素,则取栈顶元素的操作为( )。
答案:x=top->data;一个队列的入队序列是 2,4,6,8,则队列的输出序列是( )。
答案:2,4,6,8一个栈的进栈序列是 5,6,7,8,则栈的不可能的出栈序列是( )。(进出栈操作可以交替进行)
5,8,6,7
栈的插入删除操作在( )进行。
答案:栈顶栈和队列的相同点是( )。
逻辑结构与线性表相同,都是操作规则受到限制的线性表
以下说法正确的是( )。
栈的特点是先进后出,队列的特点是先进先出
设有一个带头结点的链队列,队列中每个结点由一个数据域 data 和指针域 next 组成,front 和 rear 分别为链队列的头指针和尾指针。设 p 指向要入队的新结点(该结点已被赋值),则入队操作为( )。
答案:rear->next=p;rear=p;
设有一个带头结点的链队列,队列中每个结点由一个数据域 data 和指针域 next 组成,front 和 rear 分别为链队列的头指针和尾指针,要执行出队操作,用 x 保存出队元素的值,p 为指向结点类型的指针,可执行如下操作:p=front->next;x=p->data;然后指行( )。
答案:front->next=p->next;
以下说法不正确的是( )。
顺序队列中,当尾指针已经超越队列存储空间的上界,则一定是队列已满
一个递归算法必须包括( )。
终止条件和递归部分
假定一个链式队列的队头和队尾指针分别为 front 和 rear,则判断队空的条件为( )。
front=rear
向顺序栈中压入新元素时,应当( )。
应当先移动栈顶指针,再存入元素
判断一个循环队列 Q(最多元素为 m)为满的条件是( )。
答案:Q->front==(Q->rear+1)%m
判断栈满(元素个数最多 n 个)的条件是( )。
答案:top=-1
队列的删除操作是在( )。
答案:队前
一个队列的入队序列是 a,b,c,d,按该队列的可能输出序列使各元素依次入栈,该栈的可能输
出序列是 ( )。(进栈出栈可以交替进行)。答案:d,c,b,a
带表头结点的空循环双向链表的长度等于 0
判断题
队列是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。( )
正确的答案是“错”两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片空间的两端。( )
正确的答案是==“对”==。没有元素的堆栈称为空栈,空栈用不着栈顶指针。( )
正确
对采用链式存储结构的堆栈进行操作不必判断溢出。( )
正确
采用循环链表作为存储结构的队列称为循环队列。( )
错误
链接队列不存在溢出问题。( )
错误
栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。( )
正确
没有元素的堆栈称为空栈,空栈用不着栈顶指针。( )
错误
线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。
错,线性表是逻辑结构概念,可以顺序存储或链式存储,与元素数据类型无关。
在表结构中最常用的是线性表,栈和队列不太常用。
错,不一定吧?调用子程序或函数常用,CPU中也用队列。
栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。
对
对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。
正确,都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。
栈和链表是两种不同的数据结构。
错,栈是逻辑结构的概念,是特殊殊线性表,而链表是存储结构概念,二者不是同类项
栈和队列是一种非线性数据结构。
错,他们都是线性逻辑结构,栈和队列其实是特殊的线性表,对运算的定义略有不同而已。
两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。
答:对
简答题
说明线性表、栈与队的异同点。
答:相同点:都是线性结构,都是逻辑结构的概念。都可以用顺序存储或链表存储;栈和队列是两种特殊的线性表,即受限的线性表,只是对插入、删除运算加以限制。
不同点:①运算规则不同,线性表为随机存取,而栈是只允许在一端进行插入、删除运算,因而是后进先出表LIFO;队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO。
② 用途不同,堆栈用于子程调用和保护现场,队列用于多道作业处理、指令寄存及其他运算等等。设有编号为1,2,3,4的四辆列车,顺序进入一个栈式结构的车站,具体写出这四辆列车开出车站的所有可能的顺序。
答:至少有14种。
① 全进之后再出情况,只有1种:4,3,2,1 ② 进3个之后再出的情况,有3种,3,4,2,1 3,2,4,1
3,2,1,4 ③ 进2个之后再出的情况,有5种,2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3
2,1,3,4 ④ 进1个之后再出的情况,有5种,1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,3顺序队的“假溢出”是怎样产生的?如何知道循环队列是空还是满?
答:一般的一维数组队列的尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫“假溢出”。
采用循环队列是解决假溢出的途径。 另外,解决队满队空的办法有三: ① 设置一个布尔变量以区别队满还是队空;
② 浪费一个元素的空间,用于区别队满还是队空。 ③ 使用一个计数器记录队列中元素个数(即队列长度)。
我们常采用法②,即队头指针、队尾指针中有一个指向实元素,而另一个指向空闲元素。
判断循环队列队空标志是: f=rear
队满标志是:f=(r+1)%N设循环队列的容量为40(序号从0到39),现经过一系列的入队和出队运算后,有
① front=11,rear=19; ② front=19,rear=11;问在这两种情况下,循环队列中各有元素多少个?答:用队列长度计算公式: (N+r-f)% N
① L=(40+19-11)% 40=8
② L=(40+11-19)% 40=32写出下列程序段的输出结果(队列中的元素类型QElem Type为char)。
void main( ){ Queue Q; Init Queue (Q); Char x=’e’; y=’c’; EnQueue (Q,’h’); EnQueue (Q,’r’); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,’a’); while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; Printf(x); }
答:输出为“char”。
-
数据结构--栈和队列基础知识
2020-09-01 14:05:52数据从表的一端进,从另一端出,且遵循 "先进先出" 原则的线性存储结构就是队列。3.2 队列的实现 3.3 队列的应用 一 概述 栈和队列,严格意义上来说,也属于线性表,因为它们也都用于存储逻辑关系为 "一对一" 的...目录
栈和队列不要混淆,栈结构是一端封口,特点是"先进后出";而队列的两端全是开口,特点是"先进先出"。数据从表的一端进,从另一端出,且遵循 "先进先出" 原则的线性存储结构就是队列。3.2 队列的实现
一 概述
栈和队列,严格意义上来说,也属于线性表,因为它们也都用于存储逻辑关系为 "一对一" 的数据,但由于它们比较特殊,因此将其单独作为一篇文章,做重点讲解。既然栈和队列都属于线性表,根据线性表分为顺序表和链表的特点,栈也可分为顺序栈和链表,队列也分为顺序队列和链队列,这些内容都会在本章做详细讲解。
使用栈结构存储数据,讲究“先进后出”,即最先进栈的数据,最后出栈;使用队列存储数据,讲究 "先进先出",即最先进队列的数据,也最先出队列。
二 栈
2.1 栈的基本概念
同顺序表和链表一样,栈也是用来存储逻辑关系为 "一对一" 数据的线性存储结构,如下图所示。
从上图我们看到,栈存储结构与之前所了解的线性存储结构有所差异,这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求:- 栈只能从表的一端存取数据,另一端是封闭的;
- 在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。拿图 1 的栈来说,从图中数据的存储状态可判断出,元素 1 是最先进的栈。因此,当需要从栈中取出元素 1 时,根据"先进后出"的原则,需提前将元素 3 和元素 2 从栈中取出,然后才能成功取出元素 1。
因此,我们可以给栈下一个定义,即栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构。通常,栈的开口端被称为栈顶;相应地,封口端被称为栈底。因此,栈顶元素指的就是距离栈顶最近的元素,拿下图中的栈顶元素为元素 4;同理,栈底元素指的是位于栈最底部的元素,下 中的栈底元素为元素 1。
2.2 进栈和出栈
基于栈结构的特点,在实际应用中,通常只会对栈执行以下两种操作:
- 向栈中添加元素,此过程被称为"进栈"(入栈或压栈);
- 从栈中提取出指定元素,此过程被称为"出栈"(或弹栈);
2.3 栈的具体实现
栈是一种 "特殊" 的线性存储结构,因此栈的具体实现有以下两种方式:
- 顺序栈:采用顺序存储结构可以模拟栈存储数据的特点,从而实现栈存储结构。使用顺序表模拟栈存储结构常用的实现思路,即在顺序表中设定一个实时指向栈顶元素的变量(一般命名为 top),top 初始值为 -1,表示栈中没有存储任何数据元素,及栈是"空栈"。一旦有数据元素进栈,则 top 就做 +1 操作;反之,如果数据元素出栈,top 就做 -1 操作。
- 链栈:采用链式存储结构实现栈结构。通常我们将链表的头部作为栈顶,尾部作为栈底,如下图所示。将链表头部作为栈顶的一端,可以避免在实现数据 "入栈" 和 "出栈" 操作时做大量遍历链表的耗时操作。因此,链栈实际上就是一个只能采用头插法插入或删除数据的链表。
两种实现方式的区别,仅限于数据元素在实际物理空间上存放的相对位置,顺序栈底层采用的是数组,链栈底层采用的是链表。有关顺序栈和链栈的具体实现会在后续章节中作详细讲解。
2.4 栈的应用
基于栈结构对数据存取采用 "先进后出" 原则的特点,它可以用于实现很多功能。
例如,我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A,然后关闭了页面 A 跳转到页面 B,随后又关闭页面 B 跳转到了页面 C。而此时,我们如果想重新回到页面 A,有两个选择:- 重新搜索找到页面 A;
- 使用浏览器的"回退"功能。浏览器会先回退到页面 B,而后再回退到页面 A。
浏览器 "回退" 功能的实现,底层使用的就是栈存储结构。当你关闭页面 A 时,浏览器会将页面 A 入栈;同样,当你关闭页面 B 时,浏览器也会将 B入栈。因此,当你执行回退操作时,才会首先看到的是页面 B,然后是页面 A,这是栈中数据依次出栈的效果。
不仅如此,栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号(小括号、中括号和大括号),括号的错误使用(通常是丢右括号)会导致程序编译错误,而很多开发工具中都有检测代码是否有编辑错误的功能,其中就包含检测代码中的括号匹配问题,此功能的底层实现使用的就是栈结构。
同时,栈结构还可以实现数值的进制转换功能。例如,编写程序实现从十进制数自动转换成二进制数,就可以使用栈存储结构来实现。
以上也仅是栈应用领域的冰山一角,这里不再过多举例。在后续的学习中,我们会大量使用到栈结构。
3 队列
3.1 队列的基本概念
队列,和栈一样,也是一种对数据的"存"和"取"有严格要求的线性存储结构。与栈结构不同的是,队列的两端都"开口",要求数据只能从一端进,从另一端出,如下图所示:
通常,称进数据的一端为 "队尾",出数据的一端为 "队头",数据元素进队列的过程称为 "入队",出队列的过程称为 "出队"。
不仅如此,队列中数据的进出要遵循 "先进先出" 的原则,即最先进队列的数据元素,同样要最先出队列。拿图 1 中的队列来说,从数据在队列中的存储状态可以分析出,元素 1 最先进队,其次是元素 2,最后是元素 3。此时如果将元素 3 出队,根据队列 "先进先出" 的特点,元素 1 要先出队列,元素 2 再出队列,最后才轮到元素 3 出队列。
栈和队列不要混淆,栈结构是一端封口,特点是"先进后出";而队列的两端全是开口,特点是"先进先出"。数据从表的一端进,从另一端出,且遵循 "先进先出" 原则的线性存储结构就是队列。
3.2 队列的实现队列存储结构的实现有以下两种方式:
- 顺序队列:在顺序表的基础上实现的队列结构。由于顺序队列的底层使用的是数组,因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外,为了满足顺序队列中数据从队尾进,队头出且先进先出的要求,我们还需要定义两个指针(top 和 rear)分别用于指向顺序队列中的队头元素和队尾元素,如下图所示:
由于顺序队列初始状态没有存储任何元素,因此 top 指针和 rear 指针重合,且由于顺序队列底层实现靠的是数组,因此 top 和 rear 实际上是两个变量,它的值分别是队头元素和队尾元素所在数组位置的下标。当有数据元素进队列时,对应的实现操作是将其存储在指针 rear 指向的数组位置,然后 rear+1;当需要队头元素出队时,仅需做 top+1 操作。 - 链队列:在链表的基础上实现的队列结构。链式队列的实现思想同顺序队列类似,只需创建两个指针(命名为 top 和 rear)分别指向链表中队列的队头元素和队尾元素,如下图所示。
两者的区别仅是顺序表和链表的区别,即在实际的物理空间中,数据集中存储的队列是顺序队列,分散存储的队列是链队列。
3.3 队列的应用
实际生活中,队列的应用随处可见,比如排队买 XXX、医院的挂号系统等,采用的都是队列的结构。
拿排队买票来说,所有的人排成一队,先到者排的就靠前,后到者只能从队尾排队等待,队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后,才轮到自己买票。这就不是典型的队列结构吗?
-
数据结构之 栈和队列
2020-05-27 13:20:371,栈只能从表的一端存取数据,另一端是封闭的 2,在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。 栈的使用案例1: 浏览器 “回退” 功能的实现,底层使用的就是栈存储...一、栈
1、描叙
栈和队列是计算机中基本的两个数据结构,栈可以达到后进先出,队列可以先进先出。在实际应用上,我们可以使用栈进行逆序遍历链表,非递归中序遍历二叉树,括号匹配,函数调用等等;可以使用队列对二叉树进行层次遍历,打印机的打印服务,通信中的消息队列等等。
栈的储存规则:
1,栈只能从表的一端存取数据,另一端是封闭的
2,在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。栈的使用案例1:
浏览器 “回退” 功能的实现,底层使用的就是栈存储结构。
当你关闭页面 A 时,浏览器会将页面 A 入栈;同样,当你关闭页面 B 时,浏览器也会将 B入栈。因此,当你执行回退操作时,才会首先看到的是页面 B,然后是页面 A,这是栈中数据依次出栈的效果。栈的使用案例2:
栈存储结构还可以帮我们检测代码中的括号匹配问题。
多数编程语言都会用到括号(小括号、中括号和大括号),括号的错误使用(通常是丢右括号)会导致程序编译错误,而很多开发工具中都有检测代码是否有编辑错误的功能,其中就包含检测代码中的括号匹配问题,此功能的底层实现使用的就是栈结构。2、图文示例
先进后出
3、代码示例
package stackAndQueue; /** * TODO 栈,先进后出 */ public class Stack { // 底层基于数组 private int[] arr; // 数据长度, 最后一个数据的索引=数据长度-1 private int size; // 容量设置 public Stack() { arr = new int[16]; } public Stack(int length) { arr = new int[length]; } /** * 添加 */ public void plus(int val) { arr[size++] = val; } /** * 获取并弹出元素, 最后一个数据的索引=size-1 */ public int pop() { return arr[--size]; } /** * 判断是否为空 */ public boolean isEmpty() { return size == 0; } /** * 容量是否满了,添加可先判断容量,进行扩容操作 */ public boolean isFull() { return size == arr.length; } }
测试代码
// 测试 class Test { public static void main(String[] args) { Stack stack = new Stack(5); stack.plus(1); stack.plus(2); stack.plus(3); stack.plus(4); stack.plus(5); System.out.println("容量是否满了-->" + stack.isFull()); while (!stack.isEmpty()) { System.out.println(stack.pop()); } } } // 输出 容量是否满了-->true 5 4 3 2 1
二、队列
1、描叙
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队。因为队列只允许在一端插入,在另一端删除,所以只有最早进入队列的元素才能最先从队列中删除,故队列又称为先进先出(FIFO—first in first out)线性表。 [1]队列的实现
队列存储结构的实现有以下两种方式:
顺序队列:在顺序表的基础上实现的队列结构;
链队列:在链表的基础上实现的队列结构;两者的区别仅是顺序表和链表的区别,即在实际的物理空间中,数据集中存储的队列是顺序队列,分散存储的队列是链队列。
队列的实际应用
实际生活中,队列的应用随处可见,比如排队买 XXX、医院的挂号系统等,采用的都是队列的结构。拿排队买票来说,所有的人排成一队,先到者排的就靠前,后到者只能从队尾排队等待,队中的每个人都必须等到自己前面的所有人全部买票成功并从队头出队后,才轮到自己买票。这就不是典型的队列结构吗?
2、图文示例
普通队列
先进先出
循环队列先进先出
3、代码示例
package stackAndQueue; /** * TODO 队列,先进先出 */ public class Queue { // 底层基于数组 private int[] arr; // 数据长度 private int size; // 开头元素索引 (每获取一次数据 front+1) private int front; // 结尾元素索引(每添加一次数据rear+1,每获取一次数据rear-1 )--> 数据长度=rear+1 private int rear; // 容量设置 public Queue() { arr = new int[16]; front = -1; rear = -1; } public Queue(int length) { arr = new int[length]; front = -1; rear = -1; } /** * 获取当前数据长度 */ public int size() { return this.size; } /** * 插入元素 */ public void plus(int val) { // 判断数组是否满了 if (isFull()) { System.out.println("插入["+val+"]失败,数组容量已满"); } else { // 循环插入,--元素尾添加 if (rear == arr.length - 1) { rear = -1; } size++; arr[++rear] = val; } } /** * 获取并弹出元素 */ public int pop() { // 循环读取--元素头开始读取 if (front == arr.length - 1) { front = -1; } size--; return arr[++front]; } /** * 判断元素是否为空 */ public boolean isEmpty() { return size == 0; } /** * 容量是否满了,添加可先判断容量,进行扩容操作 */ public boolean isFull() { return size == arr.length; } }
测试代码
// 测试 class Test1 { public static void main(String[] args) { Queue queue = new Queue(5); queue.plus(1); queue.plus(2); queue.plus(3); queue.plus(4); queue.plus(5); System.out.println("容量是否满了-->" + queue.isFull() + " 当前数据长度:" + queue.size()); //消费--> size=0 while (!queue.isEmpty()) { System.out.println(queue.pop()); } // 添加数据,size=0 queue.plus(6); queue.plus(7); queue.plus(8); queue.plus(9); queue.plus(10); System.out.println("弹出--> " + queue.pop()); queue.plus(11); // queue.plus(12); queue.plus(13); queue.plus(14); while (!queue.isEmpty()) { System.out.println(queue.pop()); } } } // 打印 容量是否满了-->true 当前数据长度:5 1 2 3 4 5 弹出--> 6 插入[12]失败,数组容量已满 插入[13]失败,数组容量已满 插入[14]失败,数组容量已满 7 8 9 10 11
本文到此结束,如果觉得有用,劳烦各位点赞关注一下呗,将不定时持续更新更多的内容…,感谢大家的观看!
-
下面关于栈和队列的叙述中,错误的是()。
2021-03-14 20:23:09下面关于栈和队列的叙述中,错误的是()。A.栈和队列都是操作受限的线性表B.队列采用单循环链表存储时,只需设置队尾指针就可使入队和出队操作的时间复杂度都为O(1)C.若队列的数据规模n可以确定,则采用顺序存储... -
数据结构:栈与队列的知识点by解学武
2021-02-25 15:05:43文章来自解学武学习网站的免费章节 目录什么是栈进栈和出栈栈的应用什么是队列队列的出队和...在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。拿图 1 的栈来说,从图中数据的 -
_数据结构_在计算机专业中的地位.pdf
2021-06-24 04:42:18_数据结构_在计算机专业中的地位,计算机数据结构,计算机考研数据结构,计算机数据结构考纲,数据结构与计算机网络,计算机中的高位与地位,数据结构中的堆,数据结构中的树,java中的数据结构,数据结构中的图【观察与思考... -
【数据结构】队列(顺序队列、链队列)的JAVA代码实现
2018-03-28 20:35:19队列中没有数据元素时称为空队列。 队列的操作是按照先进先出(first in first out)或后进后出(last in last out)的原则进行的。因此,队列又被称为FIFO表。它的实现方式主要有顺序队列、链队列两种。 队列... -
数据结构之——堆、栈、队列
2020-08-31 18:17:08堆栈、队列是计算机中定义最早的数据结构。堆栈是后进先出(左端固定固定右端浮动,堆栈是右进右出),队列是先进先出的数据组织和存储形式。 栈 栈是一种运算受限的线性表,其限制是指只仅允许在表的一端进行插入和... -
Java中阻塞队列类型介绍
2021-03-31 17:57:23Java中的BlockingQueue接口是一个线程安全的存取队列,适用于生产者消费者的应用场景中,支持两个附加操作: 生产者线程会一直不断的往阻塞队列中放入数据,直到队列满了为止。队列满了后,生产者线程阻塞等待消费... -
队列(Queue)是一种以“先进先出”的方式存放数据的数据结构。设计一个名为Queue的类用于存储整数
2021-10-24 21:05:01一个名为elements的int[ ]类型的数据域,保存队列的int值 一个名为size的数据域,保存队列的元素个数 一个构造方法,使用默认的容量8创建一个Queue对象 方法enqueue(int value),用于将value加入到队列中 方法... -
数据结构 第三章栈和队列 求指点,答案
2020-11-20 10:39:55对于栈操作数据的原则是( )。A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序2. 有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?( )A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1... -
【数据结构】判断队列是否队满的C++练习与实现
2021-07-05 20:37:10(四)假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试设计与此结构相应的插入和删除算法,编写... -
数据结构之栈与队列浅谈
2020-12-14 10:43:20栈只能从表的一端存取数据,另一端是封闭的。 在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。从图中可看出数据的存储状态,元素 1 是最先进的栈。因此, -
【数据结构初阶】第五篇——栈和队列(实现+图解)
2021-11-02 16:00:41本篇博客我要来和大家一起聊一聊数据结构中的栈和队列相关知识,一种是先进后出的结构,另一种是先进先出的结构。 博客代码已上传至:https://gitee.com/byte-binxin/data-structure/tree/master/stack_queue 目录... -
数据结构14:队列(Queue),“先进先出”的数据结构
2018-05-13 11:05:00队列是线性表的一种,在操作数据元素时,和栈一样,有自己的规则:使用队列存取数据元素时,数据元素只能从表的一端进入队列,另一端出队列,如图1。 图1 队列示意图 称进入队列的一端为“队尾”;出队列的... -
数据结构(一)线性链表、非线性链表、稀疏数组与队列、单向链表
2020-08-07 19:09:53➢要学习好数据结构就要多多考虑如何将生活中遇到的问题,用程序去实现解决. ➢程序=数据结构+算法 ➢数据结构是算法的基础,换言之,想要学好算法,需要把数据结构学到位。 线性链表和非线性链表 数据结构包括:线性... -
【C语言】数据结构:数组,链表,栈,队列,树
2021-12-19 17:22:52存取速度快 缺点: 事先必须知道数组的长度 插入删除元素很慢 空间通常是有限制的 需要大块连续的内存块 插入删除元素的效率很低 定义一个数组至少需要3个参数:首地址,长度,有效个数。 用指针自己... -
一本正经的聊数据结构(3):栈和队列
2020-04-27 09:47:23前文传送门: 「一本正经的聊数据结构(1):时间复杂度」 ...常用的线性结构有:线性表,栈,队列,双队列,数组,串。 线性结构是最常用的数据结构,它最大的特点是数据元素之间存在一对一的线性关... -
算法与数据结构(Java版)01-稀疏数组和队列详解及代码实现
2022-04-14 16:57:49稀疏数组和队列-JAVA篇1 稀疏数组1.1 稀疏数组的应用场景1.2 稀疏数组的基本介绍1.3 稀疏数组的应用1.4 稀疏数组代码实现1.4.1 创建二维数组并赋予初始值1.4.2 将原有的二维数组转化为稀疏数组1.4.3 将稀疏数组转化... -
栈和队列简介
2020-02-26 00:09:24栈和队列简介 栈 栈(stack),有些地方称为堆栈,是一种容器,可存入数据元素、访问元素、删除元素,它的特点在于只能允许在容器的一端(称为栈顶端指标,英语:top)进行加入数据(英语:push)和输出数据... -
超硬核!数据结构学霸笔记,考试面试吹牛就靠它
2021-03-26 11:11:21上次发操作系统笔记,很快浏览上万,这次数据结构比上次硬核的多哦,同样的会发超硬核代码,关注吧。 -
FreeRTOS 消息队列
2020-07-27 06:48:10本章节为大家讲解 FreeRTOS 的一个重要的通信机制----消息队列,初学者要熟练掌握,因为消息队列在实际项目中应用较多。 消息队列的概念及其作用消息队列就是通过 RTOS 内核提供的服务,任务或中断服务子程序可以将... -
21 利用分布式消息队列降低系统耦合性
2021-05-17 13:55:552.2 分布式消息队列 队列是一种先进先出的数据结构,分布式消息队列可以看作将这种数据结构部署到 独立的服务器上,应用程序可以通过远程访问接口使用分布式消息队列,进行消息存取 操作,进而实现分布式的异步调用... -
第3章 栈与队列习题参考答案.pdf
2020-10-24 20:08:39在栈中存取数据的原则是 B A先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2 若将整数 12 34 依次进栈则不可能得到的出栈序列是 D A1234 B. 1324 C. 4321 D. 1423 3 在链栈中进行出栈操作时 B A 需要判断栈是否满 ... -
超硬核十万字!全网最全 数据结构 代码,随便秒杀老师/面试官,我说的
2021-04-11 01:11:23本文代码实现基本按照《数据结构》课本目录顺序,外加大量的复杂算法实现,一篇文章足够。能换你一个收藏了吧? -
数据结构-队列-“先进先出”的数据结构
2018-12-04 18:15:241.队列是线性表的一种,在操作数据元素时,和栈一样,有自己的规则:使用队列存取数据元素时,数据元素只能从表的一端进入队列,另一端出队列 2.队列的顺序表示和实现 使用顺序存储结构表示队列时,首先申请足够大... -
最新第3章栈与队列习题参考答案.pdf
2020-09-27 05:17:07在栈中存取数据的原则是 B A 先进先出 B. 先进后出 C. 后进后出 D. 没有限制 2 若将整数 12 3 4 依次进栈则不可能得到的出栈序列是 D A 1234 B. 1324 C. 4321 D. 1423 3 在链栈中进行出栈操作时 B A 需要 判断栈... -
03-栈与队列
2019-05-12 19:04:13 3.1.1 抽象数据类型栈的定义 3.1.2 栈的表示和实现 3.2 栈的应用举例 3.3.1 数制转换 3.3.2 括号匹配的检验 3.3.4 行编辑程序 3.3.5 迷宫求解 3.3.5 表达式求值 3.4 队列 3.4.1 抽象数据... -
【TencentOS tiny学习】源码分析(3)——队列
2019-08-17 03:06:48队列是一种常用于任务间通信的数据结构,队列可以在任务与任务间、中断和任务间传递消息,实现了任务接收来自其他任务或中断的不固定长度的消息,任务能够从队列里面读取消息,当队列中的消息是空时,读取消息的任务...