devbox
你好赵伟
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

用数组和链表来模拟队列结构_c++ 用链表模拟队列和用数组模拟队列

作者：你好赵伟 | 2024-03-25 03:21:01

赞

踩

c++ 用链表模拟队列和用数组模拟队列

1.队列

      1.队列是一个有序的列表，可以用数组或者链表来实现。

       2. 队列存储数据的原则是：先进先出。

     

  2. 数组模拟队列的思路

      1. 队列本身就是一个有序的列表，如果要使用数组的结构来储存队列的数据。就要有以下声明：

             maxSize 表示队列的最大容量。  

       2.  队列的输出输入分别从队列的前后端处理，定义队列的前端下标为front ，队列的下标为rear。

            front会随着队列的输出而改变，rear会随队列的输入改变。 

      3. 当数据存入队列时，成为“add"，add的处理步骤如下：

                 第一：当队列为空时，即front=rear， 将尾指针向后移动：rear+1。

                第二：如果尾指针rear小于队列的最大下标maxSize-1,将数据存入到到rear所值的元素数组中，当rear=maxSize-1，

                            队列满了，无法存入数据。

3. 代码实现

 

  1. public class ArryQueue {
  2.     //使用数组模拟队列
  3.     private int maxSize;//表示队列的最大容量
  4.     private int front;//队列的头
  5.     private int rear;//队列的尾
  6.     private int[] arr;//该数组用来存放数据，模拟队列
  7.  
  8.     //创建队列的构造器
  9.     public ArryQueue(int arrMaxSize){
  10.         maxSize=arrMaxSize;
  11.         arr=new int[maxSize];
  12.         front=-1;//指向队列头部，-1是指向头部的前一个位置，看图
  13.         rear=-1;//指定队列尾，指向队列的尾的数据（就是队列的最后一个数据）
  14.     }
  15.     //判断队列是否满了
  16.     public boolean isFull(){
  17.         return rear==maxSize-1;
  18.     }
  19.     //判断队列是否为空
  20.     public boolean isEmpty(){
  21.         return rear==front;
  22.     }
  23.     //将数据插入到队列中
  24.     public void addQueue(int n){
  25.         if(isFull()){
  26.             System.out.println("队列满了，不能加入数据");
  27.             return;
  28.         }
  29.         rear++;//让rear向后移动
  30.         arr[rear]=n;
  31.     }
  32.     //获取队列中的数据
  33.     public int getQueue(){
  34.         if(isEmpty()){
  35.             //通过抛出异常
  36.             throw new RuntimeException("队列为空，不能取出数据");
  37.         }
  38.         front++;//让front后移
  39.         return arr[front];
  40.     }
  41.     //显示队列中的所有元素
  42.     public void showQueu(){
  43.         //遍历
  44.         if(isEmpty()){
  45.             System.out.println("队列空的，没有数据");
  46.             return;
  47.         }
  48.         for (int i = 0; i < arr.length; i++) {
  49.             System.out.printf("arr[%d]=%d\n",i,arr[i]);
  50.         }
  51.     }
  52.     //显示队列的头数据，不是去除数据
  53.     public int headQueu(){
  54.         //判断
  55.         if(isEmpty()){
  56.             throw new RuntimeException("队列为空，不能取出数据");
  57.         }
  58.         return arr[front+1];
  59.     }
  60.  
  61.  
  62.     //测试
  63.     public static void main(String[] args) {
  64.         //创建一个队列
  65.         ArryQueue queue=new ArryQueue(3);
  66.         char key=' ';//接受用户的输入
  67.         Scanner scanner=new Scanner(System.in);
  68.         boolean loop=true;
  69.         //输出一个菜单
  70.         while(loop){
  71.             System.out.println("s(show):显示队列");
  72.             System.out.println("e(exit):退出队列");
  73.             System.out.println("a(add):添加数据到队列");
  74.             System.out.println("g(get):从队列中去除数据");
  75.             System.out.println("h(head):查看队列头的数据");
  76.             key=scanner.next().charAt(0);//接受一个字符
  77.             switch (key){
  78.                 case 's':
  79.                     queue.showQueu();
  80.                     break;
  81.                 case 'a':
  82.                     System.out.println("输入一个数");
  83.                     int value=scanner.nextInt();
  84.                     queue.addQueue(value);
  85.                     break;
  86.                 case 'g':
  87.                     try {
  88.                         int queue1 = queue.getQueue();
  89.                         System.out.printf("取出的数据为%d\n",queue1);
  90.                     }catch (Exception e){
  91.                         System.out.println(e.getMessage());
  92.                     }
  93.                     break;
  94.                 case 'h':
  95.                     try {
  96.                         int queue2 = queue.headQueu();
  97.                         System.out.printf("队列的头元素的数据为%d\n",queue2);
  98.                     }catch (Exception e){
  99.                         System.out.println(e.getMessage());
  100.                     }
  101.                     break;
  102.                 case 'e':
  103.                     //退出
  104.                     scanner.close();
  105.                     loop=false;
  106.                     break;
  107.                 default:
  108.                     break;
  109.             }
  110.         }
  111.         System.out.println("程序退出");
  112.     }
  113. }

  4. 问题分析：

         现在的队列只能使用一次，就不能在重复使用，达不到复用的效果。

        我们可以通过使用算法优化，改进成一个环形队列。

 

