C语言数据结构队列实现-顺序队列

顺序队列，即采用顺序表模拟实现的队列结构。

我们知道，队列具有以下两个特点：
数据从队列的一端进，另一端出；
数据的入队和出队遵循"先进先出"的原则；

因此，只要使用顺序表按以上两个要求操作数据，即可实现顺序队列。首先来学习一种最简单的实现方法

顺序队列简单实现

由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求，我们还需要定义两个指针（top 和 rear）分别用于指向顺序队列中的队头元素和队尾元素，如图 1 所示：

由于顺序队列初始状态没有存储任何元素，因此 top 指针和 rear 指针重合，且由于顺序队列底层实现靠的是数组，因此 top 和 rear 实际上是两个变量，它的值分别是队头元素和队尾元素所在数组位置的下标。

在图 1 的基础上，当有数据元素进队列时，对应的实现操作是将其存储在指针 rear 指向的数组位置，然后 rear+1；当需要队头元素出队时，仅需做 top+1 操作。

例如，在图 1 基础上将 {1,2,3,4} 用顺序队列存储的实现操作如图 2 所示：


在图 2 基础上，顺序队列中数据出队列的实现过程如图 3 所示：

因此，使用顺序表实现顺序队列最简单方法的 C 语言实现代码为：

#include <stdlib.h>
#define MaxSize 10 
//顺序队列操作
int insertList(int * list, int head, int elem){
    list[head] = elem;
    head = head+1;
    return head;
}

int   outlist(int * list,int head){
    int data = list[head];
    printf("%d\n",data);
    head = head+1;
    return head;
}

void listprint(int * list, int tail){
    for(int i=0;i<tail;i++){
        printf("%d\n",list[i]);
    }
}

int main(){
    
    int head=0;
    int tail=0;
    int list[MaxSize];
    tail = insertList(list,tail,7);
    tail = insertList(list,tail,67);
    tail = insertList(list,tail,34);
    tail = insertList(list,tail,44);
    tail = insertList(list,tail,33);

    head = outlist(list,head);
    head = outlist(list,head);
    head = outlist(list,head);
    
    //listprint(list, tail);
    return(0);
}

有个问题是浪费空间所以考虑优化下如图：

#include <stdlib.h>
#define MaxSize 10 
int insertList(int * list, int head, int elem){
    int pos = head%MaxSize;//通过取余操作
    list[pos] = elem;
    return head+1;
}

int outlist(int * list,int head){
    int pos = head%MaxSize;
    int data = list[pos];
    printf("%d\n",data);
    return head+1;
}

// void listprint(int * list, int tail){
//     for(int i=0;i<tail;i++){
//         printf("%d\n",list[i]);
//     }
// }

int main(){
    
    int head=0;
    int tail=0;
    int list[MaxSize];
    tail = insertList(list,tail,7);
    tail = insertList(list,tail,67);
    tail = insertList(list,tail,34);
    tail = insertList(list,tail,44);
    tail = insertList(list,tail,33);
    
    
    head = outlist(list,head);
    head = outlist(list,head);
    head = outlist(list,head);
    
    //listprint(list, tail);
    return(0);
}