数据结构的循环队列问题：以下这道题为什么删除两个，增加3个元素后，rear和front的值分别是5,3？我算出来的结果却是3,5.晕死了，求高手解答下。1、若用一个大小为7的数组来实现循环队列，且当rear和front的值分别为0，3。当从队列中删除两个元素，再加入三个元素后，rear和front的值分别为
是5和3.你看清楚了front指向对头，当前为3，删除两个相当于出队，front值加2.不懂可以继续提问
应该是答案有问题
为您推荐：
扫描下载二维码第三章栈和队列
一.基本要求、重点、难点
本章的目的是介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。本章重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。
二.考核目标和考核要求
要求达到识记层次的有：栈和队列的特点，什么样的情况下能够使用栈或队列
要达到综合应用层次的有：栈的逻辑结构特点，栈与线性表的异同；顺序栈和链栈上实现的进栈、退栈等基本算法；栈的“上溢”和“下溢”的概念及其判别条件；利用栈设计算法解决简单的应用问题；队列的逻辑结构特点，队列与线性表的异同；顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法；队列的“上溢”和“下溢”的概念及其判别条件；使用数组实现的循环队列取代普通的顺序队列的原因；循环队列中对边界条件的处理方法；利用队列设计算法解决简单的应用问题。
1.单项选择题
1.1栈是一种受限的线性表，它的特点是（&&B
A）先进先出
B）后进先出
C）进优于出
D）随机进出
1.2设一个栈的输入序列为a，，c,d，则所得出栈的输出序列不可能是（&&D&
A）a,b,c,d
B）d,a,b,c
C）a,c,d,b
D）d,c,b,a
1.3由两个栈共享受1个向量空间的好处是（&&D&
A）减少存取时间，降低下溢发生的几率
B）节省存储空间，降低下溢发生的几率
C）减少存取时间，降低上溢发生的几率
D）节省存储空间，降低上溢发生的几率
1.4设有一个空栈，现有输入序列为1，2，3，4，5，经过pusu,push,pop,push,pop,pop,push,push,pop后输出序列是（&C）
A）2，3，4，5
B）5，1，3，4
C）2，3，1，5
D）3，1，4，2
1.5判断一个顺序表st（最多元素为StackSize）为栈满的条件是（&&D&&
A）st.top！= StackSize
B）st.top！=0
C）st.top==-1
D）st.top==StackSize-1
1.6一个队列的入队序列是1，3，5，7，9，则出队的输出序列只能是（&&
A）9，7，5，3，1
B）1，3，5，7，9
C）1，5，9，3，7
D）9，5，1，7，3
1.7判断一个顺序队列sq（最多元素为QueueSize）为空队列的条件是（&&A&&
A）sq.rear==cq.front
B）sq.rear==0
C）sq.front==QueueSize
D）sq.rear==QueueSize+1
1.8判断一个循环队列cq（最多元素为QueueSize）为满队列的条件是（&&C&
A）cq.rear==cq.front
B）cq.rear==QueueSize
C）（cq.rear+1）% QueueSize==cq.front
D）cq.rear%QueueSize+1==cq.front
1.9队列中的元素个数是（&&B
1.10同一队列内各元素的类型（&&&A
A）必须一致
B）可以不一致
C）不能一致
1.11循环队列占用的空间（&&A&&
A）必须连续
B）可以不连续
C）不能连续
D）不必连续
1.12容量是10的循环队的头指针的位置Sq.front为2，则队的头元素的位置是（&&B&
1.13初始化一个空间大小为5的顺序栈Ss后，Ss-&top的值（&&&A&
C）不再改变
D）动态变化
1.14经过下列栈的运算后StackTop（）的值是（&A&&）
InitStack(s);Push(s,a);Push(s,b),Pop(s);
1.15经过下列栈的运算后*x的值是（
&&B&&）InitStack(s);Push(s,a);Push(s,b),StackTop(s);
1.16一个循环队列一旦说明，其占用空间的大小（&&A&
B）可以改变
C）不能固定
D）动态变化
1.17队列结构属于下列结构中的（&&B&&
1.18设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front的值为（&&&D&
A）front=front+1
B）front=（front+1）%（m-1）
C）front=（front-1）%m
D）front=（front+1）%m
1.19存放循环队列元素的数组data有10元素，则data数组的下标范围是（&&B&
A）0……10
C）1……10
1.20存放循环队列Sq元素的数组data有10个元素，Sq-&front为9，队列的头元素的位置在（&&&A）
2.1栈又称后进先出表，队列又称为[先进先出]表
2.2设S[maxsize]为一个顺序存储的栈，变量Top指向栈顶位置，栈为空的条件是[S.top==-1]
2.3设S[maxsize]为一个顺序存储的栈，变量Top指向栈顶位置，栈为满的条件是[S.top==masize-1]
2.4对栈进行入栈操作时，应先判别栈是否为[栈满]
2.5对栈进行退栈操作时，应先判别栈是否为[空栈]
2.6已知一个栈的输入序列为1，2，3，…，，则其输出序列的第2个元素为的输出序列的个数是[n-1]
2.7设sq[maxsize]为一个顺序存储的栈，变量top（为负数时栈为空）指示栈顶元素的位置，能做入栈操作的条件是[S.top&maxsize-1]
2.8设sq[maxsize]为一个顺序存储的栈，变量top（为负数时栈为空）指示栈顶元素的位置，如要把栈顶元素弹出并送到x中，则需执行下列语句：[x=s.data[s.top];s.top=s.top+1;]
2.9元素进入队列的那端是[队尾]
2.10对链栈ls，指向栈顶元素的指针是[ls-&next]
2.11链栈ls是空栈的条件是[ls-&next==NULL]
2.12链栈ls的栈顶元素是链表的[首]元素
2.13栈经过运算InitStack(s);Push(s,a);Push(s,b)后StackTop（S）的值是[b]
2.14已知循环队列sq，在进行出队操作之前首先要判断[队空否]
2.15循环队列sq存储在数组sq.data[0…max]中，sq.front为i，则存放队列头元素的数组元素是[sq.data[i]]
2.16循环队列sq存储在数组sq.data[0…max]中，sq.rear为0，则存放队列尾元素的数组元素是[sq.data[max]]
2.17循环队列sq存储在数组sq.data[0…max]中，则sq中最多能存放[max+1]个队列元素
2.18在链队列lq中，链队的尾元素是链表的[尾]元素
2.19循环队列sq经过运算InitQueue(sq),
sq.front=[0]
2.20循环队列sq经过运算InitQueue(sq),
sq.rear=[0]
3.1在栈的顺序存储结构下，进栈（向栈中插入元素）的操作步骤是什么（用什么语言描述）？退栈（从栈中删除元素）的操作步骤是哪些？
答：进栈操作是先将栈顶指针加1后，再将待插入元素入栈，退栈操作则是先取出栈顶元素，在使栈顶指针减1。
3.2有循环队列cq（最大长度QueueSize，rear和front分别为队尾和队首指针）使用C语言表示的入队、出队操作时队首、队尾指针移动语句。
答：入队操作的指针移动语句为：cq.rear=(cq.rear+1)%QueueSize；
出队操作的指针移动语句为：cq.front=(cq.front+1)%QueueSize；
3.3如果编号为1，2，3的三辆列车进入一个栈式结构的站台，那么可能得到的三辆列车出站序列有哪些？不可能出现的序列是什么？
答：所有可能的出站顺序有：123，132，213，231，321，不可能是312，因为当3号车进站并出站后，站台上有1号车和2号车，不可能先出1号而后出2号。
3.4对于队列来说，出队操作和取队头有什么区别？
答：出队操作是删除队头元素（修改头指针）之后，再返回该删除元素值，而取队头操作仅仅是取出队头元素值返回，不修改队头指针。
3.5简述下面给出的算法的功能是什么？（假设栈元素为整数类型）
void ex31(SeqStack *s)
&&&&&&& int A[80],i,n;
while(!empty(S))
&&&&&&&&&& A[n]=pop(s);
n++;
for(i=0;i&n;i++)
push(S,A[i]);
此算法的功能是通过一个数组将一个栈中的所有元素逆置存放。
3.6简述下面给出的算法的功能是什么？（假设栈元素为整数类型）
void ex32(SeqStack *s,int c)
&&&&&&&& SeqStackT;
while(!StackEmpty(S))
&&&&&&&&&&&& d=pop(S);
push(T,d);
&&&&&&&& }
while(!StackEmpty(T))
&&&&&&&&&&& d=pop(T);
push(S,d);
&&&&&&&& }
该算法的功能是通过一个中间栈T，达到删除栈S中所有与变量C相同的元素。
3.7设长度为的链队列用循环链表表示，若只设头指针则入队操作的时间复杂度是多少？若只设尾指针呢？
答：只设头指针的入队操作时间复杂度为O（）；只设尾指针的入队操作时间复杂度为O（1）
3.8简述栈的特点及与一般线性表的区别？
答：栈叫先进后出表或叫后进先出表。栈的插入和删除都从称为栈顶的一端进行，一般线性表可以在线性表的中间及两端进行插入和删除操作。
3.9简述队列的特点及与一般线性表的区别？
答：队列叫先进先出表（FIFO）或叫后进后出表，队列的插入只能在队列的一端进行，该端称为队尾。队列的删除只能从另一端进行，该端称为队头。一般线性表可以在线性表的中间及两端进行插入和删除操作。
3.10比较栈和队列的相同点与不同点
答：栈和队列都是加了限制的线性表，栈叫后进先出表，队列叫先进先出表。栈和队列的插入和删除运算都在端点进行，栈的插入与删除在同一端点，队列的插入与删除在不同的端点进行。栈与队列的元素个数都是可变的，同一个栈或同一个队列中的元素类型是一致的。
3.11写出下列程序段的输出结果
&& Stack S;
InitStack(S);
x=’c’;y=’k’
Push(S,x);
&& Push(S,’a’);
Push(S,y);
&& Pop(S,x);
Push(S,’t’);
&& Push(S,x);
&& Push(S,’’);
while(!StackEmpty(S))
&&&&& Pop(S,y);
printf(y);
printf(x);
&输出结果：stack
3.12简述下列算法的功能
algo(StackS)
&& int i,n,a[255];
while(!StackEmpty(s))
&&&& n++;Pop(S,A[n]);}
for(i=1;i&=n;i++)
&&&& Push(S,A[i]);
借助数组将S栈内的元素倒置
3.13简述下列算法的功能
algo2(Stack S)
InitStack(T);
while(!StackEmpty(s))
&&& Pop(S,d);
&&& Push(T,d);
while(!StackEmpty(T))
&&&& Pop(T,d);
&&&& Push(S,d);
&借助T栈将S栈内的元素倒置
&&& 4.算法设计
4.1顺序栈的六种基本操作
voidInitStack(SeqStack*S)
& //将顺序栈置空
S-&top=-1;}
& intStackEmpty(SeqStack*S)
&&&&&&& returnS-&top==1;
& intStackFull(SeqStack*S)
&&&&&&& returnS-&top==StackSize-1;
& voidPush(SeqStack*S, DataType x)
&&& if(StackFull(S))
&&& Error(“Stackoverflow”);//上溢，退出运行
&&&&&&&S-&data[++S-&top]=x;//栈顶指针加1后将x进栈
&&DataTypePop(SeqStack*s)
&& if(StackEmpty(S))
&& Error(“Stackunderflow”);//下溢，退出运行
returnS-&data[S-&top--];//栈顶元素返回后将栈顶指针减1
DataTypeStackTop(SeqStack*s)
&&&&&& if(StackEmpty(S))
Error(“Stack is empty”);
return&S-&data[S-&top]
4.2循环队列基本算法
#defineQueueSize100
typedefcharDataType//DataType的类型依赖于具体应用
typedefSturet{
//头指针，队非空时指向队头元素
//尾指针，队非空时指向队尾元素的下一位置
//计数器，记录队中元素总数
DataTypedata[QueueSize]
voidInitQueue(CirQueue*Q)
Q-&count=0;
Q-&count=0;//计数器置0}
&& intQueueEmpty(CirQueue*Q)
{ returnQ-&count==0;//队列无元素为空}
intQueueFull(CirQueue*Q)
{returnQ-&count==QueueS //队中元素个数等于QueueSize时队满}
voidEnQueue(CirQueue*Q, DataTypex)
{if(QueueFull(Q))
Error(“Queueoverflow”);//队满上溢
Q-&count++;//队列元素个数加1
Q-&data[Q-&rear]=x;//新元素插入队尾
Q-&rear=(Q-&rear+1)%QueueS
DataTypeDeQueue(CirQueue*Q)
if(QueueEmpty(Q))
Error(“Queueunderflow”); //队空下溢
temp=Q-&data[Q-&front];
Q-&count--;
Q-&front=(Q-&front+1)%QueueS//循环意义下的头指针加1
DataTypeQueueFront(CirQueue*Q)
&& if(QueueEmpty(Q))
Error(“Queue is empty.”);
return Q-&data[Q-&
数据结构习题之栈和队列
;New-&Project，选PyDev下的PyDevProject，Grammer和Interpreter选相应的版本，Finish。在PyDevPackageExplorer的项目上右键
文件夹里放的是文档，Grammer是语法分析器，include是python所包含的一些头文件，Lib是python的库，都是用python语言写的，Moduels是用C写的python模块
参考链接：1.参考：《算法导论》
[1]聚类算法AP：[2]计算图像距离算法：参考资料：Large-ScaleImageAnnotationusingVisualSynset，DavidTsaietc.
BM和KMP字符串匹配算法学习分类：研究与学习字符串匹配BM（Boyer-Moore）算法学习心得字符串匹配那些事BM模式匹配算法原理（图解）精确字符串匹配（BM算法）BM算法中&好后缀
().getResourceAsStream("yp/library/autogrammer/test/Grammer.txt"));StateTablestateTable=newStateTable(grammer
算法概述从字面意义上理解，算法（Algorithm）就是用于计算的方法，并通过这种方法可以达到预期的计算结果。算法的专业解释：算法是解决实际问题的一种精确描述的方法，算法是对特定问题的求解步骤的一种
MOEAFramework是一个用来开发multiobjectiveevolutionary算法(MOEAs)的Java类库，提供的算法还包括：NSGA-II,ε-MOEA,GDE3,andMOEA
正则表达式在线测试工具
FaceYe @ 2015 &&&&
ICP备案号:粤ICP备1500070数据结构 自测题1-5答案_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
数据结构 自测题1-5答案
上传于||暂无简介
阅读已结束，如果下载本文需要使用0下载券
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，查找使用更方便
还剩1页未读，继续阅读
定制HR最喜欢的简历
你可能喜欢数据结构与算法（三），栈与队列 - 简书
<div class="fixed-btn note-fixed-download" data-toggle="popover" data-placement="left" data-html="true" data-trigger="hover" data-content=''>
写了54996字，被160人关注，获得了93个喜欢
数据结构与算法（三），栈与队列
转载请注明出处：
上一篇《》中介绍了数据结构中线性表的两种不同实现——顺序表与链表。这一篇主要介绍线性表中比较特殊的两种数据结构——栈与队列。首先必须明确一点，栈和队列都是线性表，它们中的元素都具有线性关系，即前驱后继关系。
1、基本概念
2、栈的顺序存储结构
3、两栈共享空间
4、栈的链式存储结构
5、栈的应用——递归
1、基本概念
2、队列的顺序存储结构
3、队列的链式存储结构
1、基本概念
栈（也称下压栈，堆栈）是仅允许在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）。栈是一种后进先出（Last In First Out）的线性表，简称（LIFO)结构。栈的一个典型应用是在集合中保存元素的同时颠倒元素的相对顺序。
抽象数据类型：
栈同线性表一样，一般包括插入、删除等基本操作。其基于泛型的API接口代码如下：
public interface Stack&E& {
//栈是否为空
boolean isEmpty();
//栈的大小
int size();
void push(E element);
//返回栈顶元素
栈的实现通常有两种方式：
基于数组的实现（顺序存储）
基于链表的实现（链式存储）
2、栈的顺序存储结构
栈的顺序存储结构其实是线性表顺序存储结构的简化，我们可以简称它为「顺序栈」。其存储结构如下图：
栈的顺序存储结构
实现代码如下：
import java.util.I
* 能动态调整数组大小的栈
public class ArrayStack&E& implements Iterable&E&, Stack&E& {
private E[]
private int size=0;
@SuppressWarnings("unchecked")
public ArrayStack() {
elements = (E[])new Object[1]; //注意：java不允许创建泛型数组
@Override public int size() {}
@Override public boolean isEmpty() {return size == 0;}
//返回栈顶元素
@Override public E peek() {return elements[size-1];}
//调整数组大小
public void resizingArray(int num) {
@SuppressWarnings("unchecked")
E[] temp = (E[])new Object[num];
for(int i=0;i&i++) {
temp[i] = elements[i];
elements =
@Override public void push(E element) {
if(size == elements.length) {
resizingArray(2*size);//若数组已满将长度加倍
elements[size++] =
@Override public E pop() {
E element = elements[--size];
elements[size] =
//注意：避免对象游离
if(size & 0 && size == elements.length/4) {
resizingArray(elements.length/2);//小于数组1/4,将数组减半
//实现迭代器, Iterable接口在java.lang中，但Iterator在java.util中
public Iterator&E& iterator() {
return new Iterator&E&() {
private int num =
public boolean hasNext() {
return num & 0;
public E next() {
return elements[--num];
public static void main(String[] args) {
int[] a = {1,2,3,4,new Integer(5),6};//测试数组
ArrayStack&Integer& stack = new ArrayStack&Integer&();
System.out.print("入栈顺序：");
for(int i=0;i&a.i++) {
System.out.print(a[i]+" ");
stack.push(a[i]);
System.out.println();
System.out.print("出栈顺序数组实现：");
for (Integer s : stack) {
System.out.print(s+" ");
每项操作的用时都与集合大小无关
空间需求总是不超过集合大小乘以一个常数
缺点：push()和pop()操作有时会调整数组大小，这项操作的耗时和栈的大小成正比
3、两栈共享空间
用一个数组来存储两个栈，让一个栈的栈底为数组的始端，即下标为0，另一个栈的栈底为数组的末端，即下标为 n-1。两个栈若增加元素，栈顶都向中间延伸。其结构如下：
两栈共享空间
这种结构适合两个栈有相同的数据类型并且空间需求具有相反的关系的情况，即一个栈增长时另一个栈缩短。如，买股票，有人买入，就一定有人卖出。
public class SqDoubleStack&E& {
private static final int MAXSIZE = 20;
private E[]
private int leftSize=0;
private int rightSize= MAXSIZE - 1;
//标记是哪个栈
enum EnumStack {LEFT, RIGHT}
@SuppressWarnings("unchecked")
public SqDoubleStack() {
elements = (E[])new Object[MAXSIZE]; //注意：java不允许创建泛型数组
public void push(E element, EnumStack es) {
if(leftSize - 1 == rightSize)
throw new RuntimeException("栈已满，无法添加");
if(es == EnumStack.LEFT) {
elements[leftSize++] =
elements[rightSize--] =
public E pop(EnumStack es ) {
if(es == EnumStack.LEFT) {
if(leftSize &= 0)
throw new RuntimeException("栈为空，无法删除");
E element = elements[--leftSize];
elements[leftSize] =
//注意：避免对象游离
if(rightSize &= MAXSIZE - 1)
throw new RuntimeException("栈为空，无法删除");
E element = elements[++rightSize];
elements[rightSize] =
//注意：避免对象游离
public static void main(String[] args) {
int[] a = {1,2,3,4,new Integer(5),6};//测试数组
SqDoubleStack&Integer& stack = new SqDoubleStack&Integer&();
System.out.print("入栈顺序：");
for(int i=0;i&a.i++) {
System.out.print(a[i]+" ");
stack.push(a[i], EnumStack.RIGHT);
System.out.println();
System.out.print("出栈顺序数组实现：");
for(int i=0;i&a.i++) {
System.out.print(stack.pop(EnumStack.RIGHT)+" ");
4、栈的链式存储结构
栈的链式存储结构，简称链栈。为了操作方便，一般将栈顶放在单链表的头部。通常对于链栈来说，不需要头结点。
其存储结构如下图：
栈的链式存储结构
代码实现如下：
import java.util.I
public class LinkedStack&E& implements Stack&E&, Iterable&E& {
private int size = 0;
private Node head =//栈顶
private class Node {
Node(E element, Node next) {
this.element =
this.next =
@Override public int size() {}
@Override public boolean isEmpty() {return size == 0;}
@Override public E peek() {return head.}
@Override public void push(E element) {
Node node = new Node(element, head);
@Override public E pop() {
E element = head.
head = head.
public Iterator&E& iterator() {
return new Iterator&E&() {
private Node current =
public boolean hasNext() {
return current !=
public E next() {
E element = current.
current = current.
public static void main(String[] args) {
int[] a = {1,2,3,4,new Integer(5),6};//测试数组
LinkedStack&Integer& stack = new LinkedStack&Integer&();
System.out.print("入栈顺序：");
for(int i=0;i&a.i++) {
System.out.print(a[i]+" ");
stack.push(a[i]);
System.out.println();
System.out.print("出栈顺序链表实现：");
for (Integer s : stack) {
System.out.print(s+" ");
注意：私有嵌套类（内部类Node）的一个特点是只有包含他的类能够直接访问他的实例变量，无需将他的实例变量（element）声明为public或private。即使将变量element声明为private，外部类依然可以通过Node.element的形式调用。
所需空间和集合的大小成正比
操作时间和集合的大小无关
链栈的push和pop操作的时间复杂度都为 O(1)。
缺点：每个元素都有指针域，增加了内存的开销。
顺序栈与链栈的选择和线性表一样，若栈的元素变化不可预料，有时很大，有时很小，那最好使用链栈。反之，若它的变化在可控范围内，使用顺序栈会好一些。
5、栈的应用——递归
栈的一个最重要的应用就是递归。那么什么是递归呢？借用《》中的话：
递归从狭义上来讲，指的是计算机科学中（也就是像各位程序猿都熟悉的那样），一个模块的程序在其内部调用自身的技巧。如果我们把这个效果视觉化就成为了「德罗斯特效应」，即图片的一部分包涵了图片本身。
如下面这张图，「先有书还是先有封面 ？」
德罗斯特效应
我们把一个直接调用自身或通过一系列语句间接调用自身的函数，称为递归函数。每个递归函数必须至少有一个结束条件，即不在引用自身而是返回值退出。否则程序将陷入无穷递归中。
一个递归的例子：斐波那契数列（Fibonacci）
斐波那契数列
递归实现：
public int fibonacci(int num) {
if(num & 2)
return num == 0 ? 0 : 1;
return fibonacci(num - 1) + fibonacci(num - 2);
迭代实现：
public int fibonacci(int num) {
if(num & 2)
return num == 0 ? 0 : 1;
int temp1 = 0;
int temp2 = 1;
int result = 0;
for(int i=2; i & i++) {
result = temp1 + temp2;
temp1 = temp2;
迭代与递归的区别：
迭代使用的是循环结构，递归使用的是选择结构。
递归能使程序的结构更清晰、简洁，更容易使人理解。但是大量的递归将消耗大量的内存和时间。
编译器使用栈来实现递归。在前行阶段，每一次递归，函数的局部变量、参数值及返回地址都被压入栈中；退回阶段，这些元素被弹出，以恢复调用的状态。
1、基本概念
队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。它是一种基于先进先出（First In First Out，简称FIFO）策略的集合类型。允许插入的一端称为队尾，允许删除的一端称为队头。
抽象数据类型：
队列作为一种特殊的线性表，它一样包括插入、删除等基本操作。其基于泛型的API接口代码如下：
public interface Queue&E& {
//队列是否为空
boolean isEmpty();
//队列的大小
int size();
void enQueue(E element);
E deQueue();
同样的，队列具有两种存储方式：顺序存储和链式存储。
2、队列的顺序存储结构
其存储结构如下图：
队列的顺序存储
与栈不同的是，队列元素的出列是在队头，即下表为0的位置。为保证队头不为空，每次出队后队列中的所有元素都得向前移动，此时时间复杂度为 O(n)。此时队列的实现和线性表的顺序存储结构完全相同，不在详述。
若不限制队列的元素必须存储在数组的前n个单元，出队的性能就能大大提高。但这种结构可能产生「假溢出」现象，即数组末尾元素已被占用，如果继续向后就会产生下标越界，而前面为空。如下图：
解决「假溢出」的办法就是若数组未满，但后面满了，就从头开始入队。我们把这种逻辑上首尾相连的顺序存储结构称为循环队列。
数组实现队列的过程：
循环队列实现过程
假设开始时数组长度为5，如图，当f入队时，此时数组末尾元素已被占用，如果继续向后就会产生下标越界，但此时数组未满，将从头开始入队。当数组满（h入队）时，将数组的长度加倍。
代码如下：
import java.util.I
* 能动态调整数组大小的循环队列
public class CycleArrayQueue&E& implements Queue&E&, Iterable&E& {
//记录队列大小
//first表示头元素的索引
//last表示尾元素后一个的索引
private E[]
@SuppressWarnings("unchecked")
public CycleArrayQueue() {
elements = (E[])new Object[1];
@Override public int size() {}
@Override public boolean isEmpty(){return size == 0;}
//调整数组大小
public void resizingArray(int num) {
@SuppressWarnings("unchecked")
E[] temp = (E[])new Object[num];
for(int i=0; i& i++) {
temp[i] = elements[(first+i) % elements.length];
elements =
first = 0;//数组调整后first，last位置
@Override public void enQueue(E element){
//当队列满时，数组长度加倍
if(size == elements.length)
resizingArray(2*size);
elements[last] =
last = (last+1) % elements.//【关键】
@Override public E deQueue() {
if(isEmpty())
E element = elements[first];
first = (first+1) % elements.//【关键】
//当队列长度小于数组1/4时，数组长度减半
if(size & 0 && size & elements.length/4)
resizingArray(2*size);
//实现迭代器
public Iterator&E& iterator() {
return new Iterator&E&() {
private int num =
private int current =
public boolean hasNext() {
return num & 0;
public E next() {
E element = elements[current++];
public static void main(String[] args) {
int[] a = {1,2,4,6,new Integer(10),5};
CycleArrayQueue&Integer& queue = new CycleArrayQueue&Integer&();
for(int i=0;i&a.i++) {
queue.enQueue(a[i]);
System.out.print(a[i]+" ");
System.out.println("入队");
for (Integer s : queue) {
System.out.print(s+" ");
System.out.println("出队");
3、队列的链式存储结构
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们简称为「链队列」。
存储结构如下图：
队列的链式存储
代码如下：
import java.util.I
* 队列的链式存储结构，不带头结点的实现
public class LinkedQueue&E& implements Queue&E&, Iterable&E& {
private N //头结点
private N //尾结点
private int size = 0;
private class Node {
Node(E element) {
this.element =
@Override public int size() {}
@Override public boolean isEmpty(){return size == 0;}
@Override public void enQueue(E element) {
Node oldLast =
last = new Node(element);
if(isEmpty()) {
first =//【要点】
oldLast.next =
@Override public E deQueue() {
E element = first.
first = first.
if(isEmpty())
last =//【要点】
//实现迭代器
public Iterator&E& iterator() {
return new Iterator&E&() {
private Node current =
public boolean hasNext() {
return current !=
public E next(){
E element = current.
current = current.
public static void main(String[] args) {
int[] a = {1,2,4,6,new Integer(10),5};
LinkedQueue&Integer& queue = new LinkedQueue&Integer&();
for(int i=0;i&a.i++) {
queue.enQueue(a[i]);
System.out.print(a[i]+" ");
System.out.println("入队");
for (Integer s : queue) {
System.out.print(s+" ");
System.out.println("出队");
循环队列与链队列，它们的基本操作的时间复杂度都为 O(1)。和线性表相同，在可以确定队列长度的情况下，建议使用循环队列；无法确定队列长度时使用链队列。
栈与队列，它们都是特殊的线性表，只是对插入和删除操作做了限制。栈限定仅能在栈顶进行插入和删除操作，而队列限定只能在队尾插入，在队头删除。它们都可以使用顺序存储结构和链式存储结构两种方式来实现。
对于栈来说，若两个栈数据类型相同，空间需求相反，则可以使用共享数组空间的方法来实现，以提高空间利用率。对于队列来说，为避免插入删除操作时数据的移动，同时避免「假溢出」现象，引入了循环队列，使得队列的基本操作的时间复杂度降为 O(1)。
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮
被以下专题收入，发现更多相似内容：
如果你是程序员，或者有一颗喜欢写程序的心，喜欢分享技术干货、项目经验、程序员日常囧事等等，欢迎投稿《程序员》专题。
专题主编：小...
· 268053人关注
玩转简书的第一步，从这个专题开始。
想上首页热门榜么？好内容想被更多人看到么？来投稿吧！如果被拒也不要灰心哦～入选文章会进一个队...
· 148551人关注
为进军数据结构和算法界而奋斗 !!!
· 1025人关注
如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
选择支付方式：}