实现链队列的基本操作

Question

实现链队列的基本操作。

【输入形式】

输入若干个整数（以空格分隔），其中0表示做出队操作，不为0的整数为入队元素。

【输出形式】

依次输出队列的全部元素，若队列为空，则输出“empty”

【样例输入1】

1 2 3 4 5 6
【样例输出1】

1 2 3 4 5 6

Answer 1

你题目的解答代码如下：（如有帮助，望采纳！谢谢! 点击我这个回答右上方的【采纳】按钮）

#include <stdio.h>
#include <stdlib.h>

typedef struct node * PNode; /*定义队列的每个节点的类型*/
typedef struct node {
    int data;//每个节点中存放的数据
    PNode next;//下一节点
}Node;

typedef struct queue {
    PNode head;//队头
    PNode tail;//队尾
    int Length;//队列长度
}Queue;

Queue *GetQueue() { // 返回创建的新空队列
    Queue *queue = (Queue *)malloc(sizeof(Queue));  //创建存放队列的空间，字节大小为Queue，字针（32位系统）是4字节，int是4字节，那么node结构体就是8字节，queue就是8+8+4=20字节的
    queue->head = (Node *)malloc(sizeof(Node));  //创建头指针结点的存放空间
    queue->head->next = NULL;   //头指针指向空指针
    queue->tail = queue->head;  //令队列的尾指针为队列的头指针，这是为了在第一个元素入队时，头指针的字针能够指向第一个元素。
    queue->Length = 0;
    return queue;
}

void EnQueue(Queue *Q,int x) { // 将x送入队，每次都是在队尾加入新结点
    PNode newnode = (Node *)malloc(sizeof(Node));//产生新的结点
    newnode->data = x;  //新的结点数据域存放输入的x
    ++Q->Length;   //队列长度加一
    newnode->next = NULL;   //新产生的结点指向空指针
    Q->tail->next = newnode;  // 队尾指针指向新结点，当第一个元素x进来的时候，队尾指针相当于队头指针，那么也就是队头指针指向第一个进来的元素
    Q->tail = newnode; //接着就是队尾变成了刚刚进来的新结点，以此类推，下一个进来的新结点（假设为y）便是头结点指向x，x指向y，y指向nul
}

int notEmpty(Queue *Q) {
    return (Q->Length > 0);
}

int DeQueue(Queue *Q,int *x) { // 将x送出队
    PNode p;            //定义结点指针p
    if(notEmpty(Q)) {
        p = Q->head->next;   //  p的地址是头指针所指的下一个地址，也就是第一个元素的地址
        *x = p->data;   //访问p的地址，取该地址的数据域的数据
        Q->head->next = p->next;  //此时，将头指针指向p的下一个地址，即第二个元素。下一次调用函数便是p值为第二个（y），以此类推第三个、第四个。。。直到尾指针指向空指针结束
        --Q->Length;  //队列长度减一
        free(p);   //释放p的空间，此时p的地址也就是队列里面结点的地址
        return 1;
    }
    return 0;
}

int GetLength(Queue *Q) { // 获取队列长度
    return Q->Length;
}

int GetFirst(Queue *Q) { // 获取队头数据
    return Q->head->next->data;
}

int GetLast(Queue *Q) { // 获取队尾数据
    return Q->tail->data;
}

void ClearQueue(Queue *Q) {
    Q->tail = Q->head;
    Q->Length = 0;
}

void DestroyQueue(Queue *Q) {
    PNode q,p = Q->head;
    while(p) {
        q = p;
        p = q->next;
        free(q);
    }
    Q->head = Q->tail = NULL;
    free(Q);
    Q = NULL;
}

int main() {
    int i,x;
    Queue *Q = GetQueue();//定义一个新的队列
    while (scanf("%d",&x)!=EOF) {
        if (x==0)
            DeQueue(Q,&x);//出队列
        else
           EnQueue(Q,x);//x送进队列
    }
    if (notEmpty(Q))
    {
        while(notEmpty(Q)) {//判断没有空队列
            DeQueue(Q,&x);//出队列
            printf("%d ",x);
        }
    }
    else
        printf("empty");
    return 0;
}