队列的顺序存储结构

队列的顺序存储结构之循环队列

队列的定义： 只允许在一端进行操作，在另一端进行删除操作的线性表。

队列是一种先进先出的线性表，简称FIFO，允许插入的一端称为队尾，允许删除的一端称为队头。

 

1、队列的顺序存储结构存在缺陷

原因：

　　　　假设一个队列有n个元素，则顺序存储的队列需要建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即为对头。
　　　　所谓的入队，就是在队尾追加一个元素，不需要移动任何元素，所以时间复杂度为O(1).
　　　　队列的出队是在对头，即下标为0的位置，也就意味着，队列中的所有位置都得向前移动，以保证下标为0的位置，即对头不为空。此时时间复杂度为O(n)。

　　　　可是有时候想想，为什么出队列时一定要全部移动呢？如果不限制队列的元素一定要存储在数组的前n个单元，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置。

但如果不全部移动的话，又会引入新的问题？那就是数组的 “假溢出”

为了避免当只有一个元素时，对头和队尾重合使得处理变得麻烦，所以引入两个指针，front指针指向对头元素，rear指针指向队尾元素的下一个元素。这样当front等于rear时，不是队列中有一个元素，而是表示空队列。

　　　　假设数组的长度为5，空队列及初始状态如左图所示，front与rear指针都指向下标为0的位置。当队列中有4个元素时，front指针不变，rear指针指向下标为4的位置。

　　　　此时出队两个元素，则front指针指向下标为2的位置，rear不变。再入队一个元素，front指针不变，此时rear指针移动到数组之外，这就产生了 “假溢出” 现象。

为了解决这种假溢出的现象。我们引入了循环队列

2、循环队列的定义

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

为了解决假溢出的现象，就是当队列满了，我们再从头开始存数据，这是时候头尾已经相连了，就形成了循环队列。

继续刚才的例子，将rear指针指向下标为0的位置，就不会导致rear指针指向不明的问题。

接着入队两个元素，会发现rear指针与front重合了

此时问题又来了，刚才说了，当rear等于front时，表示是空队列，现在当队列满时，rear也等于front。那么如何判断队列到底是空的还是满的了？

我们有两个判断方法：

办法一是设置标志变量flag，当front = rear ,且flag =0 为队列空，当front =rear ，且flag =1 时队列满。

办法二是当队列为空时，条件是front = rear ,当队列满时，我们修改其条件，保留一个元素的空间，也是就是说，当队列满时，数组里面还有一个空闲的单元。

例如下图就表示了队列已经满了

就不能再插入元素了。

由于队列是循环队列，rear可能比front大，也可能比front小，所以假设队列的最大尺寸为QueueSize, 队列满的判断条件改为（rear + 1）%QueueSize = front. 队列的长度为（rear - front + QueueSize）% QueueSize.

循环队列的引入解决了数据移动的时间损耗，使得本来插入和删除是O(n)的时间复杂度变成了O(1).

以上的部分文字和图片Copy大佬：https://www.cnblogs.com/muzijie/p/5650187.html

 

循环队列的顺序存储结构定义如下

typedef struct{ int data[MAXSIZE];   //容量
    int front;          //前驱下标
    int real;           //后继下标
 }SqQueue;

初始化队列

/*初始化队列*/
void InitQueue(SqQueue* Q){ 3     Q->front=0; 4     Q->real=0;   //前驱和后继都指向0
}

求一个循环队列的长度

/*求一个循环队列的长度*/
int QueueLength(SqQueue Q){ 3 
    return (Q.real-Q.front+MAXSIZE)%MAXSIZE; 5 }

循环队列的入队操作

/*入队操作*/
int EnQueue(SqQueue* Q,int e){ 3     if(FullQueue(*Q)) 4         return 0; 5     Q->data[Q->rear]=e; 6     Q->rear = (Q->rear+1)%MAXSIZE;  //将rear指针向后移一位
    /*若到最后则转到数组头部*/    
}

循环队列的出队操作

