c语言列队怎样实现先进先出

在C语言中，实现队列的先进先出（FIFO）可以通过结构体、数组和链表三种数据结构来实现。这里我将分别介绍这三种方法：

使用结构体实现队列：

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

typedef struct {
    int *data;
    int front;
    int rear;
    int size;
    int capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->data = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

int isFull(Queue* queue) {
    return (queue->size == queue->capacity);
}

int isEmpty(Queue* queue) {
    return (queue->size == 0);
}

void enqueue(Queue* queue, int item) {
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->data[queue->rear] = item;
    queue->size = queue->size + 1;
}

int dequeue(Queue* queue) {
    if (isEmpty(queue))
        return -1;
    int item = queue->data[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

int main() {
    Queue* queue = createQueue(5);
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);
    enqueue(queue, 50);

    while (!isEmpty(queue)) {
        printf("%d ", dequeue(queue));
    }

    free(queue->data);
    free(queue);
    return 0;
}

使用数组实现队列：

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

typedef struct {
    int *array;
    int front;
    int rear;
    int size;
    int capacity;
} QueueArray;

QueueArray* createQueueArray(int capacity) {
    QueueArray* queue = (QueueArray*)malloc(sizeof(QueueArray));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

int isFull(QueueArray* queue) {
    return (queue->size == queue->capacity);
}

int isEmpty(QueueArray* queue) {
    return (queue->size == 0);
}

void enqueue(QueueArray* queue, int item) {
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
}

int dequeue(QueueArray* queue) {
    if (isEmpty(queue))
        return -1;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

int main() {
    QueueArray* queue = createQueueArray(5);
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);
    enqueue(queue, 50);

    while (!isEmpty(queue)) {
        printf("%d ", dequeue(queue));
    }

    free(queue->array);
    free(queue);
    return 0;
}

使用链表实现队列：

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct Queue {
    Node* front;
    Node* rear;
    int size;
} QueueLinkedList;

QueueLinkedList* createQueue() {
    QueueLinkedList* queue = (QueueLinkedList*)malloc(sizeof(QueueLinkedList));
    queue->front = queue->rear = NULL;
    queue->size = 0;
    return queue;
}

void enqueue(QueueLinkedList* queue, int item) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = item;
    newNode->next = NULL;

    if (queue->rear == NULL) {
        queue->front = queue->rear = newNode;
        return;
    }

    queue->rear->next = newNode;
    queue->rear = newNode;
}

int dequeue(QueueLinkedList* queue) {
    if (queue->front == NULL)
        return -1;

    Node* temp = queue->front;
    int item = temp->data;
    queue->front = queue->front->next;

    if (queue->front == NULL)
        queue->rear = NULL;

    free(temp);
    queue->size = queue->size - 1;
    return item;
}

int main() {
    QueueLinkedList* queue = createQueue();
    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);
    enqueue(queue, 40);
    enqueue(queue, 50);

    while (!isEmpty(queue)) {
        printf("%d ", dequeue(queue));
    }

    return 0;
}

以上三种方法都可以实现队列的先进先出（FIFO）。

最新问答

相关标签