C语言示例代码讲解栈与队列

下面是关于“C语言示例代码讲解栈与队列”的完整攻略：

一、栈和队列的概念

栈和队列都是常用的数据结构，他们都是线性结构，但是他们在元素的插入和删除的方法以及相应的顺序限制上是有区别的。栈是一种“后进先出”的数据结构，也就是最后放入的元素最先被取出；而队列是一种“先进先出”的数据结构，也就是最先放入的元素最先被取出。

二、栈和队列的实现

1. 栈的实现

栈可以用数组或链表来实现。这里我们以数组为例，在C语言中，可以通过以下方式定义一个栈：

#define MAX_SIZE 100    // 栈的最大容量为100

typedef struct {
    int data[MAX_SIZE];
    int top;    // 栈顶指针，-1表示空
} Stack;

在定义完栈之后，我们需要实现一些基本的栈操作，例如入栈、出栈、栈空、栈满等：

// 入栈
int push(Stack *s, int value) {
    if (s->top == MAX_SIZE - 1) {
        return 0;   // 表示栈满
    } else {
        s->top++;
        s->data[s->top] = value;
        return 1;
    }
}

// 出栈
int pop(Stack *s, int *value) {
    if (s->top == -1) {
        return 0;   // 表示栈空
    } else {
        *value = s->data[s->top];
        s->top--;
        return 1;
    }
}

// 判断栈空
int is_empty(Stack *s) {
    if (s->top == -1) {
        return 1;
    } else {
        return 0;
    }
}

// 判断栈满
int is_full(Stack *s) {
    if (s->top == MAX_SIZE - 1) {
        return 1;
    } else {
        return 0;
    }
}

2. 队列的实现

队列也可以用数组或链表来实现。这里我们以数组为例，在C语言中，可以通过以下方式定义一个队列：

#define MAX_SIZE 100    // 队列的最大容量为100

typedef struct {
    int data[MAX_SIZE];
    int front;  // 队头指针，-1表示空
    int rear;   // 队尾指针，-1表示空
} Queue;

在定义完队列之后，我们需要实现一些基本的队列操作，例如入队、出队、队空、队满等：

// 入队
int enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        return 0;   // 表示队满
    } else if (q->front == -1 && q->rear == -1) {
        q->front = q->rear = 0;
        q->data[q->rear] = value;
        return 1;
    } else {
        q->rear = (q->rear + 1) % MAX_SIZE;
        q->data[q->rear] = value;
        return 1;
    }
}

// 出队
int dequeue(Queue *q, int *value) {
    if (q->front == -1 && q->rear == -1) {
        return 0;   // 表示队空
    } else if (q->front == q->rear) {
        *value = q->data[q->front];
        q->front = q->rear = -1;
        return 1;
    } else {
        *value = q->data[q->front];
        q->front = (q->front + 1) % MAX_SIZE;
        return 1;
    }
}

// 判断队空
int is_empty(Queue *q) {
    if (q->front == -1 && q->rear == -1) {
        return 1;
    } else {
        return 0;
    }
}

// 判断队满
int is_full(Queue *q) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        return 1;
    } else {
        return 0;
    }
}

三、关于栈和队列的示例

1. 判断字符串是否为回文串

回文串是指从左到右和从右到左读起来都是一样的字符串。可以用栈来判断一个字符串是否为回文串。具体的做法是，先将字符串中的每个字符依次入栈，然后再依次出栈，如果出栈的字符和原字符串相同，说明这个字符串是回文串。

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 100

typedef struct {
    char data[MAX_SIZE];
    int top;
} Stack;

int push(Stack *s, char c) {
    if (s->top == MAX_SIZE - 1) {
        return 0;
    } else {
        s->top++;
        s->data[s->top] = c;
        return 1;
    }
}

int pop(Stack *s, char *c) {
    if (s->top == -1) {
        return 0;
    } else {
        *c = s->data[s->top];
        s->top--;
        return 1;
    }
}

int is_empty(Stack *s) {
    if (s->top == -1) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    char str[MAX_SIZE];
    Stack s = { .top = -1 };

    printf("请输入一个字符串：");
    scanf("%s", str);

    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        push(&s, str[i]);
    }

    for (int i = 0; i < len; i++) {
        char c;
        pop(&s, &c);
        if (c != str[i]) {
            printf("%s不是回文串\n", str);
            return 0;
        }
    }

    printf("%s是回文串\n", str);
    return 0;
}

上面的代码通过栈的方式判断一个字符串是否为回文串。

2. 用队列实现循环移位

循环移位是指将一个长度为n的数组向右移动k个位置，移动后，数组的后k个元素出现在前面，前n-k个元素出现在后面。这个问题可以用队列来解决。

具体的做法是，首先将数组的后k个元素入队，然后把数组的前n-k个元素依次出队并入队，最后把队列中的元素依次出队并赋值给原数组。

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
} Queue;

int enqueue(Queue *q, int value) {
    if ((q->rear + 1) % MAX_SIZE == q->front) {
        return 0;
    } else if (q->front == -1 && q->rear == -1) {
        q->front = q->rear = 0;
        q->data[q->rear] = value;
        return 1;
    } else {
        q->rear = (q->rear + 1) % MAX_SIZE;
        q->data[q->rear] = value;
        return 1;
    }
}

int dequeue(Queue *q, int *value) {
    if (q->front == -1 && q->rear == -1) {
        return 0;
    } else if (q->front == q->rear) {
        *value = q->data[q->front];
        q->front = q->rear = -1;
        return 1;
    } else {
        *value = q->data[q->front];
        q->front = (q->front + 1) % MAX_SIZE;
        return 1;
    }
}

int is_empty(Queue *q) {
    if (q->front == -1 && q->rear == -1) {
        return 1;
    } else {
        return 0;
    }
}

int main() {
    int a[MAX_SIZE], n, k;
    Queue q = { .front = -1, .rear = -1 };

    printf("请输入数组长度n和移动位数k：");
    scanf("%d%d", &n, &k);

    printf("请输入%d个整数：", n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    for (int i = n - k; i < n; i++) {
        enqueue(&q, a[i]);
    }

    for (int i = 0; i < n - k; i++) {
        int value;
        dequeue(&q, &value);
        enqueue(&q, a[i]);
    }

    for (int i = 0; i < n; i++) {
        dequeue(&q, &a[i]);
    }

    printf("循环移位后的数组为：");
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}

上面的代码通过队列的方式实现了一个长度为n的数组向右移动k个位置的功能。