网站建设四个步骤,动漫制作专业笔记本电脑推荐,生成器,wordpress炫酷主题栈 ADT 及实现
栈#xff08;stack#xff09;是存放数据对象的一种特殊容器#xff0c;其中的数据元素按线性的逻辑次序排列#xff0c;故也可定义首、末元素。 尽管栈结构也支持对象的插入和删除操作#xff0c;但其操作的范围仅限于栈的某一特定端。 也就是说#xf…栈 ADT 及实现
栈stack是存放数据对象的一种特殊容器其中的数据元素按线性的逻辑次序排列故也可定义首、末元素。 尽管栈结构也支持对象的插入和删除操作但其操作的范围仅限于栈的某一特定端。 也就是说若约定新的元素只能从某一端插入其中则反过来也只能从这一端删除已有的元素。禁止操作的另一端称作盲端。
后进先出从栈结构的整个生命期来看更晚早出栈的元素应为更早晚入栈者。
ADT功能size()返回栈的规模empty()判断栈是否为空push(e)将 e 插至栈顶pop()删除栈顶对象top()引用栈顶对象
实现
#include ../Vector/Vector.h //以向量为基类派生出栈模板类
template typename T class Stack: public VectorT { //将向量首/末端作为栈底/顶
public: //size()、empty()以及其它开放接口均可直接沿用void push ( T const e ) { insert ( size(), e ); } //入栈等效于将新元素作为向量末元素插入T pop() { return remove ( size() - 1 ); } //出栈等效于删除向量末元素T top() { return ( *this ) [size() - 1]; } //取顶直接返向量末元素
};栈与递归
在 Windows 等 大部分操作系统中每个运行中的二进制程序都配有一个调用栈call stack或执行栈execution stack。 借助调用栈可以跟踪属于同一程序的所有函数记录它们之间的相互调用关系并保证在每一调用实例执行完毕之后可以准确地返回。
调用栈的基本单位是帧frame。 每次函数调用时都会相应地创建一帧记录该函数实例在二进制程序中的返回地址以及局部变量、传入参数等并将该帧压入调用栈。若在该函数返回之前又发生新的调用则同样地要将与新函数对应的一帧压入栈中成为新的栈顶。函数一旦运行完毕对应的帧随即弹出运行控制权将被交还给该函数的上层调用函数并按照该帧中记录的返回地址确定在二进制程序中继续执行的位置。 在任一时刻调用栈中的各帧依次对应于那些尚未返回的调用实例亦即当时的活跃函数实例。特别地位于栈底的那帧必然对应于入口主函数main()若它从调用栈中弹出则意味着整个程序的运行结束此后控制权将交还给操作系统.
进制转换
进制算法流程 十进制转二进制 使用除2取余法从十进制数中反复除以2将余数记录下来然后将余数从下到上排列起来。 二进制转十进制 从二进制的最右边开始每个位上的数字乘以2的幂然后将结果相加。
void convert ( Stackchar S_int64 n, int base ) { //十进制数n到base进制的转换迭代版)static char digit[] //0 n, 1 base m 16新进制下的数位符号可视base取值范围适当扩充 { 0 1 23 4 , 5, 678, 9ABCDEF);while ( n e ) { //由低到高逐一计算出新进制下的各数位int remainder ( int ) ( n % base ); S.push(digit[remainder] ); //余数当前位)入栈n/ base; //n 更新为其对 base 的除商}
}//新进制下由高到低的各数位自顶而下保存于栈s中main(){Stackchar S; convert(S, n, base); //用栈记录转换得到的各数位while(!S.empty())printf(%c,S.pop()); //逆序输出
}括号匹配
括号匹配的任务是对任一程序块判断其中的括号是否在嵌套的意义下完全匹配简称匹配。 顺序扫描表达式用栈记录已扫描的部分凡遇 (则进栈凡遇 )则出栈。
#include iostream
#include stack
#include stringbool isBracketMatch(const std::string input) {std::stackchar brackets;for (char c : input) {if (c ( || c { || c [) {brackets.push(c);} else if (c ) || c } || c ]) {if (brackets.empty()) {return false; // 括号不匹配没有左括号与右括号匹配}char top brackets.top();brackets.pop();if ((c ) top ! () || (c } top ! {) || (c ] top ! [)) {return false; // 括号不匹配}}}return brackets.empty(); // 所有括号都正确匹配
}int main() {std::string input {[()]};if (isBracketMatch(input)) {std::cout Brackets are matched. std::endl;} else {std::cout Brackets are not matched. std::endl;}return 0;
}
在只有一种括号类型时可以使用计数器起到与栈相同的效果但存在多种括号类型时计数器无法使用。
栈混洗
栈混洗是一个经典的问题涉及到两个栈其中一个栈包含一组数字需要确定是否可以通过一系列栈操作将这些数字从一个初始顺序重新排列成另一个目标顺序。
问题的形式如下
给定两个整数数组一个代表初始栈的顺序另一个代表目标栈的顺序判断是否可以通过以下栈操作将初始栈的元素重新排列成目标栈的顺序 1.将元素从初始栈的顶部移动到输出栈可以看作是出栈操作。 2.将元素从输入栈的底部移动到输出栈可以看作是将输入栈反转后的出栈操作。
如果可以返回 true否则返回 false。
解决这个问题的一种常见方法是使用模拟。可以创建一个辅助栈来模拟操作并按照目标顺序进行操作。具体步骤如下 1.初始化一个辅助栈。 2.遍历目标栈的顺序从左到右 3.如果目标栈的当前元素与初始栈的顶部元素相同直接从初始栈弹出元素。 4.否则从初始栈中弹出元素并将其推入辅助栈直到找到与目标栈当前元素相同的元素。 5.继续遍历目标栈如果辅助栈的栈顶元素与目标栈的当前元素相同则从辅助栈中弹出元素。 6.最后如果初始栈为空并且辅助栈也为空返回 true否则返回 false。
#include iostream
#include stack
#include vectorbool isStackPermutation(const std::vectorint input, const std::vectorint target) {std::stackint initialStack;std::stackint auxStack;for (int num : input) {initialStack.push(num);}for (int num : target) {while (!initialStack.empty() initialStack.top() ! num) {auxStack.push(initialStack.top());initialStack.pop();}if (!initialStack.empty() initialStack.top() num) {initialStack.pop();} else if (!auxStack.empty() auxStack.top() num) {auxStack.pop();} else {return false;}}return initialStack.empty() auxStack.empty();
}int main() {std::vectorint input {1, 2, 3};std::vectorint target {2, 1, 3};if (isStackPermutation(input, target)) {std::cout The permutation is valid. std::endl;} else {std::cout The permutation is not valid. std::endl;}return 0;
}栈混洗计数为 ( 2 n ! ) ( n 1 ) ! n ! c a t a l a n ( n ) \frac{(2n!)}{(n1)!n!} catalan(n) (n1)!n!(2n!)catalan(n)
甄别栈混洗 B B B 是 A A A 的一个栈混洗当且仅当对于任意 1 ≤ i j k ≤ n 1 \leq i j k \leq n 1≤ijk≤nP 中都不包含如下模式 { . . . , k , . . . , i , . . . , j , . . . } \{ ..., k, ..., i, ..., j, ...\} {...,k,...,i,...,j,...}例如{3,1,2}.
中缀表达式求值
思路
将中缀表达式转换为后缀表达式创建一个空栈用于存储操作符。从左到右遍历中缀表达式中的每个字符数字和操作符。如果遇到数字直接输出到输出队列。如果遇到操作符如果栈为空将操作符压入栈。否则比较操作符与栈顶操作符的优先级如果操作符优先级高于栈顶操作符将操作符压入栈。否则弹出栈中较高或相等优先级的操作符并将它们输出到输出队列直到遇到更低优先级的操作符或栈为空然后将当前操作符压入栈。如果遇到左括号(将其压入栈。如果遇到右括号)弹出栈中的操作符并将它们输出到输出队列直到遇到左括号(然后将左括号从栈中弹出但不输出。遍历结束后将栈中剩余的操作符全部输出到输出队列。计算后缀表达式的值创建一个空栈用于存储操作数。从左到右遍历后缀表达式中的每个元素数字和操作符。如果遇到数字将其压入栈。如果遇到操作符从栈中弹出所需数量的操作数通常是两个执行相应的运算然后将结果压入栈。最终栈中将只剩下一个元素即表达式的值。代码实现
#include iostream
#include stack
#include string
#include sstream
#include cctype//返回操作符的优先级优先级越高越早进行计算
int precedence(char op) {if (op || op -) return 1;if (op * || op /) return 2;return 0;
}
//于执行操作符的运算根据不同的操作符执行不同的操作并返回结果
double applyOperator(double operand1, double operand2, char op) {switch (op) {case : return operand1 operand2;case -: return operand1 - operand2;case *: return operand1 * operand2;case /: return operand1 / operand2;default: return 0.0; // 处理未知操作符}
}double evaluateInfixExpression(const std::string expression) {std::stackchar operators;std::stackdouble operands;//operators 用于存储操作符operands 用于存储操作数std::istringstream iss(expression);//创建了一个 std::istringstream 对象将中缀表达式字符串 expression 包装为输入流并准备逐个读取字符串中的标记std::string token;while (iss token) { //程序检查当前标记 token 是数字还是括号。如果是数字包括正数和负数将其转换为 double 类型并压入 operands 栈。如果是左括号 (将其压入 operators 栈。if (isdigit(token[0]) || (token.length() 1 token[0] - isdigit(token[1]))) {double operand std::stod(token);operands.push(operand);}else if (token () {operators.push(();}else if (token )) {//在遇到右括号 ) 时程序将执行一系列操作来处理括号内的表达式。它会弹出操作符直到遇到左括号 (并对括号内的表达式进行计算将结果压入 operands 栈。//如果在遇到左括号之前就遇到了栈空或其他操作符表示右括号没有正确匹配将返回0.0表示错误。while (!operators.empty() operators.top() ! () {char op operators.top();operators.pop();if (operands.size() 2) {// 处理错误操作数不足return 0.0;}double operand2 operands.top();operands.pop();double operand1 operands.top();operands.pop();double result applyOperator(operand1, operand2, op);operands.push(result);}if (!operators.empty() operators.top() () {operators.pop();}else {// 处理错误未匹配的右括号return 0.0;}}else {while (!operators.empty() precedence(operators.top()) precedence(token[0])) {char op operators.top();operators.pop();if (operands.size() 2) {// 处理错误操作数不足return 0.0;}double operand2 operands.top();operands.pop();double operand1 operands.top();operands.pop();double result applyOperator(operand1, operand2, op);operands.push(result);}operators.push(token[0]);}}while (!operators.empty()) {char op operators.top();operators.pop();if (operands.size() 2) {// 处理错误操作数不足return 0.0;}double operand2 operands.top();operands.pop();double operand1 operands.top();operands.pop();double result applyOperator(operand1, operand2, op);operands.push(result);}if (operands.size() ! 1 || !operators.empty()) {// 处理错误操作数和操作符未匹配return 0.0;}return operands.top();
}int main() {std::string infixExpression 2 3 * 4 - 1;double result evaluateInfixExpression(infixExpression);if (result ! 0.0) {std::cout Result: result std::endl;}else {std::cout Invalid expression. std::endl;}return 0;
}当前的操作符比栈顶的操作符优先级低时进行实际的运算。
逆波兰表达式
逆波兰表达式Reverse Polish NotationRPN也称为后缀表达式是一种数学表达式表示法其中操作符在操作数之后。这种表示法消除了括号并且使得表达式的计算顺序更加明确不需要考虑操作符的优先级。
手工转换 假设事先未就运算符之间的优先级关系做出过任何约定 1用括号显式地表示优先级 2将运算符移到对应的右括号后 3抹去所有括号整理。
//原式
( 0 ! 1 ) * 2 ^ ( 3 ! 4 ) - ( 5 ! - 67 - ( 8 9 ) )
//增添足够多的括号
( ( ( ( 0 ) ! 1 ) * ( 2 ^ ( ( 3 ) ! 4 ) ) ) - ( ( ( 5 ) ! - 67 ) - ( 8 9 ) ) )
//各运算符后移使之紧邻于其对应的右括号的右侧
( ( ( ( 0 ) ! 1 ) ( 2 ( ( 3 ) ! 4 ) ) ^ ) * ( ( ( 5 ) ! 67 ) - ( 8 9 ) ) - ) -
//最后抹去所有括号
0 ! 1 2 3 ! 4 ^ * 5 ! 67 - 8 9 - -操作数之间的相对次序在转换前后保持不变而运算符在RPN中所处的位置恰好就是其对应的操作数均已就绪且该运算可以执行的位置。
队列 ADT 及实现
队列像栈一样也是受限的序列 只能在队尾插入查询enqueue() rear() 只能在队头删除查询dequeue() front() 先进先出后进后出。
队列既然属于序列的特列故亦可直接基于向量或列表派生。
