目录😋
任务描述
本关任务：编写一个程序实现链栈的基本运算。
相关知识
为了完成本关任务，你需要掌握：
- 初始化栈
- 销毁栈
- 判断栈是否为空
- 进栈
- 出栈
- 取栈顶元素
1. 初始化栈
- 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。
- 示例（顺序栈）：
以下是一个简单的顺序栈初始化示例，假设用 C 语言实现，栈中存储整数，最大容量为MAX_SIZE。
int stack[MAX_SIZE]; int top = - 1;
这里
top初始化为- 1，表示栈为空。当top为- 1时，栈中没有元素。- 示例（链式栈）：
定义链式栈的节点结构：
typedef struct StackNode { int data; struct StackNode *next; } StackNode; StackNode *top = NULL;
这里将栈顶指针
top初始化为NULL，表示栈为空。当top为NULL时，没有节点在栈中。2. 销毁栈
- 概念：销毁栈是释放栈占用的内存资源。对于顺序栈，如果栈是通过数组实现的，且数组是在栈的生命周期内自动分配的（如在函数内部定义的局部数组），一般不需要手动释放内存；但如果是动态分配的数组，需要使用
free等函数释放。对于链式栈，需要逐个释放栈中的节点，避免内存泄漏。- 示例（顺序栈 - 动态分配情况）：
假设栈是通过动态分配的数组实现的，以下是销毁栈的示例：
void destroyStack() { // 释放动态分配的数组内存 free(stack); }
- 示例（链式栈）：
以下是链式栈销毁的过程，需要遍历栈中的节点并释放它们：
void destroyStack() { StackNode *current = top; StackNode *next; while (current!= NULL) { next = current - > next; free(current); current = next; } top = NULL; }
3. 判断栈是否为空
- 概念：判断栈中是否有元素。对于顺序栈，通过检查栈顶指针（如
top）是否为初始值来判断；对于链式栈，检查栈顶指针是否为NULL。- 示例（顺序栈）：
可以通过以下方式判断顺序栈是否为空：
int isEmpty() { return top == - 1; }
- 示例（链式栈）：
对于链式栈，判断是否为空的函数如下：
int isEmpty() { return top == NULL; }
4. 进栈（Push）
- 概念：将元素添加到栈顶。对于顺序栈，需要先检查栈是否已满，然后将元素存入栈顶位置，并更新栈顶指针；对于链式栈，创建新节点，将元素存入新节点，然后将新节点插入到栈顶位置，更新栈顶指针。
- 示例（顺序栈）：
以下是顺序栈进栈的操作示例：
int push(int value) { if (top == MAX_SIZE - 1) { // 栈已满 return 0; } top++; stack[top] = value; return 1; }
- 示例（链式栈）：
链式栈进栈操作如下：
int push(int value) { StackNode *newNode = (StackNode *)malloc(sizeof(StackNode)); if (newNode == NULL) { // 内存分配失败 return 0; } newNode - > data = value; newNode - > next = top; top = newNode; return 1; }
5. 出栈（Pop）
- 概念：从栈顶移除元素。对于顺序栈，需要先检查栈是否为空，然后取出栈顶元素，更新栈顶指针；对于链式栈，取出栈顶节点的数据，释放栈顶节点，更新栈顶指针。
- 示例（顺序栈）：
顺序栈出栈操作如下：
int pop() { if (isEmpty()) { // 栈为空 return - 1; } int value = stack[top]; top--; return value; }
- 示例（链式栈）：
链式栈出栈操作如下：
int pop() { if (isEmpty()) { // 栈为空 return - 1; } StackNode *temp = top; int value = top - > data; top = top - > next; free(temp); return value; }
6. 取栈顶元素
- 概念：获取栈顶的元素，但不将其从栈中移除。对于顺序栈和链式栈，都需要先检查栈是否为空，然后返回栈顶元素的值。
- 示例（顺序栈）：
顺序栈取栈顶元素操作如下：
int peek() { if (isEmpty()) { // 栈为空 return - 1; } return stack[top]; }
- 示例（链式栈）：
链式栈取栈顶元素操作如下：
int peek() { if (isEmpty()) { // 栈为空 return - 1; } return top - > data; }
测试说明
平台会对你编写的代码进行测试：
测试输入：
abcde
预期输出：
(1)初始化栈s (2)栈为空 (3)依次进栈元素:a b c d e (4)栈为非空 (5)出栈序列:e d c b a (6)栈为空 (7)释放栈
测试输入：
xyz
预期输出：
(1)初始化栈s (2)栈为空 (3)依次进栈元素:x y z (4)栈为非空 (5)出栈序列:z y x (6)栈为空 (7)释放栈
开始你的任务吧，祝你成功！
通关代码
// 请在Begin-End之间添加你的代码， //实现链栈的如下基本运算，假设链栈的元素类型为char// //(1)初始化栈s// //(2)判断栈s是否非空，输出判断结果// //(3)依次进栈元素，注：进栈元素由用户输入// //(4)判断栈s是否非空，输出判断结果// //(5)输出出栈序列// //(6)判断栈s是否非空，输出判断结果// //(7)释放栈// /********** Begin *********/ using namespace std; struct Node{ char data; Node *next; Node(char x): data(x),next(NULL){} }; class Stack{ private: Node *top; public: Stack() : top(NULL){} ~Stack(){ while(top != NULL){ Node *temp = top; top = top -> next; delete temp; } } bool isEmpty(){return top == NULL;} void push(char x){ Node *newNode = new Node(x); newNode->next = top; top = newNode; } char pop(){ if(isEmpty()){ throw "Stack is empty"; } char x = top->data; Node *temp = top; top =top->next; delete temp; return x; } char peek(){ if(isEmpty()){ throw "Stack is empty"; } return top->data; } }; int main(){ string input; cin>>input; Stack s; cout <<"(1)初始化栈s"<<endl; if(s.isEmpty()){ cout<<"(2)栈为空"<<endl; } cout <<"(3)依次进栈元素:"; for(char c : input){ s.push(c); cout <<c<<" "; } cout <<endl; if(!s.isEmpty()){ cout <<"(4)栈为非空"<<endl; } cout <<"(5)出栈序列:"; while (!s.isEmpty()){ cout <<s.pop()<<" "; } cout <<endl; if(s.isEmpty()){ cout<<"(6)栈为空"<<endl; } cout << "(7)释放栈"<<endl; return 0; } /********** End **********/
测试结果
