数据结构（复习）关于队列，循环队列

数据结构之队列

 

队列特性：先进先出（FIFO)——先进队列的元素先出队列。来源于我们生活中的队列（先排队的先办完事）。

队列有下面几个操作：

• InitQueue（）　　 ——初始化队列
• EnQueue（）        ——进队列
• DeQueue（）        ——出队列
• IsQueueEmpty（）——判断队列是否为空
• IsQueueFull（）    ——判断队列是否已满

队列可以由数组和链表两种形式实现队列操作（c语言），下面仅以数组为例：

数组实现：

队列数据结构

typedef struct queue
{
        int queuesize;   //数组的大小
        int head, tail;  //队列的头和尾下标
        int *q;          //数组头指针
}Queue;

InitQueue（）　　 ——初始化队列

void InitQueue(Queue *q)
{
        q->queuesize = 8;
        q->q = (int *)malloc(sizeof(int) * q->queuesize); //分配内存
        q->tail    = 0;
        q->head = 0;
}

这样有个缺陷，空间利用率不高。采用循环队列：

EnQueue（）        ——进队列

void EnQueue(Queue *q, int key)
{
        int tail = (q->tail+1) % q->queuesize; //取余保证，当quil=queuesize-1时，再转回0
        if (tail == q->head)                   //此时队列没有空间
        {
            printf("the queue has been filled full!");
        }
        else
        {
            q->q[q->tail] = key;
            q->tail = tail;
        }
}

DeQueue（）  

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

代码论：

// // 关于数据结构的总结与复习  Coding
// //1.关于栈的实现    --.链表实现每一个都用链表实现
// //top是表头      bottom是表尾        每次只可以从表头(即top)删除和插入
// 形式如下
typedef struct Lnode
{
    int data;
    struct Lnode *next;
} Lnode, *Linklist;

typedef struct stack1{
    Linklist top;
    Linklist bottom;
} stack1, *stack;
// --------------------------------------------------------------------------------------------数组实现

typedef struct stack1
{
    int base;
    int top;
    int *elem;
} stack1, *stack;
// --------------------------------------------------------------------------------------
//关于队列的链表实现和循环队列
#include <cstdio>
#include <cstdlib>
#define error 0
#define ok 1
#define maxsize 100
//#define _OJ_

typedef struct Queue1
{
    int data;
    struct Queue1 *next;
} Queue1, *Queue;

typedef struct Queue2
{
    Queue front;
    Queue rear;
} Queue2, *Linkqueue;

Linkqueue
Init_Queue(void)
{
    Linkqueue q;
    q = (Linkqueue) malloc (sizeof(Queue2));
    q->front = q->rear = (Queue) malloc (sizeof(Queue1));
    q->front->next = NULL;
    return q;
}

void
EnQueue(Linkqueue q, int data)
{
    Queue p1;
    p1 = (Queue) malloc (sizeof(Queue1));
    p1->data = data;    p1->next = NULL;

    q->rear->next = p1;
    q->rear = p1;                     //队尾进行插入
}

int
DeQueue(Linkqueue q)
{
    if(q->rear == q->front) {
        printf("队列为空：
");    return error;
    }

    int e;
    Queue q1;
    q1 = q->front->next;       e = q1->data;
    q->front->next = q1->next;       //队头进行删除

    if(q1 == q->rear)    q->rear = q->front;  
      //当最后一个元素删除时我们看作rear已经没有了要重新赋值（即rear != front)
    free(q1);
    return e;
}

int
isempty(Linkqueue q)
{
    if(q->front == q->rear)
        return 1;
    else
        return 0;
}


int
Queue_length(Linkqueue q)
{
    int cnt = 0;
    while (isempty(q) != 1) {
        DeQueue(q);   cnt++;
    }
    return cnt;
}


int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE JUDGE
       freopen("input.txt", "r", stdin);
       //freopen("output.txt", "w", stdout);
#endif
    

    Linkqueue Q;

    Q = Init_Queue();

    printf("队列长度为：%d
", Queue_length(Q));

    EnQueue(Q, 1);

    EnQueue(Q, 2);    

    EnQueue(Q, 3);        

    printf("出队：%d
", DeQueue(Q));

    printf("队列长度为：%d
", Queue_length(Q));
    


    
    return 0;
}


// -------------------------------------------------------------------------------
// 关于队列的数组实现太浪费空间在此不给予实现也不推荐使用


//关于循环队列的实现：采用数组实现
#include <cstdio>
#include <cstdlib>
#define error 0
#define ok 1
#define maxsize 6
//#define _OJ_

typedef struct Queue1
{
    int *elem;
    int front;
    int rear;
} Queue1, *Linkqueue;

Linkqueue
Init_Queue(void)
{
   Linkqueue q;
  q = (Linkqueue) malloc (sizeof(Queue1));
   q->elem = (int*) malloc (sizeof(int));
   q->front = q->rear = 0;
   return q;
}

int
InQueue(Linkqueue Q, int data)
{
    if((Q->rear + 1) % maxsize == Q->front) {
        printf("队列已满：
");    return error;
    }
    Q->elem[Q->rear] = data;
    Q->rear = (Q->rear + 1) % maxsize;
}

int
DeQueue(Linkqueue Q)
{
    if (Q->front == Q->rear) {
           printf("队列为空：
");    return error;
    }
    int e;
    e = Q->elem[Q->front];
    Q->front = (Q->front + 1) % maxsize;
    return e;
}

int
Queue_Length(Linkqueue Q)
{
        return  (Q->rear - Q->front) % maxsize;
}


int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE JUDGE
       freopen("input.txt", "r", stdin);
       //freopen("output.txt", "w", stdout);
#endif
    

    Linkqueue q;

    q = Init_Queue();

    printf("循环队列的长度为：%d
", Queue_Length(q));

    InQueue(q, 1);

    InQueue(q, 2);

    InQueue(q, 3);

    InQueue(q, 4);

    InQueue(q, 5);

    // InQueue(q, 6);

    printf("循环队列的长度为：%d
", Queue_Length(q));

    DeQueue(q);

    printf("循环队列的长度为：%d
", Queue_Length(q));
    //队列最大可存储 maxsize - 1 个元素     分别为下标   0 ---- maxsize - 2;
    return 0;
}



//注意在循环队列中由于无法使用动态数组分配内存，那么就一定要设置一个最大队列长度
//如果无法估计队列长度                         那么则采用链表更好