永康公司网站开发,国家企业信用公示信息年报入口,微网站营销是什么,网站开发教程全集1 std::stack 应用于自定义数据结构
通常#xff0c;std::stack 用于存储基本数据类型#xff0c;如 int、float、char 等。然而#xff0c;std::stack 同样可以存储自定义的数据结构#xff0c;只要这些数据结构满足一定的要求。
#xff08;1#xff09;存储自定义数…1 std::stack 应用于自定义数据结构
通常std::stack 用于存储基本数据类型如 int、float、char 等。然而std::stack 同样可以存储自定义的数据结构只要这些数据结构满足一定的要求。
1存储自定义数据结构的要求
要使自定义数据结构能够存储在 std::stack 中该数据结构必须满足以下条件
可复制性自定义数据结构必须能够被复制。这意味着它必须有一个有效的复制构造函数和一个赋值运算符。当元素被压入栈或从栈中弹出时会涉及到复制操作。析构函数自定义数据结构应该有一个合适的析构函数以确保在元素从栈中删除时能够正确地释放资源。
2使用 std::stack 存储自定义数据结构
下面是一个简单的例子展示了如何使用 std::stack 存储自定义的数据结构
#include iostream
#include stack // 自定义数据结构
struct MyData { int id; std::string name; // 构造函数 MyData(int id, const std::string name) : id(id), name(name) {} // 输出数据结构的内容 void print() const { std::cout ID: id , Name: name std::endl; }
}; int main()
{ // 创建一个存储 MyData 类型元素的栈 std::stackMyData dataStack; // 创建一些 MyData 对象并将其压入栈中 dataStack.push(MyData(1, Alice)); dataStack.push(MyData(2, Bob)); dataStack.push(MyData(3, Charlie)); // 遍历栈并输出每个元素的内容 while (!dataStack.empty()) { MyData topData dataStack.top(); // 获取栈顶元素但不移除它 topData.print(); // 输出栈顶元素的内容 dataStack.pop(); // 移除栈顶元素 } return 0;
}上面代码的输出为
ID: 3, Name: Charlie
ID: 2, Name: Bob
ID: 1, Name: Alice这个例子定义了一个名为 MyData 的自定义数据结构它包含两个成员变量id 和 name。然后我们创建了一个 std::stackMyData 类型的栈用于存储 MyData 对象。通过调用 push 方法将 MyData 对象压入栈中并通过循环和 top、pop 方法遍历并输出栈中每个元素的内容。
3注意事项
内存管理当自定义数据结构包含动态分配的内存如指针、动态数组等时需要确保在复制和析构过程中正确地管理这些内存。性能考虑对于大型或复杂的自定义数据结构频繁地复制元素可能会对性能产生显著影响。在这种情况下可以考虑使用指针或智能指针如 std::shared_ptr 或 std::unique_ptr来存储数据结构的引用而不是直接存储数据结构本身。异常安全性在自定义数据结构的复制构造函数和赋值运算符中应确保操作是异常安全的以避免在发生异常时导致资源泄漏或其他问题。
2 std::stack 的主要应用场景
下面是 std::stack 的一些主要应用场景
1函数调用与递归
在函数调用和递归实现中局部变量和参数通常被存储在栈上。std::stack 可以模拟这种行为帮助理解函数调用的过程。
2表达式求值
在算术表达式或逻辑表达式的求值过程中通常使用栈来存储操作数和操作符。例如实现一个简单的四则运算器时可以利用栈来处理运算符和操作数的优先级。
3深度优先搜索DFS
在图或树的深度优先搜索中栈可以用来保存待访问的节点。每次从栈中弹出一个节点并访问其相邻节点然后将相邻节点压入栈中直到栈为空或达到搜索目标。
4括号匹配
在解析包含括号的字符串如数学表达式、编程语言中的代码块等时栈可以用来跟踪未闭合的括号以确保它们的正确匹配。
5撤销/重做操作
在一些需要撤销或重做功能的应用中如文本编辑器、绘图工具等可以使用栈来存储历史操作。撤销操作就是弹出栈顶元素重做操作则是将之前弹出的元素再次压入栈中。
6解析与编译器设计
在编译器设计中栈可以用来跟踪语法分析过程中的符号和状态。
7UI导航历史
在一些图形用户界面GUI应用中栈可以用来存储用户的导航历史以便用户可以向前或向后导航。
8游戏开发
在某些游戏中栈可以用来管理游戏状态、事件或动作序列。
9算法实现
一些算法如汉诺塔问题、中序遍历的非递归实现等都可以使用栈来辅助实现。
2.1 std::stack 应用于函数调用与递归
下面是一个简单的示例演示了如何使用 std::stack 来模拟函数调用和递归的过程。在这个示例中我们将创建一个简单的函数调用栈并模拟执行一些基本的函数调用和返回操作。
#include iostream
#include stack
#include string // 模拟的函数调用记录结构
struct FunctionCall { std::string functionName; // 函数名 int returnAddress; // 返回地址在栈中的位置 // 构造函数 FunctionCall(const std::string name, int addr) : functionName(name), returnAddress(addr) {}
}; int main()
{ std::stackFunctionCall callStack; // 函数调用栈 int currentPosition 0; // 当前执行位置 // 模拟函数A的调用 std::cout Entering function A std::endl; callStack.push(FunctionCall(A, currentPosition 1)); // 压入函数调用记录 currentPosition; // 移动到下一个执行位置 // 假设函数A调用了函数B std::cout Calling function B from A std::endl; callStack.push(FunctionCall(B, currentPosition 1)); // 压入函数B的调用记录 currentPosition; // 移动到下一个执行位置 // 执行函数B的代码这里只是模拟 std::cout Executing function B std::endl; currentPosition; // 假设函数B执行了一些操作移动到下一个执行位置 // 函数B执行完毕准备返回 std::cout Returning from function B std::endl; FunctionCall topCall callStack.top(); // 获取栈顶函数调用记录 std::cout Returning to topCall.functionName std::endl; callStack.pop(); // 弹出栈顶记录表示返回 currentPosition topCall.returnAddress; // 设置返回地址 // 继续执行函数A的剩余代码 std::cout Continuing execution in function A std::endl; currentPosition; // 移动到下一个执行位置如果有的话 // 函数A执行完毕准备返回 std::cout Returning from function A std::endl; if (!callStack.empty()) { topCall callStack.top(); // 如果有更多函数调用则获取栈顶记录 std::cout Returning to topCall.functionName std::endl; callStack.pop(); // 弹出栈顶记录表示返回到上一层调用 currentPosition topCall.returnAddress; // 设置新的返回地址 } else { std::cout Program execution finished std::endl; } return 0;
}上面代码的输出为
Entering function A
Calling function B from A
Executing function B
Returning from function B
Returning to B
Continuing execution in function A
Returning from function A
Returning to A这个示例定义了一个 FunctionCall 结构体来记录每次函数调用的信息包括函数名和返回地址在调用栈中的位置。示例中使用 std::stackFunctionCall 来模拟函数调用栈的行为。每次函数调用时将一个新的 FunctionCall 对象压入栈中并记录当前的执行位置。当函数返回时从栈顶弹出记录并根据记录的返回地址继续执行。
注意这个示例是为了演示目的而简化的。在实际的程序中函数调用和返回通常涉及到更多的复杂性和细节比如局部变量、参数传递、作用域等。此外这个示例也没有展示如何处理函数调用中的参数和返回值。在实际的编译器或解释器实现中函数调用栈会更加复杂并且会紧密地与程序的执行流程相结合。
2.2 std::stack 应用于表达式求值
下面是一个使用 std::stack 来实现简单四则运算表达式求值的示例。这个示例将实现一个基本的计算器能够处理加、减、乘、除四种运算。为了实现这个计算器需要使用两个栈一个用于存储操作数另一个用于存储操作符。
#include iostream
#include stack
#include cctype
#include string
#include cmath // 定义运算符的优先级
int getPrecedence(char op) { if (op || op -) return 1; if (op * || op /) return 2; return 0;
} // 执行运算
double applyOp(double a, double b, char op) { switch(op) { case : return a b; case -: return a - b; case *: return a * b; case /: if (b ! 0.0) return a / b; else throw std::invalid_argument(Division by zero); default: throw std::invalid_argument(Unknown operator); }
} // 计算表达式的值
double evaluateExpression(const std::string expr) { std::stackdouble values; // 操作数栈 std::stackchar ops; // 操作符栈 for (size_t i 0; i expr.size(); i) { char ch expr[i]; // 如果是空格则跳过 if (std::isspace(ch)) continue; // 如果是操作数则压入操作数栈 if (std::isdigit(ch)) { double val 0; // 处理多位数 while (i expr.size() std::isdigit(expr[i])) { val val * 10 (expr[i] - 0); i; } --i; // 因为for循环还会递增i所以这里要减回去 values.push(val); } // 如果是左括号则压入操作符栈 else if (ch () { ops.push(ch); } // 如果是右括号则执行栈顶操作符直到遇到左括号 else if (ch )) { while (!ops.empty() ops.top() ! () { double val2 values.top(); values.pop(); double val1 values.top(); values.pop(); char op ops.top(); ops.pop(); values.push(applyOp(val1, val2, op)); } if (!ops.empty()) ops.pop(); // 弹出左括号 } // 如果是操作符则根据优先级进行处理 else if (ch || ch - || ch * || ch /) { while (!ops.empty() getPrecedence(ops.top()) getPrecedence(ch)) { double val2 values.top(); values.pop(); double val1 values.top(); values.pop(); char op ops.top(); ops.pop(); values.push(applyOp(val1, val2, op)); } ops.push(ch); } // 如果是非法字符则抛出异常 else { throw std::invalid_argument(Invalid character in expression); } } // 应用栈中剩余的操作符 while (!ops.empty()) { double val2 values.top(); values.pop(); double val1 values.top(); values.pop(); char op ops.top(); ops.pop(); values.push(applyOp(val1, val2, op)); } // 表达式的结果应该在操作数栈的顶部 return values.top();
} int main()
{ std::string expression (12)*(26)/2-1;try { double result evaluateExpression(expression); std::cout Result: result std::endl; } catch (const std::exception e) { std::cerr Error: e.what() std::endl; } return 0;
}上面代码的输出为
Result: 11程序中首先定义了一个 getPrecedence 函数来返回运算符的优先级然后定义了一个 applyOp 函数来执行实际的运算。在 evaluateExpression 函数中遍历输入的表达式并根据字符类型执行相应的操作。
当遇到数字时将其解析为一个 double 类型的数值并压入操作数栈。当遇到左括号时将其压入操作符栈。当遇到右括号时弹出操作符栈顶的操作符并执行相应的运算直到遇到左括号为止。当遇到操作符时则根据操作符的优先级来决定是否先执行栈顶的操作符。
最后在遍历完整个表达式后将执行操作符栈中剩余的所有操作符并将最终的结果存储在操作数栈的顶部。
2.3 std::stack 应用于深度优先搜索DFS
栈在深度优先搜索DFS中是一个非常有用的数据结构。以下是一个使用 std::stack 来实现深度优先搜索的简单示例。这个示例将在一个无向图中进行深度优先搜索。
#include iostream
#include vector
#include stack
#include unordered_set // 使用邻接列表表示图
class Graph {
public: Graph(int vertices) : adjList(vertices) {} // 添加边 void addEdge(int src, int dest) { adjList[src].push_back(dest); adjList[dest].push_back(src); // 对于无向图需要添加反向边 } // 深度优先搜索 void DFS(int start) { std::stackint s; std::unordered_setint visited; s.push(start); visited.insert(start); while (!s.empty()) { int vertex s.top(); s.pop(); std::cout vertex ; // 遍历与当前节点相邻且未被访问过的节点 for (int neighbor : adjList[vertex]) { if (visited.find(neighbor) visited.end()) { s.push(neighbor); visited.insert(neighbor); } } } } private: std::vectorstd::vectorint adjList; // 邻接列表
}; int main()
{ Graph g(5); // 创建一个包含5个顶点的图 // 添加边 g.addEdge(0, 1); g.addEdge(0, 4); g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(1, 4); g.addEdge(2, 3); g.addEdge(3, 4); std::cout Depth First Traversal (starting from vertex 0): ; g.DFS(0); std::cout std::endl; return 0;
}上面代码的输出为
Depth First Traversal (starting from vertex 0): 0 4 3 2 1这个示例首先定义了一个 Graph 类它包含一个邻接列表 adjList 来存储图的信息。addEdge 方法用于向图中添加边。
DFS 方法是深度优先搜索的实现。它使用一个栈 s 来保存待访问的节点以及一个 visited 哈希集合来跟踪已经访问过的节点。搜索从指定的起始节点 start 开始。
在 DFS 方法中首先将起始节点压入栈中并标记为已访问。然后在栈不为空的情况下不断地从栈顶取出节点访问它并将其未访问过的相邻节点压入栈中。这个过程一直持续到栈为空即所有可达的节点都已被访问。
在 main 函数中创建了一个包含5个顶点的图并添加了一些边。然后从顶点0开始进行深度优先遍历并输出遍历结果。
运行这个程序可以看到从顶点0开始的深度优先遍历结果。由于图的结构和遍历顺序可能因实现细节和编译器行为的不同而略有差异因此输出可能不是唯一的。
3 实现一个简单的 std::stack 容器
下面是一个简单的 MyStack 类的实现它使用 std::vector 作为底层容器。
#include iostream
#include vector template typename T
class MyStack {
public:// 构造函数 MyStack() : elements() {}// 判断栈是否为空 bool empty() const {return elements.empty();}// 返回栈顶元素不删除 T top() {if (empty()) {throw std::out_of_range(Stack is empty);}return elements.back();}const T top() const {if (empty()) {throw std::out_of_range(Stack is empty);}return elements.back();}// 将元素压入栈顶 void push(const T value) {elements.push_back(value);}// 弹出栈顶元素 void pop() {if (empty()) {throw std::out_of_range(Stack is empty);}elements.pop_back();}// 返回栈的大小 size_t size() const {return elements.size();}private:std::vectorT elements; // 底层容器
};int main()
{MyStackint myStack;// 压入几个元素 myStack.push(1);myStack.push(2);myStack.push(3);// 输出栈的大小 std::cout Size of stack: myStack.size() std::endl;// 弹出栈顶元素并输出 myStack.pop();std::cout Top element after pop: myStack.top() std::endl;// 判断栈是否为空 if (myStack.empty()) {std::cout Stack is empty. std::endl;}else {std::cout Stack is not empty. std::endl;}return 0;
}上面代码的输出为
Size of stack: 3
Top element after pop: 2
Stack is not empty.这个简单的 MyStack 类提供了基本的栈操作包括 push压栈、pop弹栈、top查看栈顶元素、empty判断栈是否为空和 size获取栈的大小。它使用 std::vector 作为底层容器来存储元素并利用 vector 的 push_back 和 pop_back 方法来实现栈的基本操作。
