队列--数组AND链表的实现

一、数组实现：

用数组模拟队列给定一个数组长度，为队列长度

用下标做指定头尾位置，pri为头，bak为尾

为了不浪费空间长度：

pri=bak时队列为空，即：

                                                                 

（bak+1）% MAXSIZE  = pri  时：             队列为满，即：

                                             

bak指向的位置始终为空。当然也可以指向最后一个元素，但是我习惯于这种

#include<cstdio>
#include<iostream>
#include<cstdlib>

#define MAXSIZE 10000

using namespace std;


typedef struct Que_line{
    int *Element;
    int pri;
    int bak;
}Que_line;

void Creat_Que(Que_line* &Que)
{
    Que = (Que_line *)malloc(sizeof(Que_line));
    Que->Element = (int *)malloc(MAXSIZE * sizeof(int));
    Que->pri = Que->bak = 0;
    return ;
}

void In_Que(Que_line* Que, int e)
{
    if((Que->bak+1) % MAXSIZE == Que->pri)
    {
        printf("队列已经满了\n");
        return ;
    }

    Que->Element[Que->bak] = e;
    Que->bak = (Que->bak+1) % MAXSIZE;
    return ;
}

void Out_Que(Que_line* Que, int &e)
{
    if(Que->pri == Que->bak)
    {
        printf("队列已经为空\n");
        return ;
    }

    e = Que->Element[Que->pri];
    Que->pri = (Que->pri+1) % MAXSIZE;
    return ;
}

int main()
{
    int x, n;
    Que_line *Que;
    Creat_Que(Que);

    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        In_Que(Que, x);
    }

    for(int i = 0; i < n; i++)
    {
        Out_Que(Que, x);
        printf("%d%c", x, i == n-1 ? '\n' : ' ');
    }

    if(Que->pri == Que->bak)
        printf("队列为空\n");
    else
        printf("出错\n");

    return 0;
}

二、链表实现：

链表结构：

typedef struct Que_link{
    int data;
    struct Que_link *next;
}Que_link, *Que_link_idx;

自定义链表头部：

typedef struct Que_link_h{
    Que_link_idx pri;    ///指向链表的头节点
    Que_link_idx bak;    ///指向链表的尾节点
}Que_link_h;

插入时在尾节点处插入，删除时在头结点处删除

插入时：

如果插入的是第一个元素则应使   自定义的头部的头指针和尾指针都指向第一个元素；

如果不是就将这个元素接到链表尾部，并它的next=NULL（表示尾部），而且要 自定义的链表头部  尾指针后移一下。

删除时：

如果删除的时最后一个元素，则应该让   自定义的头指针和尾指针  指向尾部，表示队列为为空。

如果不是，就让头指针后移一下就ok了，    记得将删除的节点free()哦，节省空间。

接下来看完整代码：

#include<cstdio>
#include<iostream>
#include<cstdlib>

using namespace std;

typedef struct Que_link{
    int data;
    struct Que_link *next;
}Que_link, *Que_link_idx;

typedef struct Que_link_h{
    Que_link_idx pri;
    Que_link_idx bak;
}Que_link_h;

void Creat_Que_link(Que_link_h* &Que)
{
    Que = (Que_link_h *)malloc(sizeof(Que_link_h));
    Que->pri = Que->bak = NULL;
    return ;
}

void In_Que_link(Que_link_h* Que, int e)
{
    Que_link_idx p;
    p = (Que_link_idx)malloc(sizeof(Que_link));
    p->data = e;

    ///进入第一个元素与进入第i(i!=1)个元素操作不同：
    p->next = NULL;
    if(Que->bak == NULL)  ///进入第一个元素时首位指针都要指向该位置
        Que->bak = Que->pri = p;
    else                  ///进入第i(i!=1)个元素则需要先接到链上，然后为指针后移
    {
        Que->bak->next = p;
        Que->bak = p;
    }
    return ;
}
void Out_Que_link(Que_link_h* Que, int &e)
{
    if(Que->pri == NULL)
    {
        printf("队列已经为空\n");
        return ;
    }
///删除最后一个元素时与删除第i(i!=1)个元素不同
    Que_link_idx p; ///删除第i(i != 1)个元素只需要头指针后移
    p = (Que_link_idx)malloc(sizeof(Que_link));
    p = Que->pri;
    Que->pri = Que->pri->next;
    if(Que->bak == p)  ///删除最后一个元素还需要尾指针指空NULL
        Que->bak = NULL;
    e = p->data;
    free(p);
    return ;
}
int main()
{
    int n, x;
    Que_link_h* Que;
    Creat_Que_link(Que);


    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        In_Que_link(Que, x);
    }

    for(int i = 0; i < n; i++)
    {
        Out_Que_link(Que, x);
        printf("%d ", x);
    }
    printf("\n\n\n\n");

    if(Que->pri == NULL)
        printf("队列为空\n");
    else
        printf("操作出错\n");


    return 0;
}