700字范文 > 数据结构—栈与队列【顺序存储链式存储卡特兰数优先级队列】

数据结构—栈与队列【顺序存储链式存储卡特兰数优先级队列】

时间：2023-09-21 13:17:49

💂 个人网站:路遥叶子🤟 版权:本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦💅想寻找共同成长的小伙伴，请点击【Java全栈开发社区】

第三章：栈与队列

(一) 栈、队列和线性表有什么区别？

1. 栈和队列可被看成是两种操作受限制的特性线性表。

2. 其特色性体现在它们的插入和删除操作都是控制在线性表的一端或两端进行。

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

(二) 栈

一、什么是栈？栈又有什么特性？

1. 栈是特殊的线性表。栈中的数据元素及其元素之间的逻辑关系和线性表相同，逻辑结构和存储结构都相同。

2. 栈的插入和删除操作只允许在表的尾端进行。其允许进行插入和删除的一端称为栈顶，另一端为栈底。

3. 栈的插入操作称为入栈(push)，删除操作称为出栈(pop)。

4. 栈每次最先进去的元素总是最后一个出来。因此栈顶具有一种后进先出或先进后出的特性。

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

二、栈都有那些术语操作？

栈顶Top：允许进行插入和删除的一端。

栈底Bottom

入栈push：栈的插入操作。

出栈pop：栈的删除操作。

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

三、对于四个元素ABCD它们的出栈的序列有多少种呢？

—— 对于四个元素ABCD依次入栈，那么出栈的序列有多少种呢？（进出栈可以交替进行）

// in 代表进，out代表出。例：Ain Aout 表示A进 A出
Ain Aout Bin Bout Cin Cout Din Dout --> ABCD
Ain Aout Bin Bout Cin Din Dout Cout --> ABDC
Ain Aout Bin Cin Cout Din Dout Bout --> ACDB
Ain Aout Bin Cin Cout Bout Din Dout --> ACBD
Ain Aout Bin Cin Din Dout Cout Bout --> ADCB
Ain Bin Bout Aout Cin Cout Din Dout --> BACD
Ain Bin Bout Aout Cin Din Dout Cout --> BADC
Ain Bin Bout Cin Cout Aout Din Dout --> BCAD
Ain Bin Bout Cin Cout Din Dout Aout --> BCDA
Ain Bin Bout Cin Din Dout Cout Aout --> BDCA
Ain Bin Cin Cout Din Dout Bout Aout --> CDBA
Ain Bin Cin Cout Bout Din Dout Aout --> CBDA
Ain Bin Cin Cout Bout Aout Din Dout --> CBAD
Ain Bin Cin Din Dout Cout Bout Aout --> DCBA
—— 最终结果：14种出栈序列

四、卡特兰数

进出栈是最经典的卡特兰数

公式：

详情链接：

「算法入门笔记」卡特兰数 - 知乎/p/97619085 解析卡特兰数的计算

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

五、栈的抽象数据类型Java接口【 IStack】

package data.linear_table.stack_queue;//栈的抽象数据类型Java接口public interface IStack {public void clear() ; //置栈空public boolean isEmpty() ; //判断栈是否为空public int length() ; //栈中数据元素的个数public Object peek() ; //取栈顶元素public void push(Object x) throws Exception; //入栈public Object pop() ; //出栈}

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

(三) 顺序栈

一、什么是顺序栈？

使用数组来实现的栈。

入栈和出栈只能在栈顶进行。

假设数组名为：stackElem 。变量top表示栈顶元素。则top有两种情况：

一种是将top设置为指向栈顶元素的下一个元素的位置，则空栈时：top = 0

一种是将top设置为指向栈顶元素的位置，则空栈时，top = -1

二、那么顺序栈默认采用那种top情况呢？

约定：

空栈：top == 0

满栈：top == stackElem.length

长度：top

栈顶元素：stackElem[top - 1]

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

三、顺序栈类【SqStack】

—— 实现栈接口 IStack

