一、堆栈是什么（原理）
在数据结构中，堆栈（Stack）是一种特殊的线性表，它遵循后进先出（LIFO, Last In First Out）的原则。堆栈的基本操作主要包括压栈（Push）、弹栈（Pop）、查看栈顶元素（Peek 或 Top）、检查栈是否为空（IsEmpty）以及获取栈的大小（Size）。以下是一个简单的堆栈操作实现，使用C语言作为示例。
二、实验内容及过程
1.实现栈的顺序存储结构
在顺序存储结构中，栈的数据元素存储在一个数组中，通过栈顶指针来指示当前栈顶的位置。实验中实现了栈的初始化、判断栈是否为空、入栈、出栈、取栈顶元素等基本操作。
2.实现栈的链式存储结构
在链式存储结构中，栈的数据元素通过链表节点来存储，每个节点包含数据域和指向下一个节点的指针。实验中同样实现了栈的初始化、判断栈是否为空、入栈、出栈、取栈顶元素等基本操作，并设计了一个主函数对链式堆栈进行测试，测试方法包括依次把数据元素入栈，然后出栈并在屏幕上显示出栈的数据元素。
3.栈的应用
如：
- 使用栈完成对一个字符串的逆序输出。
- 使用栈完成判断表达式的括号是否匹配。
- 对算术表达式求值，包括将中缀表达式转换为后缀表达式并进行计算。
三、操作步骤
1、堆栈的定义
首先，我们需要定义堆栈的数据结构。这里我们使用动态数组（通过指针和动态内存分配实现）来、存储堆栈元素。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define INITIAL_CAPACITY 10 // 初始容量
typedef struct {
int *data; // 指向堆栈元素的指针
int top; // 栈顶索引（指向最后一个压入的元素）
int capacity; // 堆栈的容量
int size; // 堆栈的当前大小（元素个数）
} Stack;2、堆栈的初始化
在创建堆栈时，我们需要分配内存并初始化相关字段。
Stack* createStack(int initialCapacity) {
Stack *stack = (Stack*)malloc(sizeof(Stack));
if (!stack) {
perror("Failed to allocate memory for stack");
exit(EXIT_FAILURE);
}
stack->data = (int*)malloc(initialCapacity * sizeof(int));
if (!stack->data) {
perror("Failed to allocate memory for stack data");
free(stack);
exit(EXIT_FAILURE);
}
stack->top = -1; // 栈顶初始化为-1，表示堆栈为空
stack->capacity = initialCapacity;
stack->size = 0;
return stack;
}3、压栈操作
压栈操作将新元素添加到堆栈的顶部，并更新栈顶索引和堆栈大小。如果堆栈已满，可能需要扩展容量。
void push(Stack *stack, int value) {
if (stack->size == stack->capacity) {
// 堆栈已满，扩展容量（这里简单地将容量加倍）
int newCapacity = stack->capacity * 2;
int *newData = (int*)realloc(stack->data, newCapacity * sizeof(int));
if (!newData) {
perror("Failed to reallocate memory for stack data");
exit(EXIT_FAILURE);
}
stack->data = newData;
stack->capacity = newCapacity;
}
stack->data[++stack->top] = value;
stack->size++;
}4、弹栈操作
弹栈操作移除并返回堆栈顶部的元素，同时更新栈顶索引和堆栈大小。
int pop(Stack *stack) {
if (isEmpty(stack)) {
fprintf(stderr, "Stack underflow\n");
exit(EXIT_FAILURE); // 或者可以返回一个特殊值来表示错误
}
int value = stack->data[stack->top--];
stack->size--;
return value;
}5、查看栈顶元素
查看栈顶元素操作返回堆栈顶部的元素但不移除它。（这里未对函数isEmpty做详细定义，详情请看整体代码实现）
int peek(Stack *stack) {
if (isEmpty(stack)) {
fprintf(stderr, "Stack is empty\n");
exit(EXIT_FAILURE); // 或者可以返回一个特殊值来表示错误
}
return stack->data[stack->top];
}6、检查堆栈是否为空
检查堆栈是否为空操作返回一个布尔值来表示堆栈是否为空。
bool isEmpty(Stack *stack) {
return stack->size == 0;
}7、获取堆栈大小
获取堆栈大小操作返回堆栈中元素的个数。
int stackSize(Stack *stack) {
return stack->size;
}8、销毁堆栈
在不再需要堆栈时，我们应该释放其占用的内存。
void destroyStack(Stack *stack) {
if (stack) {
if (stack->data) {
free(stack->data);
}
free(stack);
}
}以上代码是各堆栈片段的操做实现，仅供学习参考。
四、完整操作代码实现
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 100 // 栈的最大容量
// 定义栈结构体
typedef struct {
char* data; // 动态数组
int top; // 栈顶指针
} Stack;
// 初始化栈
Stack* initStack() {
Stack* s = (Stack*)malloc(sizeof(Stack));
s->data = (char*)malloc(MAXSIZE * sizeof(char)); // 分配内存
s->top = -1; // 栈为空
return s;
}
// 判断栈是否为空
bool isEmpty(Stack* s) {
return s->top == -1;
}
// 判断栈是否为满
bool isFull(Stack* s) {
return s->top == MAXSIZE - 1;
}
// 压入栈
bool push(Stack* s, char elem) {
if (isFull(s)) {
printf("栈已满，无法压入元素。\n");
return false;
}
s->data[++s->top] = elem; // 压入元素
return true;
}
// 出栈
char pop(Stack* s) {
if (isEmpty(s)) {
printf("栈为空，无法出栈。\n");
return '\0'; // 返回空字符
}
return s->data[s->top--]; // 返回并删除栈顶元素
}
// 获取栈顶元素
char peek(Stack* s) {
if (isEmpty(s)) {
printf("栈为空，无法获取栈顶元素。\n");
return '\0'; // 返回空字符
}
return s->data[s->top]; // 返回栈顶元素
}
// 获取栈内元素个数
int size(Stack* s) {
return s->top + 1; // 返回元素个数
}
// 主程序
int main() {
Stack* s = initStack(); // 初始化栈
int choice;
char elem;
while (1) {
printf("\n======================\n");
printf(" 菜单\n");
printf("======================\n");
printf("1. 初始化栈\n");
printf("2. 判断栈是否非空\n");
printf("3. 输入元素\n");
printf("4. 输出栈内元素个数\n");
printf("5. 输出栈顶元素\n");
printf("6. 输出出栈序列\n");
printf("0. 退出程序\n");
printf("======================\n");
printf("请选择操作: ");
scanf("%d", &choice);
switch (choice) {
case 1:
s = initStack();
printf("栈已初始化。\n");
break;
case 2:
if (isEmpty(s)) {
printf("栈是空的。\n");
}
else {
printf("栈非空。\n");
}
break;
case 3:
printf("请输入要压入的元素（字符）：");
scanf(" %c", &elem); // 注意前面的空格用于跳过空白字符
push(s, elem);
break;
case 4:
printf("栈内元素个数: %d\n", size(s));
break;
case 5:
elem = peek(s);
if (elem != '\0') {
printf("栈顶元素: %c\n", elem);
}
break;
case 6:
printf("出栈序列: ");
while (!isEmpty(s)) {
printf("%c ", pop(s));
}
printf("\n");
break;
case 0:
free(s->data); // 释放动态分配的内存
free(s);
printf("程序退出。\n");
return 0;
default:
printf("无效选择，请重新输入。\n");
break;
}
}
return 0;
}运行结果如下：
以上代码展示的菜单可能并不美观，后期需要自己修改。
五、实验结果与分析
1.顺序栈与链栈的比较
顺序栈在访问速度上较快，因为其数据元素存储在连续的内存空间中，但在插入和删除操作时可能需要移动大量的数据元素。而链栈在插入和删除操作上较为灵活，不需要移动数据元素，但在访问速度上可能稍慢，因为其数据元素存储在分散的内存空间中。
2.栈的应用实现
- 在字符串逆序输出中，通过依次将字符入栈，然后依次出栈即可实现逆序输出。
- 在括号匹配问题中，通过设置一个栈来存储左括号，每当遇到右括号时检查是否与栈顶的左括号匹配，从而判断括号是否正确配对。
- 在算术表达式求值中，先将中缀表达式转换为后缀表达式，然后利用栈进行求值。转换过程中，通过遍历表达式，遇到操作数则入栈，遇到操作符则弹出两个操作数进行运算，并将结果再次入栈。
3.实验中的问题与解决
在实验过程中，遇到了一些问题，如内存分配失败、栈溢出等。通过检查代码和调试程序，最终成功解决了这些问题。同时，在实验中也深刻体会到了栈这种数据结构的强大功能和灵活性。
六、实验总结
通过本次实验，我深刻理解了栈这种特殊线性结构的特性和操作原理，掌握了栈在顺序存储结构和链表存储结构下的基本运算方法。同时，通过利用栈的特性解决了一些实际问题，如字符串逆序输出、括号匹配和算术表达式求值等，进一步加深了对栈的理解和应用能力。本次实验不仅提高了我的编程能力和问题解决能力，也为后续的学习和工作打下了坚实的基础。
标签：数据结构,int,元素,stack,printf,堆栈,实验报告,Stack From： https://blog.csdn.net/weixin_56313201/article/details/143892246