/*出队操作*/
int DeQueue(SqQueue* Q){  3     int e;  4     if(Q->front ==Q->rear){  5         return 0;  6  }  7     e = Q->data[Q->front];  8     Q->front = (Q->front+1)%MAXSIZE;  9     return e; 10 }

其它操作的实现代码

#include <stdio.h>
#define MAXSIZE 20

typedef struct{  5     
    int data[MAXSIZE];   //容量
    int front;          //前驱下标
    int rear;           //后继下标

}SqQueue; 11 
/*初始化队列*/
void InitQueue(SqQueue* Q){ 14     Q->front=0; 15     Q->rear=0;   //前驱和后继都指向0
} 17 
/*求一个循环队列的长度*/
int QueueLength(SqQueue Q){ 20 
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; 22 } 23 
/*判断是否队满*/
int FullQueue(SqQueue Q){ 26     if(QueueLength(Q) ==MAXSIZE) 27         return 1; 28     else 
        return 0; 30 } 31 
/*入队操作*/
int EnQueue(SqQueue* Q,int e){ 34     if(FullQueue(*Q)) 35         return 0; 36     Q->data[Q->rear]=e; 37     Q->rear = (Q->rear+1)%MAXSIZE;  //将rear指针向后移一位
    /*若到最后则转到数组头部*/    
} 40 
/*出队操作*/
int DeQueue(SqQueue* Q){ 43     int e; 44     if(Q->front ==Q->rear){ 45         return 0; 46  } 47     e = Q->data[Q->front]; 48     Q->front = (Q->front+1)%MAXSIZE; 49     return e; 50 } 51 
int main(){ 53 
 SqQueue s; 55     InitQueue(&s); 56     for(int i=0;i<10;i++){ 57         EnQueue(&s,i); 58  } 59 
    for( i=0;i<10;i++){ 61         printf("出队元素：%d\n",DeQueue(&s)); 62  } 63 
    return 0; 65 }

 

附上Java代码实现

 

package queue;

public class Queue {

    int data[] = new int[20];
    int rear; // 后下标
    int front; // 前下标

    /**
     * 初始化队列
     */
    public void initQueue(Queue Q) {
        Q.front = 0;
        Q.rear = 0;
    }

    /**
     * 入队操作
     */
    public int enQueue(Queue Q, int e) {
        if (fullQueue(Q) == 1)
            return 0;

        Q.data[Q.rear] = e;
        Q.rear = (Q.rear + 1) % 20;

        return e;
    }

    /**
     * 出队操作
     */
    public int deQueue(Queue Q) {
        int e;
        if (queueLength(Q) == 0)
            return 0;

        e = Q.data[Q.front];
        Q.front = (Q.front + 1) % 20;
        return e;
    }

    /**
     * 判断是否队满
     */
    public int fullQueue(Queue Q) {
        if ((Q.rear + 1) % 20 == Q.front) // 判断是否为队满
            return 1;
        else
            return 0;
    }

    /**
     * 返回队长度
     */
    public int queueLength(Queue Q) {

        return (Q.rear - Q.front + 20) % 20;
    }

    /**
     * 判断是否队空
     */
    public boolean elmptyQueue(Queue Q) {
        if (Q.front == Q.rear)
            return true;
        return false;
    }
}

 

package queue;

public class Test {

    public static void main(String[] args) {

        Queue queue = new Queue();
        System.out.println("初始化队...");
        queue.initQueue(queue);
        System.out.println("入队操作...");
        for (int i = 0; i < 10; i++)
            System.out.print(queue.enQueue(queue, i) + " ");

        System.out.println("");
        System.out.println("判断对是否为空..." + queue.elmptyQueue(queue));

        System.out.println("出队操作...");
        for (int j = 0; j < 10; j++)
            System.out.print(queue.deQueue(queue) + " ");

        System.out.println("");
        System.out.println("判断对是否为空..." + queue.elmptyQueue(queue));
    }

}

 

 

完毕 - -