数据结构-3-4.栈与队列

写在前面

本篇文章整理《数据结构(C++语言版)》关于栈与队列这种线性结构知识点。

后进先出(LIFO)是栈这种结构最大的特点。对栈而言,只有一端的可访问称作,顶端top。
栈结构示意及基础功能
栈也是一种线性结构,即满足逻辑地址连续,故可直接基于向量或列表派生。

1
2
3
4
5
6
7
8
//基于vector结构的栈初始化
template<typename T>
class Stack: public Vector<T>{
public:
void push(T const& e) { insert( size(), e);} //入栈,等效于作为向量末元素插入
T pop() { return remove( size() -1); } //出栈,等效于删除向量末元素
T& top() { return ( *this ) [ size() - 1 ]; } //取顶,直接返回向量的末元素
};

栈应用

基于栈结构的应用,就是要充分利用其后进先出LIFO的特性。

括号匹配

解决问题:判断一个只含括号的表达式是否匹配。
算法:从表达式左侧开始扫描,当扫描到左括号(则压入栈中,若扫描到右括号)则弹出栈顶元素,继续扫描下去。当且仅当最后扫描完成时,栈类所有左括号(均已弹出,栈为空栈时该表达式括号匹配。
括号匹配算法示意图
代码实现

1
2
3
4
5
6
7
8
9
bool paren( char exp[], int lo, int hi ) { //exp[lo, hi)
Stack<char> 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();
}

TIPS:字符串与字符数组
字符串以空字符\0结尾,用来标记字符串的结尾。
char dog[4] = {‘a’, ‘b’, ‘c’, ‘d’}; //不是字符串,是char数组
char cat[4] = {‘a’, ‘b’, ‘c’, ‘\0’}; //是字符串,也是char数组
另一种操作方法是通过双引号声明字符串,若声明长度比实际长度长,则空字符将自动补全到实际长度之后
char bird[5] = “abc”; //实际为 abc\0\0
char bird[] = “abc”; //编译器自己判断字符串长度

栈混洗甄别

解决问题:将栈A中的元素通过栈S转移入栈B中。对元素的移入移出操作只允许以入栈出栈方式。进而判断栈B中元素序列是否是一种栈混洗。
栈混洗
算法:不妨设栈A的元素为升序排列。对栈B中第i个元素,当其从栈S弹出前,S栈顶端以下元素按降序排列。即,若栈S顶元素小于B[i],则依次将A中元素入栈;若栈S顶元素等于B[i],则S出栈,继续判断B[i+1];若栈S顶元素大于B[i],则不是栈混洗
该算法的一个典型应用场景为火车调度问题。
代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
判断栈B中序列是否为一种栈混洗
为了简化问题,栈A、B元素确定,因此可以通过数组等方式实现。
/*
int A = 1;
int B[] = {2, 3, 1, 4, 5};
bool Stackverfi(int A, const int* array_B){
Stack<int> S;
for(int i = 0; i < 5; i++){
while( S.top() < B[i] ){
S.push(A++);
std::cout << "push\n";
}
if( S.top() == B[i] ){
S.pop();
std::cout << "pop\n";
}
else{
std::cout << "NO!!!";
return false;
}
}
}

中缀表达式

算法:对于一个正确的算数表达式,先准备两个栈A,B分别用于存储运算符和运算数。扫描到运算数,则入栈A中;扫描到运算符时,与栈B的栈顶运算符比较,若栈顶运算符优先级较低,则入栈;若栈顶运算符优先级较高,则弹出栈B顶运算符,弹出栈A两个运算数(若为单元素操作符,只弹出一个元素),将运算结果压入栈A
采用一个栈结构的算法实例

队列

队列的特性与栈结构正好相反,其主要性能是先进先出(FIFO)。具体实现方式与栈结构类似,这里不过多叙述。

本文标题:数据结构-3-4.栈与队列

文章作者:Lumo Wang

发布时间:2018年03月05日 - 14:03

最后更新:2018年11月07日 - 15:11

原始链接:https://luameows.github.io/2018/03/05/学习笔记-数据结构-3-4-栈与队列/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我喝杯咖啡,我会继续熬夜的~