(数据结构)利用 C语言实现顺序队列及链队列

顺序队列的实现：

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

#define MAXSIZE 100 // 队列的最大长度

typedef struct{
    int data[MAXSIZE];
    int front; // 队头指针，指向队头元素
    int rear;  // 队尾指针，指向队尾元素的后一个位置
}SqQueue;

// 初始化队列
void InitQueue(SqQueue *Q){
    Q->front = 0;
    Q->rear = 0;
}

// 判断队列是否为空
int IsEmptyQueue(SqQueue Q){
    if(Q.front == Q.rear)
        return 1;
    else
        return 0;
}

// 判断队列是否已满
int IsFullQueue(SqQueue Q){
    if((Q.rear+1)%MAXSIZE == Q.front)
        return 1;
    else
        return 0;
}

// 入队
int EnQueue(SqQueue *Q, int data){
    if(IsFullQueue(*Q)){
        printf("Queue is full\n");
        return 0;
    }
    Q->data[Q->rear] = data;
    Q->rear = (Q->rear+1)%MAXSIZE;
    return 1;
}

// 出队
int DeQueue(SqQueue *Q, int *data){
    if(IsEmptyQueue(*Q)){
        printf("Queue is empty\n");
        return 0;
    }
    *data = Q->data[Q->front];
    Q->front = (Q->front+1)%MAXSIZE;
    return 1;
}

// 输出队列
void PrintQueue(SqQueue Q){
    if(IsEmptyQueue(Q)){
        printf("Queue is empty\n");
        return;
    }
    int i = Q.front;
    while(i != Q.rear){
        printf("%d ", Q.data[i]);
        i = (i+1)%MAXSIZE;
    }
    printf("\n");
}

int main(){
    SqQueue Q;   // 声明一个队列
    InitQueue(&Q);  // 初始化队列
    int flag = 1, choice, data;
    while(flag){    // 循环操作
        printf("1. EnQueue\n");
        printf("2. DeQueue\n");
        printf("3. PrintQueue\n");
        printf("0. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        switch(choice){
            case 0:
                flag = 0;
                break;
            case 1:
                printf("Enter data to Enqueue: ");
                scanf("%d", &data);
                if(EnQueue(&Q, data))
                    printf("Enqueue %d successfully!\n", data);
                break;
            case 2:
                if(DeQueue(&Q, &data))
                    printf("Dequeue %d successfully!\n", data);
                break;
            case 3:
                PrintQueue(Q);
                break;
            default:
                printf("Invalid choice\n");
        }
    }
    return 0;
}

链队列的实现：

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

typedef struct Node{    // 链队列结点的定义
    int data;
    struct Node *next;
}Node, *pNode;

typedef struct{         // 链队列的定义
    pNode front;        // 队头指针
    pNode rear;         // 队尾指针
}LinkQueue;

// 初始化队列
void InitQueue(LinkQueue *Q){
    Q->front = Q->rear = (pNode)malloc(sizeof(Node));
    Q->front->next = NULL;
}

// 判断队列是否为空
int IsEmptyQueue(LinkQueue Q){
    if(Q.front == Q.rear)
        return 1;
    else
        return 0;
}

// 入队
void EnQueue(LinkQueue *Q, int data){
    pNode p;
    p = (pNode)malloc(sizeof(Node));
    p->data = data;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
}

// 出队
int DeQueue(LinkQueue *Q, int *data){
    if(IsEmptyQueue(*Q)){
        printf("Queue is empty\n");
        return 0;
    }
    pNode p = Q->front->next;
    *data = p->data;
    Q->front->next = p->next;
    if(Q->rear == p)    // 如果队列中只有一个元素
        Q->rear = Q->front;
    free(p);
    return 1;
}

// 输出队列
void PrintQueue(LinkQueue Q){
    if(IsEmptyQueue(Q)){
        printf("Queue is empty\n");
        return;
    }
    pNode p = Q.front->next;
    while(p){
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main(){
    LinkQueue Q;    // 声明一个队列
    InitQueue(&Q);  // 初始化队列
    int flag = 1, choice, data;
    while(flag){    // 循环操作
        printf("1. EnQueue\n");
        printf("2. DeQueue\n");
        printf("3. PrintQueue\n");
        printf("0. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);
        switch(choice){
            case 0:
                flag = 0;
                break;
            case 1:
                printf("Enter data to Enqueue: ");
                scanf("%d", &data);
                EnQueue(&Q, data);
                printf("Enqueue %d successfully!\n", data);
                break;
            case 2:
                if(DeQueue(&Q, &data))
                    printf("Dequeue %d successfully!\n", data);
                break;
            case 3:
                PrintQueue(Q);
                break;
            default:
                printf("Invalid choice\n");
        }
    }
    return 0;
}