数据结构--队列（FIFO）

港控/mmm° 2022-06-02 06:12 182阅读 0赞

*  c++中的STL是非常好用的。这里使用数组的形式或结构体的形式加深理解。
 *  首先，**介绍数组的形式**，，将“6 3 1 7 5 8 9 2 4”这 9个数分别写在 9张便签上模拟这样的规则，规则是这样的：首先将第 1个数删除，紧接着将第 2个数放到 这串数的末尾，再将第 3个数删除并将第 4个数放到这串数的末尾，再将第 5个数删除…… 直到剩下后一个数，将后一个数也删除。
 *  引入两个整型变量 head 和 tail。head 用来记录队列的队首（即第一位）， tail 用来记录队列的队尾（即后一位）的下一个位置。你可能会问：为什么 tail 不直接记 录队尾，却要记录队尾的下一个位置呢？这是因为当队列中只剩下一个元素时，队首和队尾重合会带来一些麻烦。我们这里规定队首和队尾重合时，队列为空。
 *  其次，**使用结构体的形式**，定义一个结构体类型。
    
    ![61531651.jpg][]
 *  代码：

#include<iostream>
    using namespace std;
    /*这是第一种用数组的形式；
    int main(){
        int p[102]={0,6,3,1,7,5,8,9,2,4},head,tail;
        int i;
         head=1;
         tail=10;
         while(head<tail){
            cout<<p[head]<<" ";
            head++;
            p[tail]=p[head];
            tail++;
            head++;
         }
         return 0;
    }
    */
    //以下是结构体类型写的：
    struct queue{
      int data[100];
      int head;
      int tail;
    };
    int main(){
        struct queue q;
         q.head=1;
         q.tail=1;
        for(int i=1;i<=9;i++){
            cin>>q.data[q.tail];
            q.tail++;
        }
        while(q.head<q.tail){
            cout<<q.data[q.head]<<" ";
            q.head++;
            q.data[q.tail]=q.data[q.head];
            q.tail++;
            q.head++;
        }
        return 0;
    }

[61531651.jpg]: http://oz3ijy2k5.bkt.clouddn.com/18-1-5/61531651.jpg