5. 数组模拟环形队列

      对上述代码进行优化，充分使用数组，因此可以将数组看成环形的。

 

6. 分析：

             1.  调整front的含义，front指向队列的第一个元素，arr [front] =第一个元素。此时front的初始值为0。

             2. 调整real的含义，rear指向队列的最后一个元素的后一个位置（倒数第二个元素），因为我们想留出一个空间作为约                      定。 rear的初始值为0.

             3. 队列满的条件：  （rear+1）%maxSize= front 。

             4. 队列空的条件：  rear == front 。

             5. 队列有效数据的个数    （real + maxSize - front ）% maxSize

7 代码实现

  1. public class CirleQueueDemo {
  2.     //使用数组模拟环形队列
  3.     private int maxSize;//表示队列的最大容量
  4.     private int front;//队列的头，指向队列的头
  5.     private int rear;//队列的尾，指向队列的最后一个元素的后一个位置，希望留出一个空间作为约定
  6.     private int[] arr;//该数组用来存放数据，模拟环形队列
  7.  
  8.     //创建队列的构造器
  9.     public CirleQueueDemo(int arrMaxSize){
  10.         maxSize=arrMaxSize;
  11.         arr=new int[maxSize];
  12.         //front=0;//指向队列头部，
  13.         //rear=0;//指定队列尾，
  14.     }
  15.     //判断队列是否满了
  16.     public boolean isFull(){
  17.         return (rear+1)%maxSize==front;
  18.     }
  19.     //判断队列是否为空
  20.     public boolean isEmpty(){
  21.         return rear==front;
  22.     }
  23.     //将数据插入到队列中
  24.     public void addQueue(int n){
  25.         if(isFull()){
  26.             System.out.println("队列满了，不能加入数据");
  27.             return;
  28.         }
  29.         arr[rear]=n;
  30.         //将rear后移，这里必须考虑取模
  31.         rear=(rear+1)%maxSize;
  32.     }
  33.     //获取队列中的数据
  34.     public int getQueue(){
  35.         if(isEmpty()){
  36.             //通过抛出异常
  37.             throw new RuntimeException("队列为空，不能取出数据");
  38.         }
  39.         //1.先把元素取出来，存储到临时变量中
  40.         int v=arr[front];
  41.         //2 front后移，这时需要考虑取模
  42.         front=(front+1)%maxSize;
  43.         //3 将保存的变量返回
  44.         return v;
  45.     }
  46.     //显示队列中的所有元素
  47.     public void showQueu(){
  48.         //遍历
  49.         if(isEmpty()){
  50.             System.out.println("队列空的，没有数据");
  51.             return;
  52.         }
  53.         for (int i=front; i < front+size(); i++) {
  54.             System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);
  55.         }
  56.     }
  57.     //得到当前队列中的有效数据的个数
  58.     public int size(){
  59.         return (rear+maxSize-front)%maxSize;
  60.     }
  61.     //显示队列的头数据，不是去除数据
  62.     public int headQueu(){
  63.         //判断
  64.         if(isEmpty()){
  65.             throw new RuntimeException("队列为空，不能取出数据");
  66.         }
  67.         return arr[front];
  68.     }
  69.  
  70.  
  71.     //测试
  72.     public static void main(String[] args) {
  73.         //创建一个队列
  74.         CirleQueueDemo queue=new CirleQueueDemo(4);//设置为4，队列中的有效数据最大为3，留出了一个约定孔空间
  75.         char key=' ';//接受用户的输入
  76.         Scanner scanner=new Scanner(System.in);
  77.         boolean loop=true;
  78.         //输出一个菜单
  79.         while(loop){
  80.             System.out.println("s(show):显示队列");
  81.             System.out.println("e(exit):退出队列");
  82.             System.out.println("a(add):添加数据到队列");
  83.             System.out.println("g(get):从队列中去除数据");
  84.             System.out.println("h(head):查看队列头的数据");
  85.             key=scanner.next().charAt(0);//接受一个字符
  86.             switch (key){
  87.                 case 's':
  88.                     queue.showQueu();
  89.                     break;
  90.                 case 'a':
  91.                     System.out.println("输入一个数");
  92.                     int value=scanner.nextInt();
  93.                     queue.addQueue(value);
  94.                     break;
  95.                 case 'g':
  96.                     try {
  97.                         int queue1 = queue.getQueue();
  98.                         System.out.printf("取出的数据为%d\n",queue1);
  99.                     }catch (Exception e){
  100.                         System.out.println(e.getMessage());
  101.                     }
  102.                     break;
  103.                 case 'h':
  104.                     try {
  105.                         int queue2 = queue.headQueu();
  106.                         System.out.printf("队列的头元素的数据为%d\n",queue2);
  107.                     }catch (Exception e){
  108.                         System.out.println(e.getMessage());
  109.                     }
  110.                     break;
  111.                 case 'e':
  112.                     //退出
  113.                     scanner.close();
  114.                     loop=false;
  115.                     break;
  116.                 default:
  117.                     break;
  118.             }
  119.         }
  120.         System.out.println("程序退出");
  121.     }

           

