数据结构-顺序循环队列

 

文章目录

 

简介

顺序队列很简单,所以这里专门来实现顺序循环队列了,循环队列还是蛮有意思的,通过取模运算得到队列中的指定元素。顺序队列写法和顺序栈很相似这里就不实现了,这里就开始实现顺序循环队列!

Java 实现

逻辑思路

顺序队列和顺序栈很相似,都是设置了头结点和尾结点,并且在空间上是连续的,都是线性表,只不过栈是 FILO,队列是 FIFO 罢了,这里我使用两个下标来实现队头和队尾,下标会在数组上滑动,对头不一定一直指向 0 下标的元素,由于出队,对头甚至可以指向末尾下标的元素,我们通过取模的方式可以灵活的入队出队

算法图解

数据结构-顺序循环队列

代码实现

// 顺序循环队列
public class SequentialCircleQueue {
    private int[] arr;
    private int head;
    private int tail;
    private int count;
    private static final int DEFAULT_CAPACITY = 10;
    
    // 初始化
    public SequentialCircleQueue() {
        head = tail = 0;
        count = 0;
        arr = new int[DEFAULT_CAPACITY];
    }
    public SequentialCircleQueue(int capacity) {
        head = tail = 0;
        count = 0;
        arr = new int[capacity];
    }
    
    // 返回对头元素
    public getHead() throws Exception {
        if (count == 0)
            throw new Exception("队空!");
        return arr[head];
    }
    
    // 入队
    public void enqueue(int e) throws Exception {
        if (count == arr.length)
            throw new Exception("队满了!");
        arr[tail] = e;
        tail = (tail + 1) % arr.length;
        count++;
    }
    
    // 出队
    public int dequeue() throws Exception {
        if (head == tail)
            throw new Exception("队空!");
        int e = arr[head];
        head = (head + 1) % arr.length;
        count--;
        return e;
    }
    
    // 求队长
    public int getLength() {
        return count;
    }
}
写在后面

判定循环队列为空还是满,要么采用上面增加一个 count 变量来存储队列里有多少个元素,这样当 head == tail 的时候既可能是队空有可能是队满。如果我们不设置这个 count 呢,那我们就要牺牲一个数组空间,从而来判定队空队满,逻辑如下:

  • 当有元素要入队时,我们存入 tail 指向的空间,然后 tail 后移,假如一个数组有 5 个数,现在 head 在 0 位,存了数,tail 现在已经移动到 4 位置,tail 当前是空的,如果再存一个,那 tail 就会到 head 处了,这样队空和队满又都是 head == tail,这样就没法判定队空队满,所以我们决定用数组牺牲一个空间的方式来判定队空队满,也就是当 tail 在 4 的地方,就可以判定为队满了,怎么判定呢?只要(tail+1)%arr.length==head即可表示为队满,具象化就是 tail 后面跟着就是 head 的时候表示队满
  • 同上,表示队空直接head==tail
  • tail 的下一个位置是(tail+1)%arr.length
  • head 的下一个位置是(head+1)%arr.length

 

上一篇:c语言学习4


下一篇:第五天