"数据结构笔记.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()`进行计算，遇到操作数则压栈。这样可以避免优先级和括号的困扰，简化表达式求值的过程。
以上就是数据结构笔记中关于栈和后缀表达式的部分，这些基础知识在算法和编程中都有着广泛的应用。
我的内容管理
展开