package data.linear_table.stack_queue;//顺序栈类public class SqStack implements IStack {private Object[] stackElem ; //对象数组private int top ; //在非空栈中，top始终指向栈顶元素的下一个存储位置.栈为空，top = 0 ;//栈的构造函数，构造一个存储空间容量为maxSize个单元public SqStack (int maxSize) {top = 0 ; //初始化top = 0stackElem = new Object[maxSize] ;// 为栈分配maxSize个存储单元}@Overridepublic void clear() {top = 0 ;}//判断是否为空@Overridepublic boolean isEmpty() {return top == 0 ;}//求栈中数据元素个数@Overridepublic int length() {return top ;}//取栈顶元素@Overridepublic Object peek() {if (!isEmpty()) { //如果栈不为空return stackElem[top -1] ; //返回栈顶元素}else {return null ;}}//入栈@Overridepublic void push(Object x) throws Exception {// {....}}//出栈@Overridepublic Object pop() {// {....}return null ;}//输出栈中所有数据元素（从栈顶元素到栈底元素）public void display() {for (int i = top - 1 ; i >= 0 ; i -- ) {//输出System.out.print(stackElem[i].toString()+" ");}}}

注：代码中 ” {....}“ 处，会在后面单独进行讲解。

算法：入栈

算法1 ：