数组模拟队列2：

  

  1. package Queue.VirtulQueue;
  2.  
  3. import java.util.ArrayList;
  4.  
  5. public class ArrayQueuedemo {
  6.     public static void main(String[] args) {
  7.         ArrayQueue arrayQueue=new ArrayQueue<Integer>();
  8.         arrayQueue.inQueue(1);
  9.         arrayQueue.inQueue(2);
  10.         arrayQueue.inQueue(3);
  11.         arrayQueue.inQueue(4);
  12.         arrayQueue.inQueue(5);
  13.         System.out.println("队中的元素个数"+arrayQueue.size());
  14.         System.out.println("队中的首元素"+arrayQueue.firstQueue());
  15.         System.out.println("队中的尾元素"+arrayQueue.lastQueue());
  16.         arrayQueue.outQueue();
  17.         arrayQueue.outQueue();
  18.         System.out.println("队中的元素个数"+arrayQueue.size());
  19.         System.out.println("队中的首元素"+arrayQueue.firstQueue());
  20.         System.out.println("队中的尾元素"+arrayQueue.lastQueue());
  21.     }
  22. }
  23. class ArrayQueue<T>{
  24.     private ArrayList<T> array=new ArrayList<T>();//成员变量 array 来存储元素怒
  25.     private int front;//成员变量，指向队列的首位置
  26.     private int real;//成员变量，指向队列尾元素的下一个位置。
  27.  
  28.     public ArrayQueue() {
  29.         front=0;
  30.         real=0;
  31.     }
  32.     //判断队列是否为空
  33.     Boolean Empty(){
  34.         return front==real;
  35.     }
  36.     //入队
  37.     void inQueue(T item){
  38.         array.add(item);
  39.         real++;
  40.     }
  41.     //查看队列的大小
  42.     int size(){
  43.         return real-front;
  44.     }
  45.     //查看队列的首元素
  46.     T firstQueue(){
  47.         if (Empty()){
  48.             return null;
  49.         }
  50.         return array.get(front);
  51.     }
  52.     //查看队列的尾元素
  53.     T lastQueue(){
  54.         if (Empty()){
  55.             return null;
  56.         }
  57.         return array.get(real-1);
  58.     }
  59.     //出队
  60.     void outQueue(){
  61.         if (real>front){
  62.             front++;
  63.         }else {
  64.             System.out.println("队列为空");
  65.         }
  66.  
  67.     }
  68. }

