栈和队列 --- C语言实现

**栈和队列的基本概念**

在计算机科学中，栈和队列是两种常见的数据结构，它们都用于存储和管理元素的顺序。虽然它们看起来很相似，但它们有着不同的使用场景和特点。

### 栈**定义**

栈是一种后进先出的数据结构（LIFO），意味着最后添加的元素将首先被移除。栈通常用来实现递归算法、表达式求值和括号匹配等功能。

**基本操作**

栈支持以下基本操作：

* **push**: 将一个元素添加到栈顶。
* **pop**: 移除并返回栈顶的元素。
* **peek**: 返回栈顶的元素，但不移除它。
* **isEmpty**: 检查栈是否为空。

### 队列**定义**

队列是一种先进先出的数据结构（FIFO），意味着最先添加的元素将首先被移除。队列通常用来实现任务调度、消息传递和缓冲等功能。

**基本操作**

队列支持以下基本操作：

* **enqueue**: 将一个元素添加到队尾。
* **dequeue**: 移除并返回队头的元素。
* **peek**: 返回队头的元素，但不移除它。
* **isEmpty**: 检查队列是否为空。

### C语言实现下面是栈和队列的C语言实现：

#### 栈实现

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

// 定义栈结构体typedef struct {
 int *data;
 int top; // 栈顶指针 int capacity; // 栈容量} Stack;

// 初始化栈void initStack(Stack *s, int capacity) {
 s->data = (int *)malloc(sizeof(int) * capacity);
 s->top = -1;
 s->capacity = capacity;
}

// 检查栈是否为空int isEmpty(Stack *s) {
 return s->top == -1;
}

// 检查栈是否满了int isFull(Stack *s) {
 return s->top == s->capacity -1;
}

// 将元素添加到栈顶void push(Stack *s, int element) {
 if (isFull(s)) {
 printf("Stack overflow!
");
 return;
 }
 s->data[++s->top] = element;
}

// 移除并返回栈顶的元素int pop(Stack *s) {
 if (isEmpty(s)) {
 printf("Stack underflow!
");
 return -1; // 返回-1表示出错 }
 return s->data[s->top--];
}

// 返回栈顶的元素，但不移除它int peek(Stack *s) {
 if (isEmpty(s)) {
 printf("Stack is empty!
");
 return -1;
 }
 return s->data[s->top];
}

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

// 定义队列结构体typedef struct {
 int *data;
 int front; // 队头指针 int rear; // 队尾指针 int size; // 队列大小} Queue;

// 初始化队列void initQueue(Queue *q, int capacity) {
 q->data = (int *)malloc(sizeof(int) * capacity);
 q->front = -1;
 q->rear = -1;
 q->size =0;
}

// 检查队列是否为空int isEmpty(Queue *q) {
 return q->front == -1 && q->rear == -1;
}

// 将元素添加到队尾void enqueue(Queue *q, int element) {
 if (q->size == q->data[0]) {
 printf("Queue is full!
");
 return;
 }
 if (isEmpty(q)) {
 q->front =0;
 q->rear =0;
 } else {
 q->rear++;
 }
 q->data[q->rear] = element;
 q->size++;
}

// 移除并返回队头的元素int dequeue(Queue *q) {
 if (isEmpty(q)) {
 printf("Queue is empty!
");
 return -1; // 返回-1表示出错 }
 int element = q->data[q->front];
 q->size--;
 if (q->rear == q->front) {
 q->front = -1;
 q->rear = -1;
 } else if (q->rear >0) {
 q->front++;
 }
 return element;
}

// 返回队头的元素，但不移除它int peek(Queue *q) {
 if (isEmpty(q)) {
 printf("Queue is empty!
");
 return -1;
 }
 return q->data[q->front];
}

cint main() {
 // 初始化栈和队列 Stack s;
 initStack(&s,10);
 Queue q;
 initQueue(&q,10);

 // 将元素添加到栈顶 push(&s,1);
 push(&s,2);
 push(&s,3);

 // 移除并返回栈顶的元素 printf("%d
", pop(&s)); // 输出:3 printf("%d
", pop(&s)); // 输出:2 printf("%d
", pop(&s)); // 输出:1 // 检查栈是否为空 if (isEmpty(&s)) {
 printf("Stack is empty!
");
 } else {
 printf("Stack is not empty!
");
 }

 // 将元素添加到队尾 enqueue(&q,1);
 enqueue(&q,2);
 enqueue(&q,3);

 // 移除并返回队头的元素 printf("%d
", dequeue(&q)); // 输出:1 printf("%d
", dequeue(&q)); // 输出:2 printf("%d
", dequeue(&q)); // 输出:3 // 检查队列是否为空 if (isEmpty(&q)) {
 printf("Queue is empty!
");
 } else {
 printf("Queue is not empty!
");
 }

 return0;
}