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