栈和队列（C）

**栈和队列**

在计算机科学中，栈和队列是两种基本的数据结构，它们分别用于存储和管理元素的顺序。栈通常使用后进先出（LIFO）的原则，而队列则使用先进先出（FIFO）的原则。

**栈**

栈是一种特殊的线性表，它遵循后进先出的原则，即最后添加的元素将首先被移除。栈通常使用一个数组或链表来实现。

### 栈的基本操作1. **push**: 将元素添加到栈顶。
2. **pop**: 移除栈顶元素并返回其值。
3. **peek**: 返回栈顶元素的值，但不移除它。
4. **isEmpty**: 检查栈是否为空。

### 栈的实现我们可以使用一个数组来实现栈。下面是C语言中的栈实现代码：

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

// 栈结构体typedef struct {
 int* elements;
 int size;
 int capacity;
} Stack;

// 创建一个新的栈Stack* createStack(int initialCapacity) {
 Stack* stack = (Stack*)malloc(sizeof(Stack));
 stack->elements = (int*)malloc(initialCapacity * sizeof(int));
 stack->size =0;
 stack->capacity = initialCapacity;
 return stack;
}

// 将元素添加到栈顶void push(Stack* stack, int element) {
 if (stack->size == stack->capacity) {
 // 栈满了，需要扩容 stack->capacity *=2;
 int* newElements = (int*)malloc(stack->capacity * sizeof(int));
 for (int i =0; i < stack->size; i++) {
 newElements[i] = stack->elements[i];
 }
 free(stack->elements);
 stack->elements = newElements;
 }
 stack->elements[stack->size++] = element;
}

// 移除栈顶元素并返回其值int pop(Stack* stack) {
 if (stack->isEmpty()) {
 // 栈空了，无法移除元素 return -1; // 或抛出异常 }
 int element = stack->elements[--stack->size];
 free(stack->elements);
 stack->elements = (int*)malloc(stack->capacity * sizeof(int));
 return element;
}

// 返回栈顶元素的值，但不移除它int peek(Stack* stack) {
 if (stack->isEmpty()) {
 // 栈空了，无法返回元素 return -1; // 或抛出异常 }
 return stack->elements[stack->size -1];
}

// 检查栈是否为空int isEmpty(Stack* stack) {
 return stack->size ==0;
}

cint main() {
 // 创建一个新的栈，初始容量为10 Stack* stack = createStack(10);

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

 // 移除栈顶元素并返回其值 int element = pop(stack);
 printf("弹出元素：%d
", element); // 输出：3 // 返回栈顶元素的值，但不移除它 element = peek(stack);
 printf("栈顶元素：%d
", element); // 输出：2 // 检查栈是否为空 int isEmpty = isEmpty(stack);
 printf("栈是否为空：%s
", isEmpty ? "是" : "否"); // 输出：否 return0;
}

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

// 队列结构体typedef struct {
 int* elements;
 int size;
 int capacity;
} Queue;

// 创建一个新的队列Queue* createQueue(int initialCapacity) {
 Queue* queue = (Queue*)malloc(sizeof(Queue));
 queue->elements = (int*)malloc(initialCapacity * sizeof(int));
 queue->size =0;
 queue->capacity = initialCapacity;
 return queue;
}

// 将元素添加到队尾void enqueue(Queue* queue, int element) {
 if (queue->size == queue->capacity) {
 // 队列满了，需要扩容 queue->capacity *=2;
 int* newElements = (int*)malloc(queue->capacity * sizeof(int));
 for (int i =0; i < queue->size; i++) {
 newElements[i] = queue->elements[i];
 }
 free(queue->elements);
 queue->elements = newElements;
 }
 queue->elements[queue->size++] = element;
}

// 移除队头元素并返回其值int dequeue(Queue* queue) {
 if (queue->isEmpty()) {
 // 队列空了，无法移除元素 return -1; // 或抛出异常 }
 int element = queue->elements[0];
 for (int i =1; i < queue->size; i++) {
 queue->elements[i -1] = queue->elements[i];
 }
 queue->size--;
 return element;
}

// 返回队头元素的值，但不移除它int peek(Queue* queue) {
 if (queue->isEmpty()) {
 // 队列空了，无法返回元素 return -1; // 或抛出异常 }
 return queue->elements[0];
}

// 检查队列是否为空int isEmpty(Queue* queue) {
 return queue->size ==0;
}

cint main() {
 // 创建一个新的队列，初始容量为10 Queue* queue = createQueue(10);

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

 // 移除队头元素并返回其值 int element = dequeue(queue);
 printf("弹出元素：%d
", element); // 输出：1 // 返回队头元素的值，但不移除它 element = peek(queue);
 printf("队头元素：%d
", element); // 输出：2 // 检查队列是否为空 int isEmpty = isEmpty(queue);
 printf("队列是否为空：%s
", isEmpty ? "是" : "否"); // 输出：否 return0;
}