用java、cpp两种语言实现顺序循环队列

矫情吗；* 2023-07-24 11:33 87阅读 0赞

引言：**队列是一种受限线性表**，在计算机世界中广泛应用，**他的特性是先进先出（FIFO）**，即和现实世界中的排队一样，符合先到先处理的原则，比如我们要用计算机和打印机打印文件时，计算机的数据处理能力显然比打印机快的多得多，为了避免计算机一下子把所有的数据都输出给打印机，造成打印机崩溃。我们需要有个缓冲区，先处理首先进来的数据，先打印出来，当这部分数据处理完后，让后续数据继续进入打印机，做到先来先打印。而队列便是实现这个方法的数据结构。**为使底层数组达到循环利用的目的，在这里使用循环数组。**  
**队列的特性：先进先出。元素从队尾进入，从队头出去，而且不允许遍历！**  
下面分别用java语言和Cpp实现顺序循环队列  
java实现：  
分析：**首先我们需要有一个底层循环数组，用来存放队列的元素，其次，为了实现对元素入队和出队的操作，我们需要引入两个指针：头指针和尾指针，插入元素时尾指针++，删除元素时头指针++，（这里用数组下标代替指针）当数组有剩余件且头或尾指针触底时则反弹。此外，我们还要引入一个变量来记录队列的长度，每次插入元素时判断队列是否出现索引越界，每次删除元素时判断是否为空队列。**

import java.util.Scanner;
    public class SeQueue{
        
    private int front;//头指针
    private int tail;//尾指针
    private int size; 
    private Object data[];//底层循环数组
    //有参构造，创建空队列
    public SeQueue(int cap){
         //从键盘读取数组长度
      data=new Object[cap];
     size=front=tail=0;//头尾指针都从数组零号索引开始，初始队列长度为0
    }
    public void push(Object e){
         //向队列中插入元素
        if(size==data.length)//如果数组中没有剩余空间，则抛出越界异常
    throw new ArrayIndexOutOfBoundsException("上溢！");
         data[tail]=e;//否则就将元素从队尾纳入进来
    /*接下来尾指针后移以确保下次插入元素时仍从队尾插入。但是要用问号冒号表达式判断指针后移是否越界，
    若越界，判断是否为假溢出，即数组低端仍有空间的现象，若是，则尾指针置零，将下一个元素插入数组0号位，
    否则正常尾指针++*/
     tail=tail+1==data.length?0:++tail;
    size++;//队列长度加1
    }
    public Object pop()//取出头元素并且删除
    {
           if(size==0)
    throw new ArrayIndexOutOfBoundsException("队列为空！")；
       Object temp=data[front];//创建临时变量接收队头
       front=front+1==data.length?0:++front;/*判断头指针移动后是否到达数组底部，若是，则循环加一置零
       反弹。若否则正常加一*/
    size--;
    return temp;
    }
    public Object top()//查看队头元素
    {
           if(size==0)
      throw new ArrayIndexOutOfBoundsException("队列为空！")；
       return data[front];
    }
    public Object rear()//查看队尾元素
    {
         if(size ==0)
     throw new ArrayIndexOutOfBoundsException("队列为空！")；
    return data[tail-1];/*由于每次插入新元素后尾指针都会加一，提前为指向下一个元素所在的位置，所以这里需
    要减一。*/
    }
    }
    
    //Cpp实现，原理相同
    ```cpp
    #include<stdc++.h>
    using namespace std;
    const int cap = 5;
    template<typename DataType>
    class SeQueue {
        
    private:
    int tail;
    int front;
    int size;
    int length;
    DataType data[cap];
    public:
    SeQueue();
    ~SeQueue();
    void push(DataType e);
    DataType top();
    DataType pop();
    DataType rear();
    
    
    };
    template<typename DataType>
    SeQueue<DataType>::SeQueue() {
        
    length = cap;
    tail = front = size = 0;
    
    }
    template <typename DataType>
    SeQueue<DataType>::~SeQueue() {
        
    
    }
    template <typename DataType>
    void SeQueue<DataType>::push(DataType e) {
        
    if (size == length)
    throw "上溢！";
    data[tail] = e;
    tail = tail + 1 == length ? 0 : ++tail;
    size++;
    
    }
    template<typename DataType>
    DataType SeQueue<DataType>::pop() {
        
    if (size == 0)
    throw"下溢！";
    DataType temp = data[front];
    front = front + 1 == length ? 0 : ++front;
    size--;
    return temp;
    
    }
    template<typename DataType>
    DataType SeQueue<DataType>::top() {
        
    if (size == 0)
    throw"下溢！";
    return data[front];
    }
    template<typename DataType>
    DataType SeQueue<DataType>::rear() {
        
    if(size==0)
    throw"下溢！";
    return data[--tail];
    }