溫馨提示×

c語言列隊(duì)怎樣實(shí)現(xiàn)先進(jìn)先出

小樊
81
2024-10-16 22:45:38
欄目: 編程語言

在C語言中，實(shí)現(xiàn)隊(duì)列的先進(jìn)先出（FIFO）可以通過結(jié)構(gòu)體、數(shù)組和鏈表三種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)。這里我將分別介紹這三種方法：

  1. 使用結(jié)構(gòu)體實(shí)現(xiàn)隊(duì)列：
#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;
}
  1. 使用數(shù)組實(shí)現(xiàn)隊(duì)列：
#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;
}
  1. 使用鏈表實(shí)現(xiàn)隊(duì)列：
#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;
}

以上三種方法都可以實(shí)現(xiàn)隊(duì)列的先進(jìn)先出（FIFO）。

0 踩