0. 数据结构图文解析系列
数据结构图文解析之：树的简介及二叉排序树C++模板实现.
数据结构图文解析之：AVL树详解及C++模板实现
数据结构图文解析之：二叉堆详解及C++模板实现
数据结构图文解析之：哈夫曼树与哈夫曼编码详解及C++模板实现
1. 栈的基本概念
1.1 栈的特点
栈(Stack)是一种线性存储结构，它具有如下特点：
（1）栈中的数据元素遵守”先进后出"(First In Last Out)的原则，简称FILO结构。
（2）限定只能在栈顶进行插入和删除操作。
1.2 栈的相关概念
- 栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。
- 压栈：栈的插入操作，叫做进栈，也称压栈、入栈。
- 弹栈：栈的删除操作，也叫做出栈。
例如我们有一个存储整型元素的栈，我们依次压栈：{1,2,3}
在压栈的过程中，栈顶的位置一直在”向上“移动，而栈底是固定不变的。
如果我们要把栈中的元素弹出来：
出栈的顺序为3、2、1 ，顺序与入栈时相反，这就是所谓的”先入后出“。
在弹栈的过程中，栈顶位置一直在”向下“移动，而栈底一直保持不变。
如果你玩过一种称为汉诺塔的益智玩具，你就会知道游戏中小圆盘的存取就是一种先进后出的顺序，一个圆柱就是一个栈：
1.3 栈的操作
栈的常用操作为：
- 弹栈，通常命名为pop
- 压栈，通常命名为push
- 求栈的大小
- 判断栈是否为空
- 获取栈顶元素的值
2. 栈的实现
2.1 栈的抽象数据类型
栈提供了如上所述操作的相应接口。
template<typename T> class ArrayStack { public: ArrayStack(int s = 10); //默认的栈容量为10 ~ArrayStack(); public: T top(); //获取栈顶元素 void push(T t); //压栈操作 T pop(); //弹栈操作 bool isEmpty(); //判空操作 int size(); //求栈的大小 private: int count; //栈的元素数量 int capacity; //栈的容量 T * array; //底层为数组 };
说明：
- count 为栈的元素数量，capacity为栈的容量，count<=capacity，当栈满的时候，count = capacity。
- 本实现中不支持栈的动态扩容，栈满的时候无法再插入元素。栈的容量在定义栈的时候就需要指定，默认的栈容量为10。
2.2 栈的常见分类
（1）基于数组的栈实现——以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向
（2）基于单链表的栈实现——以链表为底层的数据结构时，以链表头为栈顶，便于节点的插入与删除，压栈产生的新节点将一直出现在链表的头部。
2.3 实例分析
使用标准库的栈时, 应包含相关头文件，在栈中应包含头文件： #include< stack > 。定义：stack< int > s;
s.empty(); //如果栈为空则返回true, 否则返回false; s.size(); //返回栈中元素的个数 s.top(); //返回栈顶元素, 但不删除该元素 s.pop(); //弹出栈顶元素, 但不返回其值 s.push(); //将元素压入栈顶
（1）基于数组的栈
#include <stack> #include <iostream> using namespace std; int main() { stack<int> mystack; int sum = 0; for (int i = 0; i <= 10; i++){ mystack.push(i); } cout << "size is " << mystack.size() << endl; while (!mystack.empty()){ cout << " " << mystack.top(); mystack.pop(); } cout << endl; system("pause"); return 0; } //size is 11 // 10 9 8 7 6 5 4 3 2 1 0
（2）基于单链表的栈
#include <iostream> using namespace std; template<class T>class Stack { private: struct Node { T data; Node *next; }; Node *head; Node *p; int length; public: Stack() { head = NULL; length = 0; } void push(T n)//入栈 { Node *q = new Node; q->data = n; if (head == NULL) { q->next = head; head = q; p = q; } else { q->next = p; p = q; } length++; } T pop()//出栈并且将出栈的元素返回 { if (length <= 0) { abort(); } Node *q; int data; q = p; data = p->data; p = p->next; delete(q); length--; return data; } int size()//返回元素个数 { return length; } T top()//返回栈顶元素 { return p->data; } bool isEmpty()//判断栈是不是空的 { if (length == 0) { return true; } else { return false; } } void clear()//清空栈中的所有元素 { while (length > 0) { pop(); } } }; int main() { Stack<char> s; s.push('a'); s.push('b'); s.push('c'); while (!s.isEmpty()) { cout << s.pop() << endl; } system("pause"); return 0; }
3. 真题练习
练习1 返回栈中最小元素
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
解法参考博客：设计一个有getMin功能的栈（C++版），具体过程如下：
（1）使用两个栈，一个栈用来保存当前的元素，记做：stackData，一个栈用来保存压入操作每一步的最小元素，记做：stackMin。
（2）入栈：当stackData栈中压入一个数据时，判断satckMin中是否为空。若为空，将该元素压入stackMin栈中。若不空，判断两者之间的大小，当前者小于或等于后者时，将前者中的数据压入后者中；当前者大于后者时，不进行任何操作。
（3）出栈：保证stackMin中栈顶的元素是stackData中最小的。
#include<iostream> #include <stack> #include <cassert> using namespace std; //方法一： 一个辅助栈，如果这个栈为空，直接将元素入这个栈，如果辅助栈中有元素，将压入的元素和辅助栈顶元素比较， //压入两者中较小的那个元素使得辅助栈总是维持栈顶元素为最小值。 //class Stack //{ //public: // void Push(int data) // { // stackData.push(data); // if (stackMin.empty()) // { // stackMin.push(data); // } // else // { // int tmp = stackMin.top(); // int min = data > tmp ? tmp : data; // stackMin.push(min); // } // } // // void Pop() // { // assert(!stackData.empty() && !stackMin.empty()); // stackData.pop(); // stackMin.pop(); // } // // int GetMin() // { // assert(!stackMin.empty()); // return stackMin.top(); // } // //private: // stack<int> stackData; // stack<int> stackMin; //}; //方法二： 一个辅助栈，如果这个栈为空，直接将元素入这个栈，如果辅助栈中有元素，将压入的元素和辅助栈顶元素比较， //如果压入的元素小于等于辅助栈顶元素，者将这个元素入辅助栈，否则无操作，出栈的时候判断要出栈的元素是否等于辅助 //栈顶元素，如果是，也将辅助栈顶元素出栈。否则无操作。 class Stack { public: void Push(int data) { stackData.push(data); if (stackMin.empty()) { stackMin.push(data); } else { if (data <= stackMin.top()) { stackMin.push(data); } } } void Pop() { assert(!stackData.empty() && !stackMin.empty()); if (stackData.top() == stackMin.top()) { stackMin.pop(); } stackData.pop(); } int GetMin() { assert(!stackMin.empty()); return stackMin.top(); } private: stack<int> stackData; stack<int> stackMin; }; int main() { Stack s; //s.Push(5); s.Push(36); s.Push(15); s.Push(95); s.Push(50); s.Push(53); cout << s.GetMin() << endl; system("pause"); return 0; }//15
（3）栈的应用举例
1）进制转换
2）括号匹配的检验
3）行编辑程序
4）迷宫求解、汉诺塔等经典问题
5）表达式求值
6）栈与递归的实现
练习2 剑指offer面试题30——包含min函数的栈
参考链接：包含min函数的栈
题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
class Solution { public: stack<int> stackData;//保存数据用的栈stackData stack<int> stackMin;//保存最小的数的栈stackMin，其中它的栈顶始终为最小的数 void push(int value) { stackData.push(value); if(stackMin.empty()) stackMin.push(value);//如果stackMin为空，则value是最小的值，入栈 else{ if(stackMin.top()>=value) stackMin.push(value);//否则当value小于等于stackMin的栈顶元素时，入栈（等于的时候也入栈是因为我考虑有相同的数） } } void pop() { if(stackData.top()==stackMin.top())//如果出栈的数刚好是最小的数，那么stackMin也应该出栈 stackMin.pop(); stackData.pop(); } int top() { return stackData.top();//栈顶元素应返回stackData的栈顶元素 } int min() { return stackMin.top();//stackMin的栈顶元素即是最小的数 } };
运行结果：
练习3 剑指offer面试题31——栈的压入、弹出序列
参考博客：剑指offer题解C++【21】栈的压入、弹出序列，解题思路为：创建一个栈进行压入、弹出操作。具体操作如下：
（1）当栈为空或者栈顶元素和popV当前元素不相等时，将pushV当前元素压入；
（2）当栈顶元素与popV当前元素相等时，将栈顶元素弹出，并移至popV下一个元素；
（3）如果需要压入的元素个数大于pushV的元素个数，说明popV不可能是pushV的弹出序列。
代码为：
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { //特殊输入测试 if(pushV.empty() || popV.empty() || pushV.size()!=popV.size()) return false; stack<int> mystack;//定义一个辅助栈 int index=0; for(int i=0;i<popV.size();i++){ //当辅助栈为空或者栈顶元素和popV当前元素不相等时，将pushV当前元素压入 while(mystack.empty()||mystack.top()!=popV[i]){ if(index>=pushV.size()) //如果需要压入的元素个数大于pushV的元素个数，说明popV不可能是pushV的弹出序列 return false; mystack.push(pushV[index++]); } //当栈顶元素与popV当前元素相等时，将栈顶元素弹出，并移至popV下一个元素 if(mystack.top()==popV[i]) mystack.pop(); } return true; } };
运行结果：
当然可以利用其他思想解决，如引入哈希或直接利用向量的方式求解。
class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { if(pushV.empty() && popV.empty() && pushV.size() != popV.size()){ return false; } map<int,int> Hash; //用map做一个映射，入栈顺序的值不一定是递增 for(int i=0;i<pushV.size();i++){ Hash[pushV[i]]=i+1; } int now=Hash[popV[0]]; //当前最靠后入栈的键值，例如题目给的4 3 5 1 2，now先等于4，再等于5 for(int i=0;i<popV.size();i++){ //如果入栈序列中没有这个值 if(Hash[popV[i]]==0){ return false; } if(Hash[popV[i]]>=now){ now=Hash[popV[i]]; } else if(Hash[popV[i]]<=Hash[popV[i-1]]){ continue ; } else{ return false; } } return true; } };
练习4 简单的括号匹配判断
例如，爱奇艺的一道实习在线编程题：当输入为（）（（））（），返回true；当输入为）（）（）（）（）），返回false，时间15min。（不能使用栈）
1、假设可以使用栈（15min可以完成）
C++代码：
#include <iostream> #include <stack> #include <vector> using namespace std; bool isRight(vector<char> &vec){ stack<char> stack1; bool index = false; if (vec.size() <= 1 || vec[0]!='(' || vec.size()%2!=0){ return index; } for (int i = 0; i < vec.size(); i++){ if (vec[i] == '(') stack1.push(vec[i]); else if (vec[i] == ')') stack1.pop(); } if (stack1.empty()) index = true; return index; } int main(){ //输入不定长的括号 vector<char> vec; char tmpCh; char t; cout << "输入一串括号为："; do{ cin >> tmpCh; vec.push_back(tmpCh); } while ((t = cin.get()) != '\n'); //调用isRight函数 bool myRes = isRight(vec); cout << myRes << endl; system("pause"); return 0; }
运行结果：
python代码：
def isRight(str1): index = False tmp = [] if(len(str1)>=2 and len(str1)%2==0 and str1[0]=='('): for id in range(len(str1)): if str1[id] == '(': tmp.append(str1[id]) else: tmp.pop() if len(tmp)==0: index = True return index if __name__ == "__main__": try: while True: str1 = [i for i in input().split()] print(isRight(str1)) # 返回判断结果 except: pass
运行结果：
2、不能使用栈（15min，不太好想，笔试那会儿就没想到！）
以下是具体的过程如下：（1）由于不能使用栈，将左括号定义为数值1，右括号定义为数值-1，存放到向量id（C++）或列表tmp （Python）中；（2）初始化变量sum，用于判断总的求和结果是否等于0，若不等于0，则肯定不正确，若等于0，不一定正确；（3）循环遍历输入的括号向量vec，判断当前括号属性的同时，进行累加求和，如果求和值小于等于-1，break（跳出循环）；（4）最后再检查sum是否等于0，此时若等于0，则为正确。
C++代码：
#include <iostream> #include <vector> using namespace std; bool isRight(vector<char> &vec){ vector<int> id(vec.size()); //用于存放左右括号的属性：左括号用1表示，右括号用-1表示 int sum = 0; bool index = false; if (vec.size() <= 1 || vec[0]!='(' || vec.size()%2!=0){ return index; } for (int i = 0; i < vec.size(); i++){ if (vec[i] == '('){ id.push_back(1); sum = id[i] + sum; } else if (vec[i] == ')'){ id.push_back(-1); sum = id[i] + sum; if (sum <= -1) break; } } if (sum == 0) index = true; return index; } int main(){ //输入不定长的括号 vector<char> vec; char tmpCh; char t; cout << "输入一串括号为："; do{ cin >> tmpCh; vec.push_back(tmpCh); } while ((t = cin.get()) != '\n'); //调用isRight函数 bool myRes = isRight(vec); cout << myRes << endl; system("pause"); return 0; }
运行结果同上
python代码：
def isRight(str1): index = False sum = 0 tmp = [] if(len(str1)>=2 and len(str1)%2==0 and str1[0]=='('): for id in range(len(str1)): if str1[id] == '(': tmp.append(1) sum += tmp[id] else: tmp.append(-1) sum += tmp[id] if sum<=-1: break if sum == 0: index = True return index if __name__ == "__main__": try: while True: str1 = [i for i in input().split()] print(isRight(str1)) # 返回判断结果 except: pass
运行结果同上。
最后奉上`数据结构与算法之美`专栏中的精彩文章
