在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)。