C语言实现队列和栈

C语言中可以使用数组或链表来实现队列和栈。

1. 队列

使用数组实现队列，需要定义一个指向队列头的指针front和一个指向队列尾的指针rear，队列的长度为maxsize。具体实现如下：

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int front, rear;
} Queue;

void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

int isQueueFull(Queue *q) {
    return (q->rear + 1) % MAXSIZE == q->front;
}

int isQueueEmpty(Queue *q) {
    return q->front == q->rear;
}

void enqueue(Queue *q, int x) {
    if (isQueueFull(q)) {
        printf("Queue is full\n");
        return;
    }
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;
}

int dequeue(Queue *q) {
    if (isQueueEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int x = q->data[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    return x;
}

其中，initQueue函数用于初始化队列；isQueueFull函数和isQueueEmpty函数分别用于判断队列是否已满和是否为空；enqueue函数用于入队；dequeue函数用于出队。注意，在队列满或空时，需要对应处理。

使用链表实现队列，需要定义一个链表节点Node，以及一个指向队列头节点和队列尾节点的指针head和tail。具体实现如下：

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

typedef struct {
    Node *head, *tail;
} Queue;

void initQueue(Queue *q) {
    q->head = q->tail = NULL;
}

int isQueueEmpty(Queue *q) {
    return q->head == NULL;
}

void enqueue(Queue *q, int x) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = NULL;
    if (isQueueEmpty(q)) {
        q->head = q->tail = newNode;
    } else {
        q->tail->next = newNode;
        q->tail = newNode;
    }
}

int dequeue(Queue *q) {
    if (isQueueEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int x = q->head->data;
    Node *temp = q->head;
    q->head = q->head->next;
    if (q->head == NULL) {
        q->tail = NULL;
    }
    free(temp);
    return x;
}

其中，initQueue函数用于初始化队列；isQueueEmpty函数用于判断队列是否为空；enqueue函数用于入队；dequeue函数用于出队。注意，在队列为空时，需要对应处理。

2. 栈

使用数组实现栈，需要定义一个指向栈顶的指针top，栈的长度为maxsize。具体实现如下：

#define MAXSIZE 100
typedef struct {
    int data[MAXSIZE];
    int top;
} Stack;

void initStack(Stack *s) {
    s->top = -1;
}

int isStackFull(Stack *s) {
    return s->top == MAXSIZE - 1;
}

int isStackEmpty(Stack *s) {
    return s->top == -1;
}

void push(Stack *s, int x) {
    if (isStackFull(s)) {
        printf("Stack is full\n");
        return;
    }
    s->top++;
    s->data[s->top] = x;
}

int pop(Stack *s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    int x = s->data[s->top];
    s->top--;
    return x;
}

其中，initStack函数用于初始化栈；isStackFull函数和isStackEmpty函数分别用于判断栈是否已满和是否为空；push函数用于入栈；pop函数用于出栈。注意，在栈满或空时，需要对应处理。

使用链表实现栈，需要定义一个链表节点Node，以及一个指向栈顶节点的指针top。具体实现如下：

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

typedef struct {
    Node *top;
} Stack;

void initStack(Stack *s) {
    s->top = NULL;
}

int isStackEmpty(Stack *s) {
    return s->top == NULL;
}

void push(Stack *s, int x) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = x;
    newNode->next = s->top;
    s->top = newNode;
}

int pop(Stack *s) {
    if (isStackEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    }
    int x = s->top->data;
    Node *temp = s->top;
    s->top = s->top->next;
    free(temp);
    return x;
}

其中，initStack函数用于初始化栈；isStackEmpty函数用于判断栈是否为空；push函数用于入栈；pop函数用于出栈。注意，在栈为空时，需要对应处理。