数据结构与算法 4. 栈与队列 2021-07-06 浏览量 583 暂无评论 [TOC] ## 4.1 接口与实现 特殊的线性结构。 push, top, pop 实现:借助向量或列表 ```cpp class Stack: public Vector { public: void push(T const & e) {insert(size(), e);} T pop() {return remove(size() - 1);} T & top() {return (*this)[size() - 1];} }; ``` 应用场合 - 逆序输出 - 递归嵌套 - 延迟缓冲 - 栈式计算 ## 4.2 逆序输出--进制转换 商+余数,逆序输出余数 ```cpp void convert( Stack & S, __init64 n, int base) { static char digit[] = {'0', '1', '2', '3', '4', '5', '6', '7'}; while (n > 0) { S.push(digit[n % base]); n /= base; } } main() { Stack S; convert(S, n, base); while (!S.empty()) printf("%c", S.pop()); } ``` ## 4.3 递归嵌套--括号匹配 ```cpp // 假设只有(),没有其他字符 bool paren(const char exp[], int lo, int hi) { Stack S; for (int i = lo; i < hi; i++) if ('(' == exp[i]) S.push(exp[i]); else if (!S.empty()) S.pop(); else return false; // 右括号缺失对应的左括号 return S.empty(); // 左括号缺失对应的右括号 } ``` 可扩展至多种类型括号,在弹出时检查当前右括号是否与栈顶的左括号匹配。 ## 4.4 栈混洗 按某种顺序,移动栈中的元素。 只允许: - 将A的顶元素弹出并压入S - 将S的顶元素弹出并压入B **计数** 一个长度为n的栈的栈混洗总数为$SP(n)=\sum_{k=1}^{n}{SP(k-1)xSP(n-k)}=catalan(n)$ ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210706093301949.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) **如何判断一个排列是否为一个序列的栈混洗:** 观察:任意三个元素能否按某相对次序出现与混洗中,与其他元素无关。 > 对于任何$1<=i 第一个是从顶到底,第二个是从底到顶,因为这样一来,栈底元素相同,只能有一种顺序 1. 枚举并判断i,j,k,$O(n^3)$ 2. 枚举并判断i,j,j+1,$O(n^2)$ 3. 利用栈,$O(n)$ 模拟混洗过程,每次S.pop()之前,检测S是否已空;或需弹出的元素在S中,却非顶元素。 ```python for k in B: while (S.empty() or k!=S.top()): if A.empty(): return False S.push(A.pop()) if (k in S) and (k!=S.top()): return False return True # 更正 while len(A) > 0: S.append(A.pop()) if B[0] in S and S[-1] != B[0]: print(False) while len(S) > 0 and S[-1] == B[0]: S.pop() B.pop(0) print(True) ``` **合法的栈混洗与合法的括号匹配存在一一对应关系。** ![在这里插入图片描述](https://img-blog.csdnimg.cn/202107061058285.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) ## 4.5 延迟缓冲--中缀表达式 不能保证处理的速度和读取的速度同步,所以要缓冲。 求值算法 = 栈 + 线性扫描 两个栈:一个栈用来存放操作数,一个栈用来存放操作符 ```cpp float evaluate(char* S, char*& RPN) { stack opnd; stack optr; optr.push('\0'); while (!optr.empty()) { if (isdigit(*S)) {readNumber(S, opnd); append(RPN. opnd.top();} else switch (orderBetween(optr.top(), *S)) { case '<': optr.push(*S); S++; break; case '=': optr.pop(); S++; break; case '>': { char op = optr.pop(); append(RPN, op); if ('!' == op) opnd.push(calcu(op, opnd.opo())); else { float p0pnd2 = opnd.pop(), p0pnd1 = opnd.pop(); opnd.push(calcu(p0pnd1, op, p0pnd1)); // why not opnd.push(calcu(opnd.pop(), op, opnd.pop())); // 顺序问题 } break; } default: exit(-1); } } return opnd.pop(); } void readNumber(char* & p, stack& stk) { stk.push((float)(*p - '0')); while (isdigit(*(++p))) stk.push(stk.pop() * 10 + (*p - '0')); if ('.' != *p) return; float fraction = 1; while (isdigit(*(++p))) stk.push(stk.pop() + (*p - '0') * (fraction /= 10)); } Operator optr2rank ( char op ) { //由运算符转译出编号 switch ( op ) { case '+' : return ADD; //加 case '-' : return SUB; //减 case '*' : return MUL; //乘 case '/' : return DIV; //除 case '^' : return POW; //乘方 case '!' : return FAC; //阶乘 case '(' : return L_P; //左括号 case ')' : return R_P; //右括号 case '\0': return EOE; //起始符与终止符 default : exit ( -1 ); //未知运算符 } } char orderBetween ( char op1, char op2 ) //比较两个运算符之间的优先级 { return pri[optr2rank ( op1 ) ][optr2rank ( op2 ) ]; } ``` ## 4.6 逆波兰表达式(Reverse Polish Notation) 又称为后缀式。 不使用括号,即可表示带优先级的运算关系。 infix到postfix手工转换 操作数的相对位置不会改变,操作符的相对位置可能改变。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/2021070616150694.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NzkyOTU5,size_16,color_FFFFFF,t_70) 代码实现结合evaluate,只在两种情况下将当前字符添加至RPN末尾: 1. 数字 2. 当前操作符可立即执行 ## 4.7 队列接口与实现 队尾插入(查询):enqueue、rear 队头删除(查询):dequeue、front ```cpp template class Queue: public List { public: void enqueue(T const & e) {insertAsLast(e);} T dequeue() {return remove(first());} T & front() {return first()->data;} T & rear() {return last()->data;} } ``` 赞赏 微信支付 支付宝支付