数据结构精讲：栈、队列与后缀表达式

"数据结构笔记.md" 这篇笔记主要涵盖了数据结构中的栈和队列概念，以及它们在实际问题中的应用。栈是一种具有“后进先出”（LIFO）特性的数据结构，常用于括号匹配、表达式求值等问题。队列则是一种“先进先出”（FIFO）的数据结构。 ### 栈 栈是一种特殊类型的线性表，其特点在于插入和删除操作只在表的一端进行，这一端被称为栈顶。栈的操作通常包括压栈（元素进入栈顶）和弹栈（元素从栈顶移除）。在程序设计中，栈的应用非常广泛，例如： #### 顺序栈 顺序栈是通过数组实现的栈，当栈满时需要进行扩容。下面是一个C++实现的顺序栈扩容示例： ```cpp template<class T> void SeqStack<T>::overflowProcess() { T* newArray = new T[maxSize + stackIncrement]; if (newArray == NULL) { cerr << “存储分配失败！” << endl; exit(1); } for (int i = 0; i <= top; i++) newArray[i] = elements[i]; maxSize = maxSize + stackIncrement; delete[] elements; elements = newArray; } ``` 这段代码展示了如何动态创建一个更大的数组来扩展栈的容量，并将原数组中的元素复制到新数组中。 #### 括号匹配 栈可以用于括号匹配问题，例如C++代码所示： ```cpp void printmatchpairs(string s) { stack<string> sta(s); int j, length = s.size(); for (int i = 1; i < length; i++) { if (s[i] == '(') sta.push_back(s[i]); else if (s[i] == ')') { if (sta.pop(j) == true) // 栈不空,且将左括号退出 cout << j << "匹配" << i << endl; else cout << "无匹配的"; } } while (!sta.empty()) { // 还有空的 s.pop(j); cout << "没有与j匹配的括号"; } } ``` 这个函数使用栈来检查字符串中的括号是否匹配，遇到左括号就压栈，遇到右括号则尝试弹栈匹配，如果栈为空或者找不到匹配的左括号，则输出错误信息。 ### 后缀表达式（逆波兰表达式） 后缀表达式是一种方便计算的表达式形式，其中运算符位于操作数之后。下面是一个简单的后缀表达式计算器的实现： ```cpp void Calculator::Run() { char ch; double newOperand; while (cin >> ch, ch != '#') { switch (ch) { case '+': case '-': case '*': case '/': DoOperator(ch); break; // 计算 default: cin.putback(ch); // 将字符放回输入流 cin >> newOperand; // 读操作数 AddOperand(newOperand); // 操作数入栈 } } } void Calculator::DoOperator(char op) { double left, right, value; bool result; result = Get2Operands(left, right); // 取得两个操作数 // 根据运算符计算并更新栈顶元素 } ``` `Calculator::Run()`方法处理用户输入的后缀表达式，遇到操作符时调用`DoOperator()`进行计算，遇到操作数则压栈。这样可以避免优先级和括号的困扰，简化表达式求值的过程。 以上就是数据结构笔记中关于栈和后缀表达式的部分，这些基础知识在算法和编程中都有着广泛的应用。