链表模拟队列

  1. package Queue.VirtulQueue;
  2.  
  3. public class ListQueue {
  4.     public static void main(String[] args) {
  5.         Queue<Integer> queue=new Queue<Integer>();
  6.         queue.inQueue(1);
  7.         queue.inQueue(2);
  8.         queue.inQueue(3);
  9.         queue.inQueue(4);
  10.         queue.inQueue(5);
  11.         System.out.println("队列的大小"+queue.size());
  12.         System.out.println("队列的首元素"+queue.fqueue());
  13.         System.out.println("队列的尾元素"+queue.lqueue());
  14.         queue.outQueue();
  15.         System.out.println("队列的大小"+queue.size());
  16.         System.out.println("队列的首元素"+queue.fqueue());
  17.         System.out.println("队列的尾元素"+queue.lqueue());
  18.     }
  19. }
  20. class Queue<T>{
  21.     private LNode<T> head;//定义链表的头结点，指向队列的头
  22.     private LNode<T> end;//定义链表的尾结点，指向队列的尾
  23.  
  24.     //构造函数，一开始初始化队列为空
  25.     public Queue() {
  26.         head=end=null;
  27.     }
  28.  
  29.     //队列是否为空
  30.     Boolean Empty(){
  31.         return head==null;
  32.     }
  33.  
  34.     //入队
  35.     void inQueue(T item){
  36.         LNode<T> tmp=new LNode<>();
  37.         tmp.data=item;
  38.         tmp.next=null;
  39.         if (head==null){
  40.             head=end=tmp;
  41.         }else {
  42.             end.next=tmp;
  43.             end=tmp;
  44.         }
  45.  
  46.     }
  47.     //队列元素的个数
  48.     int size(){
  49.         int i=0;
  50.         LNode<T> tmp=head;
  51.         while (tmp!=null){
  52.             tmp=tmp.next;
  53.             i++;
  54.         }
  55.         return i;
  56.     }
  57.     //出队
  58.     void outQueue(){
  59.         if (Empty()){
  60.             System.out.println("队列为空");
  61.         }
  62.         head=head.next;
  63.         if (head==null){
  64.             end=null;
  65.         }
  66.     }
  67.     //队列的首元素
  68.     T fqueue(){
  69.         if (Empty()){
  70.             System.out.println("队列为空");
  71.             return null;
  72.         }
  73.         return head.data;
  74.     }
  75.     //队列的尾
  76.     T lqueue(){
  77.         if (end==null){
  78.             System.out.println("队列为空");
  79.             return null;
  80.         }
  81.         return end.data;
  82.     }
  83. }
  84.  
  85. class LNode<T>{
  86.     T data;
  87.     LNode<T> next;
  88. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/306636
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号