（一）实验类型：设计性

（二）实验目的：

      1．掌握栈和队列的抽象数据类型。

2．掌握实现栈和队列的各种操作的算法。

3．理解栈与递归的关系。

4. 掌握队列的链式存贮结构及基本操作，深入了解链队列的基本特性，以便在实际问题背景下灵活运用它们。

（三）实验内容：

1. 栈和队列的数据结构定义；

2. 栈的建立、初始化、判空、入栈、出栈等操作。

  3. 队列的建立、初始化、判空、入队、出队等操作。

//1. 栈和队列的数据结构定义：// 栈的数据结构定义
typedef struct {int top;             // 栈顶指针int capacity;        // 栈容量int* array;          // 栈数据
} Stack;// 队列的数据结构定义
typedef struct {int front;           // 队首指针int rear;            // 队尾指针int capacity;        // 队列容量int* array;          // 队列数据
} Queue;//在C / C++中，数组名本质上是一个指向数组首元素的指针。
//因此，当使用 int* array; 声明一个指针时，array指向的是一个int类型的内存空间，
//它可以被用来存储整数数据，也可以被当做数组使用。//2. 栈的建立、初始化、判空、入栈、出栈等操作：// 创建一个新的栈
Stack * createStack(int capacity) {Stack* stack = (Stack*)malloc(sizeof(Stack));stack->capacity = capacity;stack->top = -1;stack->array = (int*)malloc(capacity * sizeof(int));//需要内存的访问，要访问容量才能设置合理的内存空间return stack;
}// 判断栈是否为空
int isStackEmpty(Stack* stack) {return stack->top == -1;
}// 判断栈是否已满
int isStackFull(Stack* stack) {return stack->top == stack->capacity - 1;
}
//从-1开始，自然要-1// 入栈
void push(Stack* stack, int item) {if (isStackFull(stack)) {printf("栈已满，无法入栈。\n");return;}stack->array[++stack->top] = item;// stack->top是一个整体，表示栈顶//然后才是++，表示插入下一个位置printf("%d 入栈成功。\n", item);
}// 出栈
int pop(Stack* stack) {if (isStackEmpty(stack)) {printf("栈为空，无法出栈。\n");return -1;}int item = stack->array[stack->top--];//只需要把Top数减一即可printf("%d 出栈成功。\n", item);return item;
}// 清空栈
void clearStack(Stack* stack) {stack->top = -1;
}// 销毁栈
void destroyStack(Stack* stack) {free(stack->array);free(stack);
}
```//3. 队列的建立、初始化、判空、入队、出队等操作：// 创建一个新的队列
Queue * createQueue(int capacity) {Queue* queue = (Queue*)malloc(sizeof(Queue));queue->capacity = capacity;queue->front = queue->rear = -1;queue->array = (int*)malloc(capacity * sizeof(int));return queue;
}// 判断队列是否为空
int isQueueEmpty(Queue* queue) {return queue->front == -1;
}// 判断队列是否已满
int isQueueFull(Queue* queue) {return (queue->rear + 1) % queue->capacity == queue->front;}// 入队
void enqueue(Queue* queue, int item) {if (isQueueFull(queue)) {printf("队列已满，无法入队。\n");return;}if (isQueueEmpty(queue)) {queue->front = queue->rear = 0;}else {queue->rear = (queue->rear + 1) % queue->capacity;//分配一个位置给新的数据}queue->array[queue->rear] = item;printf("%d 入队成功。\n", item);
}// 出队
int dequeue(Queue* queue) {if (isQueueEmpty(queue)) {printf("队列为空，无法出队。\n");return -1;}int item = queue->array[queue->front];//队头出队if (queue->front == queue->rear) //相等时，说明队列中仅有一个元素，所以出队完该元素后就直接设置为队空即可{queue->front = queue->rear = -1;}else {queue->front = (queue->front + 1) % queue->capacity;//直接替换成下一个front}printf("%d 出队成功。\n", item);return item;
}// 清空队列
void clearQueue(Queue* queue) {queue->front = queue->rear = -1;
}// 销毁队列
void destroyQueue(Queue* queue) {free(queue->array);free(queue);
}