首页天道酬勤循环队列是线性结构吗,数据结构环形队列

循环队列是线性结构吗,数据结构环形队列

张世龙 05-06 11:51 33次浏览

队列和循环队列1 .队列1.1定义循环队列1.2基本介绍循环队列1.3基于数组模拟的队列1.3.1数据模拟队列图像1.3.2数组模拟队列思路1.4代码实现队列2

1 .队列1.1定义队列

队列是一个线性表,只允许在一端进行插入操作,而在另一端允许删除操作。

1.2队列的基本介绍1 )队列是有序的列表,可以通过数组和链表实现

2 )队伍遵循先进先出原则。 即,先排队的数据先取出。 以后寄存的东西以后再拿出来。

3 )队列映像

1.3通过数组模拟实现队列1.3.1数据模拟的队列映像

1.3.2数组模拟队列的想法1 )首先,确定队列中的开头指针(front )和结尾指针(rear ),它们从一开始就指向开头元素前面-1的位置

2 )如果front==rear,则可以确定队列为空

3 )如果rear==maxSize (队列最大容量),则可以确定队列已满

1.4代码实现队列数据包队列; import java.util.Scanner; //数组模拟队列public class ArrayQueue数组队列(publicstaticvoidmain (字符串[ ] args ) ) arrayqueue=newarrayqueue); char key=' '; sanner scanner=new scanner (system.in; 布尔环=真; while(loop ) system.out.println ) (s ) show ) :显示队列); system.out.println(e(exit ) :程序结束); 将数据添加到system.out.println(a(add ) :队列); system.out.println (从' g (get ) :队列中检索数据); system.out.println (显示' h (head ) :队列标头元素); key=scanner.next ().charAt(0) ) 0; sitch(key ) ) { case 's': queue.show; 布雷克; 请输入case ' a ' : system.out.println (' : '; int value=scanner.nextInt (; queue.add queue (值; 布雷克; case ' g ' : try { intvalue2=queue.get queue (; system.out.println(value2; }catch(exceptione ) { e.getMessage ); } break; case ' h ' : try { intvalue3=queue.getfirstqueue (; system.out.println(value3; }catch(exceptione ) { e.getMessage ); } break; case 'e': scanner.close (; loop=false; 布雷克; 默认: break; } } classarrayqueue { private int maxsize; //队列最大容量专用前端; //头指针私有内读;

//尾指针 private int[] arrQueue; //数组 public ArrayQueue(int arrMaxQueue){ maxsize = arrMaxQueue; arrQueue = new int[maxsize]; front = -1;//头指针一开始都指向队头元素的前面-1的位置 rear = -1;//尾指针一开始都指向队头元素的前面-1的位置 } public boolean isFull(){ return rear == maxsize-1; } public boolean isEmpty(){ return rear == front; } public void addQueue(int n){ if(isFull()){ System.out.println("队列已满"); return; } rear++; arrQueue[rear] = n; } public int getQueue(){ if (rear == front){ throw new RuntimeException("队列为空"); } front++; return arrQueue[front]; } //显示整个队列 public void show(){ if(rear == front){ System.out.println("队列为空"); } for (int i = 0; i < arrQueue.length; i++) { System.out.println(arrQueue[i]); } } //显示队列的头数据 public int getFirstQueue(){ if(rear == front){ System.out.println("队列为空"); } return arrQueue[front+1]; }} 2.循环队列 2.1循环队列的定义

  队列的头尾相接的顺序存储结构称为循环队列。

2.2循环队列的基本介绍

  从上图我们可以看出,如果进行一系列的入队出队的操作之后,我们可以发现下标为0和1的地方为空,如果再进行入队操作却会报队列已满。这种情况我们就可以成为假溢出。

  解决假溢出的办法就是后面满了,就从头开始,也就是头尾相接的循环,我们把队列的这种头尾相接的顺序存储结构称为循环队列。

2.3用数组模拟实现循环队列 2.3.1数组模拟循环队列的思路

  1)首先确定队列的front和rear指针,它们都指向了队列的头元素0。
  2)确定队列的有效个数 (rear+maxSize-front)%maxSize
  3)确定队列的判空条件 rear == front
  4)确定队列的已满的情况 (rear + 1) % maxSize == front

2.4 代码实现 package Queue队列;import java.util.Scanner;//使用数组模拟队列public class CircleQueue循环队列 { public static void main(String[] args) { CircleQueue queue = new CircleQueue(4); char key = ' '; Scanner scanner = new Scanner(System.in); boolean loop = true; while (loop){ System.out.println("s(show):显示队列"); System.out.println("e(exit):退出程序"); System.out.println("a(add):添加数据到队列"); System.out.println("g(get):从队列取出数据"); System.out.println("h(head):查看队列头元素"); key = scanner.next().charAt(0); switch (key){ case 's': queue.show(); break; case 'a': System.out.println("请输入: "); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': try { int value2 = queue.getQueue(); System.out.println(value2); }catch (Exception e){ e.getMessage(); } break; case 'h': try { int value3 = queue.getFirstQueue(); System.out.println(value3); }catch (Exception e){ e.getMessage(); } break; case 'e': scanner.close(); loop = false; break; default: break; } } }}class CircleQueue{ private int maxsize; //队列最大容量 private int front; //头指针 private int rear; //尾指针 private int[] arrQueue; //数组 public CircleQueue(int arrMaxQueue){ maxsize = arrMaxQueue; arrQueue = new int[maxsize]; front = 0;//头指针一开始都指向队头元素0的位置a rear = 0;//尾指针一开始都指向队头元素0的位置 } public boolean isFull(){ return (rear + 1) % maxsize == front; //循环队列判断队列是否已经满 (rear + 1) % maxsize == front } public boolean isEmpty(){ return rear == front; //循环队列判断队列是否已经空 rear == front } public void addQueue(int n){ if(isFull()){ System.out.println("队列已满"); return; } arrQueue[rear] = n; rear = (rear + 1) % maxsize; } public int getQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空"); } //需要分析front是指向队列的第一个元素 //1.先把front对应的值保存到一个临时变量 //2.将front后移,需要考虑取% //3.将临时变量的值返回 int value = arrQueue[front]; front = (front + 1) % maxsize; return value; } public int total(){ return (rear + maxsize - front) % maxsize; } //显示整个队列 public void show(){ if(isEmpty()){ System.out.println("队列为空"); } for (int i = front; i < front+total(); i++) { System.out.printf("arrQueue[%d]=%d\n",i%maxsize,arrQueue[i%maxsize]); } } //显示队列的头数据 public int getFirstQueue(){ if(rear == front){ System.out.println("队列为空"); } return arrQueue[front]; }}
简要叙述循环队列的数据结构,数据结构拓扑排序