public void push(Object x) {if(top == stackElem.length) {//栈满throw new RuntimeException("栈满");} else {stackElem[top] = x;top++;}}

算法2：

public void push(Object x) {if(top == stackElem.length) {//栈满throw new RuntimeException("栈满");} else {stackElem[top++] = x;}}

算法：出栈

算法1：

public Object pop() {if(top == 0) {return null;//空栈} else {top--;return stackElem[top];}}

算法2：

public boolean isEmpty() {//是否为空return top == 0;}public Object pop() {if(isEmpty()) {return null;//空栈} else {return stackElem[--top];}}

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

(四) 链栈

一、什么是链栈？

使用链式存储的栈，就是链栈。

插入和删除操作在栈顶进行，也就是链表的尾端。

存储单元由2部分组成：数据域data和指针域next。

使用top栈顶指针用于指向栈尾

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

二、链栈类【LinkStack】

package data.linear_table.stack_queue;import data.linear_table.node.Node;//链栈类public class LinkStack implements IStack {private Node top ;//栈顶元素的引用//将栈置空@Overridepublic void clear() {top = null ;}//判断链栈是否为空@Overridepublic boolean isEmpty() {return top == null ;}//求链栈的长度@Overridepublic int length() {//{...} return 0 ;}//取栈顶元素并返回其值@Overridepublic Object peek() {//栈如果不为空if (!isEmpty()) {//返回栈顶元素return top.data ;}else {return null ;}}//入栈@Overridepublic void push(Object x) throws Exception {//{...} }//出栈@Overridepublic Object pop() {// {...}return null ;}//输出栈中所有数据元素（从栈顶元素到栈底元素）public void display() {Node p = top ;//初始化，p指向栈顶元素while (p != null ) { //输出所有非空结点的数据元素值System.out.print(p.data.toString()+" ");p = p.next ; //p指针向后移}}}

注：代码中 ” {....}“ 处，会在后面单独进行讲解。

public class LinkStack {private Node top;//栈顶指针}

算法：链栈的长度

//求链栈的长度@Overridepublic int length() {Node p = top ;//初始化,p指向栈顶元素int length = 0 ; //length为计数器//从栈顶元素开始向后查找，直到p为空while (p != null ) {p = p.next ; //p指向后继结点length++ ;//长度增加1}return length ;}

算法：入栈

public void push(Object x) {Node p = new Node(x); // 创建新结点pp.next = top;// 1.p的指针域指向栈顶元素top = p;// 2.栈顶指针top指向新结点p}

算法：出栈

public Object pop() {if(top == null) {//空栈 isEmpty()return null; } else {Node p = top; // 1 存放栈顶元素top = top.next;// 2 将top指向栈顶的下一个元素return p.data;// 3 返回栈顶元素数据}}

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

(五) 队列

一、什么是队列？

队列是一个特殊的线性表。

只允许在队尾进行插入操作

只允许在队首进行删除操作

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

二、队列的相关术语？

队尾rear：进行插入操作的一端。

队首front:进行删除操作的一端

入队offer: 进行插入操作，称为入队

出队poll : 进行删除操作，称为出队

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

三、队列有哪两种存储方式？

使用顺序存储的称为顺序队列。

使用链式存储的称为链队列。

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

四、队列的抽象数据类型Java接口【IQueue】

package data.linear_table.stack_queue;//队列的抽象数据类型Java接口public interface IQueue {public void clear() ; //置队成空队列public boolean isEmpty() ; //判断队列是否为空public int length() ; //队列中数据元素的个数public Object peek() ; //取队列首元素public void offer(Object x) throws Exception; //将元素x插入到队列中使用成为新的队尾元素public Object poll() ; //删除对首元素并返回其值。若队列为空，则返回null}

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

(六) 顺序队列

一、什么是顺序队列？

· 顺序队列的存储结构中，需要分配一块地址连续的存储区域来一次存放队列中从队首到队尾的所有元素。

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

二、关于队列的那些操作？

front表示队首，进行出队操作时，front进行计数。

rear表示队尾，进行入队操作时，rear进行计数。

front == rear == 0为空队列。

入队操作：

出队操作：

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

三、队列存在的问题“假溢出” 。

因为顺序队列的多次入队和出队操作后出现有存储空间，但是又不能顺序入队的溢出现象，称为“假溢出”。

假溢出，数组的最后一个元素已经添加数据，但队列没有满。

解决方案：使用循环队列解决“假溢出”问题。将顺序队列所使用的存储空间看成是一个逻辑上首尾相连的循环队列。

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

(七) 循环顺序队列

一、什么是循环顺序队列？

在逻辑上队首和队尾连接在一起。

存在的问题：队首front和队尾rear重叠时，无法区分队满还是队空。

解决方案：

方案1：设计一个计数器，出入队累计法。（整数变量num，入队+1，出队-1，如果num=0就是空）。判断条件为：num == 0 为队空；num > 0 && front == rear 为队满。

方案2：设计一个标识变量法。（flag=0出队，flag=1入队，重叠后0表示空，1表示满）。判断条件为：front == rear && flag == 0 为队空；front == rear && flag == 1 为队满。

方案3：少用一个存储单位。当顺序存储空间为maxSize时，只允许最多存放maxSize -1个数据元素。判断条件为：

// 队列空front == rear;// 队列满(rear + 1) % maxSize == front;

详解front == (rear+1) % maxSize 为队满：

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

循环顺序队列类！

循环顺序队列，在逻辑上是一个循环，也就是队首和队尾连接

循环顺序队列，在物理上就是一个数组。

循环顺序队列类Java语言描述【SqQueue】

—— 实现队列接口IQueue

package data.linear_table.stack_queue;//循环队列类public class SqQueue implements IQueue {private Object[] queueElem ; //队列的存空间private int front ; //队首的引用，若队列不为空，指向队首元素private int rear ; //队尾的引用，若队列不为空，指向队尾元素的下一个存储位置//循环队列类的构造函数public SqQueue(int maxSize) {front = rear = 0 ;//队首、队尾初始化为0queueElem = new Object[maxSize] ; //为队列分配maxSize个存储单元}//队列置空@Overridepublic void clear() {front = rear = 0 ;}//判断队列是否为空@Overridepublic boolean isEmpty() {return front == rear;}//求队列的长度@Overridepublic int length() {//（尾 - 头 + 队列长度） % 队列长度return (rear - front + queueElem.length)%queueElem.length ;}//读取队首元素@Overridepublic Object peek() {if (front == rear) {//队列为空return null ;}else {//返回队首元素return queueElem[front];}}//入队@Overridepublic void offer(Object x) throws Exception {//{..... }}//出队@Overridepublic Object poll() {//{..... }return null ;}//输出队列中的所有数据元素（从队首到队尾）public void display () {//队列不为空if (!isEmpty()) {for (int i = front ; i != rear ; i = (i+1)% queueElem.length ) {System.out.print(queueElem[i].toString()+" ");}}else {System.out.println("此队列为空");}}}

注：代码中 ” {....}“ 处，会在后面单独进行讲解。

算法：入队

//入队@Overridepublic void offer(Object x) throws Exception {//判断是否已经满了，如果已经满了，抛异常//例头front = 0 ; rear = 4 ；即queueElem.length = 5 ；//即：(rear+1) % queueElem.length = 5 % 5 = 0 = front ；满足，即队列满if ( (rear+1) % queueElem.length == front) {throw new RuntimeException("队列满了");}else {//没有满进行入队操作//入队只能从队尾进行添加。队尾rearqueueElem[rear] = x ;rear = (rear + 1) % queueElem.length ;//队尾rear累加1 ，但最后时需要归零}}

算法：出队

//出队@Overridepublic Object poll() {if (front == rear) {//队列为空return null ;}else {Object t = queueElem[front] ; //记录出队的元素front = (front+1) % queueElem.length ;//重新赋值队首+1 ，并且要归0return t ; //返回队列的队首元素}}

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

(八) 链队列

一、什么是链队列？

队列采用链式存储结构的队列叫链队列。

用两个指针front和rear来分别队首元素和队尾元素。

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

二、链队列类【LinkQueue】

链表所需结点类：

package data.linear_table.node;//单链表：结点类public class Node {public Object data ; //存放结点值public Node next ; // 后继结点的引用//无参时的构造函数public Node() {this(null,null);}//带一个参数时的构造函数public Node(Object data) {this(data,null);}//带两个参数时的构造函数public Node(Object data , Node next) {this.data = data ;this.next = next ;}}

LinkQueue类

package data.linear_table.stack_queue;import data.linear_table.node.Node;//链队列类public class LinkQueue implements IQueue {private Node front ; //队首指针private Node rear ; //队尾指针//链队列类的构造函数public LinkQueue () {front = rear = null ;}//队列置空@Overridepublic void clear() {front = rear = null ;}//判断队列是否为空@Overridepublic boolean isEmpty() {return front == null ;}//求队列的长度@Overridepublic int length() {Node p = front ;int length = 0 ;while (p != null ){p = p.next ;length++ ;}return length ;}//取首元素@Overridepublic Object peek() {if (front != null ) { //队列非空return front.data ;//返回队首结点数据域值} else {return null ;}}//入队@Overridepublic void offer(Object x) throws Exception {//{...}}//出队@Overridepublic Object poll() {//{...}return null}}

注：代码中 ” {....}“ 处，会在后面单独进行讲解。

算法：入队

//入队@Overridepublic void offer(Object x) throws Exception {Node p = new Node(x) ;//初始化新结点if (front != null) { //队列非空rear.next = p ; //指向队尾指向新结点rear = p ; //改变队尾的位置}else {//队列为空的话，新添加的这个就是队首元素front = rear = p ;}}

算法：出队

//出队@Overridepublic Object poll() {if (front != null ) { //队列非空Node p = front ; //p指向队首结点,记录被删除的结点front = front.next ;//队首结点移动到下一个if (p == rear ) { //只有应该元素，删除的队首结点是队尾时rear = null ;}return p.data ; //返回被删除的队首元素的数据域值}else {return null ;}}}

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

(九) 优先级队列

一、什么是优先级队列？

它是一种带有优先级的队列，是一种比栈和队列更为专用的数据结构。

有一个队首和队尾。

在队首删除数据元素，顺序插入元素到队列的合适位置。

队列中的每一个数据元素按照关键字的值有序排列。

约定：关键字最小的数据元素（或者在某些实现中要求数据是最大的）具有最高优先级。

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

二、优先级队列使用顺序和链两个存储结构那个更好呢？

可采用顺序和链式两种存储结构。

考虑到优先级队列，既要保证能够快速的访问到优先级高的数据，又要保证可以实现快速的插入操作。所以通常以链式存储结构来实现优先级队列。

数据级别的高低依据优先数来鉴定，优先数越小，优先级别就越大。

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

三、优先级队列中结点的数据域data类【PriorityData】

package data.linear_table.node;//优先队列中结点类的data类：数据域的值public class PriorityQData {public Object elem ; //结点的数据元素值public int priority ; //结点的优先数//构造函数public PriorityQData (Object elem , int priority ) {this.elem = elem ;this.priority = priority ;}}

四、实现IQueue接口的优先级队列类【PriorityQueue】

package data.linear_table.stack_queue;import data.linear_table.node.Node;import data.linear_table.node.PriorityQData;//优先队列【常以链式存储结构实现】public class PriorityQueue implements IQueue {private Node front ; //队首的引用private Node rear ; //队尾的引用//优先队列类的构造函数public PriorityQueue () {front = rear = null ;}//队列置空@Overridepublic void clear() {front = rear = null ;}//判断队列是否为空@Overridepublic boolean isEmpty() {return front == null;}//求队列长度@Overridepublic int length() {Node p = front ;int length = 0 ;while (p != null ){//一直查到队尾p = p.next ;length++ ;}return length ;}//读取首元素@Overridepublic Object peek() {if (front == null ){return null;}else {return front.data ; //返回队首结点的数据域值}}//入队@Overridepublic void offer(Object x) {// {...}}//出队@Overridepublic Object poll() {// {... }return null ;}//输出队列中的所有元素public void display() {if (!isEmpty()) {Node p = front ;while (p != null ) {PriorityQData q = (PriorityQData) p.data;System.out.println(q.elem+" " + q.priority);p = p.next ;}//从队首到队尾}else {System.out.println("此队列为空！");}}}

算法：出队

//出队@Overridepublic Object poll() {if (front == null){return null;}else {Node p = front ; //保存记录要被删除的队首元素front = front.next ; //队首指向下一个元素return p.data ;}}

算法：入队【数字越小，优先级越高】

情况1：队首插入（p如果指向队首front,表示新结点的优先级数字小）

情况2：队尾插入（q为null 或p 等于队尾rear）

情况3：在两个元素的中间插入

//入队@Overridepublic void offer(Object x) {PriorityQData pn = (PriorityQData) x ;Node s = new Node(pn) ; //构造一个新结点//如果队列为空if (front == null) {front = rear = s ; //修改队列首结点}else {// 1) 移动：按照优先级进行移动，优先级大就需要移动Node p = front ; //用于记录下一个Node q = front ; //用于记录前驱（之前的）// 队首不为null ,并且新结点的优先级 >= 队列结点的优先级【两者进行比较】while (p != null && pn.priority >= ((PriorityQData)p.data).priority ) {//满足，q = p ; //记录前驱p = p.next ; //指向下一个}// 2) 插入// 2.1 情况一：新结点的优先级比队尾还低if (p == null ) { // p，遍历到下一个结点为空，表示遍历到了队列尾部rear.next = s;//将新结点加入到队尾,队尾指针域next,指向新结点rear = s ;//修改队尾指针// 情况二：新结点的优先级比队首还高}else if (p == front ) {s.next = front ; //将新结点加入到队首，新结点s指向队首frontfront = s ; //修改队首指针// 情况三：新结点位于两个结点的中间}else {//新结点加入到队列中部q.next = s ;//q是s的前驱结点，则s是q的下一个结点s.next = p ;// s的下一个结点是p,则s为于 q 和 p 之间}}}

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

(十) 每日一练

41. 队列的插入操作在（）进行。
A．队头
B．队尾
C．队头或队尾
D．在任意指定位置
----------------------------------------------
42. 队列的删除操作在（）进行。
A．队头
B．队尾
C．队头或队尾
D．在任意指定位置
----------------------------------------------
43. 栈的插入操作在（）进行。
A．栈顶
B．栈底
C．栈顶或栈底
D．在任意指定位置
----------------------------------------------
44. 一个队列的入队序列是 2，4，6，8，则队列的输出序列是（）。
A．8，6，4，2
B．2，4，6，8
C．4，2，8，6
D．6，4，2，8
----------------------------------------------
45. 一个队列的入队序列是 5，6，7，8，则队列的输出序列是（）。
A. 5 6 7 8
B. 8 7 6 5
C. 7 8 6 5
D.可能有多种情况
----------------------------------------------
46. 一个栈的进栈序列是 1，2，3，4，则不可能的出栈序列是（）（进出栈操作可以交替进行）。
A．3，2，4，1
B．1，4，2，3 1 4 3 2
C．4，3，2，1
D．3，2，1，4
----------------------------------------------
47. 一个栈的进栈序列是 5，6，7，8，则栈的不可能的出栈序列是（）（进出栈操作可以交替进行）
A．5，8，6，7 5 8 7 6
B．7，6，8，5
C．7，6，5，8
D．8，7，6，5
----------------------------------------------
48. 一个栈的进栈序列是 a，b，c，d，e，则栈的不可能输出序列是（）（进栈出栈可以交替进行）。
A．dceab ain bin cin din dout cout ein eout bout aout --> dceba
B．edcba ain bin cin din ein eout dout cout bout aout --> edcba
C．decba ain bin cin din dout ein eout cout bout aout --> decba
D．abcde ain aout bin bout cin cout din dout ein eout --> abcde
----------------------------------------------
49. 以下说法不正确的是（）。
A．顺序栈中，栈满时再进行进栈操作称为“上溢”
B．顺序栈中，栈空时再作出栈栈操作称为“下溢”
C．顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满。（假溢出）
D．顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空
----------------------------------------------
50. 以下说法不正确的是（）。
A．栈的特点是后进先出
B．队列的特点是先进先出
C．栈的删除操作在栈底进行，插入操作在栈顶进行。栈顶删除
D．队列的插入操作在队尾进行，删除操作在队头进行
----------------------------------------------
51. 以下说法正确的是（）。
A．栈的特点是先进先出，队列的特点是先进后出
B．栈和队列的特点都是先进后出
C．栈的特点是先进后出，队列的特点是先进先出
D．栈和队列的特点都是先进先出
----------------------------------------------
52. 以下说法正确的是（）。
A．栈的特点是先进先出，队列的特点是先进后出
B．栈和队列的特点都是先进后出
C．栈的特点是先进后出，队列的特点是先进先出
D．栈和队列的特点都是先进先出
----------------------------------------------
53. 元素 2，4，6，8 按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。
A．8，6，4，2 2in4in 6in 8in 8out 6out 4out 2out --> 8642
B．2，4，6，8 2in 2out 4in 4out 6in 6out 8in 8out --> 2468
C．4，2，8，6 2in 4in 4out 2out 6in 8in 8out 6out --> 4286
D．8，6，2，48642
----------------------------------------------
54. 元素 2，4，6 按顺序依次进栈，则该栈的不可能的输出序列是（）。
A. 6 4 2 2in4in6in 6out 4out 2out --> 642
B. 6 2 4 642
C. 4 2 6 2in 4in 4out 2out 6in 6out --> 426
D. 2 6 4 2in 2out 4in 6in 6out 4out --> 264
----------------------------------------------
55. 栈的插入删除操作在（）进行。
A．栈底
B．任意位置
C．指定位置
D．栈顶
----------------------------------------------
56. 栈和队列的相同点是（）。
A．都是后进先出
B．都是后进后出
C．逻辑结构与线性表不同
D．逻辑结构与线性表相同，都是操作规则受到限制的线性表
----------------------------------------------
57. 从一个栈顶指针为 top 的链栈中插入一个由 P 指向的新结点时，则执行的操作是（）。
A．p.setNext(top); top=p;
B．top=p; p.setNext(top);
C．top.setNext(p); p=top;
D．top.setNext(p); p=top;
-----------------------------------------------------------------------
58. 设 top 是一个链栈的栈顶指针，栈中每个结点由一个数据域 data 和指针域 next 组成，
设用 x 接收栈顶元素，则出栈操作为（）。
A．x=top.getData(); top=top.getNext();
B．top=top.getNext();x=top.getData();
C．x=top.getNext(); top=top.getData();
D．top.setNext(top); x=top.getData();
-----------------------------------------------------------------------
59. 在一个链队列中，假设 f 和 r 分别为队头和队尾指针，则插入 s 所指结点的运算为（）。
A．f．setNext(s); f=s;
B．r.setNext（s）; r=s;
C．s．setNext(r); r=s;
D．s.setNext(f); f=s;
-----------------------------------------------------------------------
60. 在一个链队列中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算为（）。
A．r=f.getNext();
B．r=r.getNext();
C．f=r.getNext();
D．f=f.getNext();
-----------------------------------------------------------------------
61. 在一个循环队列中，队列的空间大小为 length, 设对头指针为 front, 队尾指针为 rear,
按照教材采用减少一个存储元素的方法，以下那个能判断队列已满。（）
A. (rear+1)%length==front;
B. rear==front;
C. rear%length==front ;
D. (rear-1)%length==front;
-----------------------------------------------------------------------
62. 若一个栈用数组 data[1..n]存储,初始栈顶指针 top 为 n, 则如元素 x 进栈的正确操作是：（）
A. top++; data[top]=x;
B. data[top]=x;top++;
C. top--;data[top]=x ;
D. data[top]=x;top--;

如果觉得文章对您有帮助，就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来，让我们一起加油学习。博主会不断推出更多优质文章哟

想要了解更多吗？没时间解释了，快来点一点！

《数据结构-Java语言描述》打卡第一天/zsy3757486/article/details/123735691?spm=1001..3001.5501《数据结构-Java语言描述》打卡第二天/zsy3757486/article/details/123786120?spm=1001..3001.5501《数据结构-Java语言描述》打卡第三天/zsy3757486/article/details/123810848?spm=1001..3001.5501《数据结构-Java语言描述》打卡第四天/zsy3757486/article/details/123846758?spm=1001..3001.5501《数据结构=Java语言描述》打卡第五天/zsy3757486/article/details/123862163?spm=1001..3001.5501

本内容不代表本网观点和政治立场，如有侵犯你的权益请联系我们处理。

网友评论

网友评论仅供其表达个人看法，并不表明网站立场。

数据结构—栈与队列【顺序存储 链式存储 卡特兰数 优先级队列】

目录

第三章：栈与队列​

(一) 栈、队列和线性表有什么区别？

(二) 栈

一、 什么是栈？栈又有什么特性？

二、栈都有那些术语操作？

三、 对于四个元素ABCD它们的出栈的序列有多少种呢？

四、卡特兰数

五、栈的抽象数据类型Java接口 【 IStack】

(三) 顺序栈

一、什么是顺序栈？

二、那么顺序栈默认采用那种top情况呢？

三、顺序栈类 【SqStack】

(四) 链栈

一、什么是链栈？

二、链栈类 【LinkStack】

(五) 队列

一、什么是队列？

二、队列的相关术语？

三、 队列有哪两种存储方式 ？

四、队列的抽象数据类型Java接口【IQueue】

(六) 顺序队列

一、什么是顺序队列？

二、关于队列的那些操作？

三、队列存在的问题“假溢出” 。

(七) 循环顺序队列

一、什么是循环顺序队列？

循环顺序队列类 ！

循环顺序队列类Java语言描述【SqQueue】

(八) 链队列

一、什么是链队列？

二、链队列类【LinkQueue】

链表所需结点类：

LinkQueue类

(九) 优先级队列

一、什么是优先级队列？

二、优先级队列使用顺序和链两个存储结构那个更好呢？

三、优先级队列中结点的数据域data类【PriorityData】

四、实现IQueue接口的优先级队列类【PriorityQueue】

(十) 每日一练

如果觉得文章对您有帮助，就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来，让我们一起加油学习。博主会不断推出更多优质文章哟

想要了解更多吗？没时间解释了，快来点一点！

数据结构—栈与队列【顺序存储链式存储卡特兰数优先级队列】

第三章：栈与队列

一、什么是栈？栈又有什么特性？

三、对于四个元素ABCD它们的出栈的序列有多少种呢？

五、栈的抽象数据类型Java接口【 IStack】

三、顺序栈类【SqStack】

二、链栈类【LinkStack】

三、队列有哪两种存储方式？

循环顺序队列类！