数据结构与算法详解——栈篇（附c++实现代码）

• • 栈的概念
  • 栈的实现
  • 完整代码
  • 时间复杂度分析
  • 栈的应用
  • • 括号匹配
    • 中缀表达式求值

  栈又叫堆栈，是一种运算受限的线性表，只能在表尾进行插入或者删除，表尾这一断也称为栈顶，另一端称为栈底，插入一般称为入栈或者压栈，删除一般称为出栈。栈的特性就是“先进先出”，例如我把1，2先后压栈，出栈的时候必须先弹出2，才能弹出1。
  注意：堆栈就是栈，而不是指堆和栈两种数据结构，还有，操作系统内存中的堆栈和数据结构中的堆栈是两回事。

  栈可以用数组或者链表实现，用数组实现的称为顺序栈，用链表实现的称为链式栈，这里我实现的是顺序栈，主要的操作就是入栈和出栈，注意顺序栈还要支持动态扩容，而链表天然支持动态扩容所以链式栈不用考虑动态扩容。

template
class stack {
public:
	virtual int size() const= 0;	//返回元素个数
	virtual bool empty() const= 0;	//栈是否为空
	virtual void push(DataType data) = 0;	//入栈
	virtual DataType pop() = 0;		//出栈
	virtual DataType top() const= 0;	//返回栈顶元素
};

template
class ArrayStack : public stack {		//注意这里stack也要有DataType
private:
	DataType* array=nullptr;
	int _size = 0;	//实际存储的元素个数
	int capacity = 32;	//申请的空间大小
	int _top = -1;	//栈顶
public:
	ArrayStack();
	ArrayStack(const ArrayStack& as);
	ArrayStack(DataType a[] , int n);
	ArrayStack(std::vector& v);
	~ArrayStack();
	int size() const;
	bool empty() const;
	void push(DataType data) ;
	DataType pop();
	DataType top() const;	
	DataType operator[](int index) const;	//返回值是DataType，所以s[n]只能访问不能修改，后面const让const stack对象也能有一个访问的版本
	void printStack();
private:
	void make_space(int n);	//扩容
};

  这里定义了一个基类stack并用纯虚函数声明了一些必须实现的接口，有子类继承了stack就必须实现这几个接口。operator[]的重载可有可无，但是如果有返回值只能是DataType而不能是DataType&。

template
void ArrayStack::make_space(int n) {
	if (array == nullptr) 
		array = new DataType[capacity];
	
	if (capacity > n)
		return;
	while (capacity < n)
		capacity <<= 1;
	std::cout << "capacity : "< 
  先来看看扩容的函数，代码应该比较清晰，如果已经申请的容量capacity>要申请的容量n就直接返回，否则capacity就一直左移一位（乘2）直到大于等于n，然后重新申请capacity大小的空间，把旧空间的元素复制过去，然后释放旧空间。
 
template
void ArrayStack::push(DataType data) {
	make_space(_size + 1);
	array[++_top] = data;
	++_size;
}

template
DataType ArrayStack::pop() {
	if (_size == 0) 
		throw "stack is empty, no data to pop";
	DataType data = array[_top--];
	--_size;
	return data;
}
 
  入栈和出栈的逻辑也比较简单，需要注意入栈时需要判断是否需要扩容，出栈时需要判断栈是否为空。
 
完整代码 
#ifndef STACK_H
#define STACK_H

#include 
#include 
#include 

template
class stack {
public:
	virtual int size() const= 0;
	virtual bool empty() const= 0;
	virtual void push(DataType data) = 0;
	virtual DataType pop() = 0;
	virtual DataType top() const= 0;
};

template
class ArrayStack : public stack {		//注意这里stack也要有DataType
private:
	DataType* array=nullptr;
	int _size = 0;
	int capacity = 32;
	int _top = -1;
public:
	ArrayStack();
	ArrayStack(const ArrayStack& as);
	ArrayStack(DataType a[] , int n);
	~ArrayStack();
	ArrayStack(std::vector& v);
	int size() const;
	bool empty() const;
	void push(DataType data) ;
	DataType pop();
	DataType top() const;
	DataType operator[](int index) const;	//返回值是DataType，所以s[n]只能访问不能修改，后面const让const stack对象也能有一个访问的版本
	void printStack();
private:
	void make_space(int n);
};

template
ArrayStack::~ArrayStack() {
	delete[] array;
}

template
ArrayStack::ArrayStack(){
	make_space(capacity);
}

template
ArrayStack::ArrayStack(const ArrayStack& as) {
	make_space(as.size());
	for (int i = 0; i < _size; i++)
		array[i] = as[i];	//注意不能写成*this[i]=as[i]，因为operator[]()在声明时返回值是DataType而不是DataType&，所以返回的是右值不能赋值，而这里array[i]是数组所以可以用=赋值
	_size = as.size();
	_top = _size - 1;
}

template
ArrayStack::ArrayStack(DataType a[] , int n) {
	if (a == nullptr)throw "constructor : a[]==nullptr";
	make_space(n);
	for (int i = 0; i < n; i++)
		array[i] = a[i];
	_size = n;
	_top = _size - 1;
}

template
ArrayStack::ArrayStack(std::vector& v) {
	make_space(v.size());
	for (int i = 0; i < v.size(); i++)
		array[i] = v[i];
	_size = v.size();
	_top = _size - 1;
}

template
int ArrayStack::size() const{
	return _size;
}

template
bool ArrayStack::empty() const{
	return _size == 0;
}

template
void ArrayStack::push(DataType data) {
	make_space(_size + 1);
	array[++_top] = data;
	++_size;
}

template
DataType ArrayStack::pop() {
	if (_size == 0) 
		throw "stack is empty, no data to pop";
	DataType data = array[_top--];
	--_size;
	return data;
}

template
DataType ArrayStack::top() const{
	if (_size == 0)throw "stack has no data";
	return array[_top];
}

template
DataType ArrayStack::operator[](int index) const {
	if (index >= _size) {
		std::cerr << "index out of boundn";
		exit(1);
	}
	return array[index];
}
template
void ArrayStack::printStack() {
	for (int i = 0; i <= _top; i++)
		std::cout << array[i] << " ";
	std::cout << "   " << "size : " << _size << std::endl;
}

template
void ArrayStack::make_space(int n) {
	if (array == nullptr) 
		array = new DataType[capacity];
	
	if (capacity > n)
		return;
	while (capacity < n)
		capacity <<= 1;
	std::cout << "capacity : "< 
时间复杂度分析 
  出栈的时间复杂度是O(1)应该没啥问题。
   来看看入栈的时间复杂度，最好的情况下是O(1)，最坏的情况下是O(n)，因为需要动态扩容，涉及到数据的复制。假设原始capacity=n，在入栈n次后才会需要一次扩容变为2n，再入栈n次后才会需要一次扩容变为4n，再入栈2n次后才会需要一次扩容变为8n，以此类推，均摊下去就是O(1)，所以入栈的均摊时间复杂度是O(1)。
 
栈的应用 
括号匹配 
  假设给定字符串只有(),{},[]三种括号，如果字符串里的左括号都能对应右括号返回true否则返回false，注意返回false的三种情况：
 
类似(}这种左右括号不匹配
只有右括号而没有左括号
只有左括号而没有右括号
 
  这里可以用栈实现，遍历字符串，遇到左括号就入栈；遇到右括号就从出栈一个左括号，如果左右括号匹配就继续，如果不匹配或者栈空无法出栈就返回false。
 
#include "stack.h"
#include 
#include 

bool MatchedParis(char l, char r) {		//判断两个括号是否左右匹配
	if ((l == '(' && r == ')') || (l == '{' && r == '}') || (l == '[' && r == ']'))return true;
	return false;
}

bool ExpressionMatchedParis(std::string &str) {
	ArrayStack stack;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == '(' || str[i] == '[' || str[i] == '{')
			stack.push(str[i]);
		else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {
			if (stack.empty())return false;	// 2. 只有右括号而没有左括号
			char c = stack.pop();	//弹出一个左括号
			if (!MatchedParis(c, str[i]))return false;	// 1. 类似(}这种左右括号不匹配
		}
	}
	if (!stack.empty())return false;	//3. 只有左括号而没有右括号
	return true;
}

int main() {
	std::string s1 = "asd({})[asd]{";
	if (ExpressionMatchedParis(s1))
		std::cout << "truen";
	else
		std::cout << "falsen";

	std::string s2 = "asd(})[asd]";
	if (ExpressionMatchedParis(s2))
		std::cout << "truen";
	else
		std::cout << "falsen";
}
 
中缀表达式求值 
  PS:中缀表达式是指运算符在操作数中间，也就是符合我们平时习惯的一种表达式，还有前缀表达式（波兰表达式），后缀表达式（逆波兰表达式），操作符分别在操作数的前面和后面，举个例子，中缀表达式1-2*3，前缀表达式 -1*23，后缀表达式 123*-
   假设表达式只有加减乘除四种运算和括号()，假设结果和中间的操作数都在int类型范围内不会溢出，输入一条中缀表达式求值，例如(34+8)*12+4/(8-6)，求表达式的结果。
   这里我们用两个栈来实现，一个栈存储操作数，一个栈存储操作符。遍历表达式，遇到操作数就压入操作数栈；当遇到操作符的时候，就要与操作符栈的栈顶元素进行比较：
 
如果操作符优先级>栈顶元素，操作符入栈
如果操作符优先级<=栈顶元素，就从操作符栈里取栈顶的操作符，操作数栈里弹出两个操作数，进行运算，将结果压入操作数栈中，然后继续拿这个操作符和栈顶元素比较优先级，直到跳到1这种情况将这个操作符入栈。
 
  实际实现起来还是有一些细节要处理的：
   1、操作数可能是负数：-38+(-8/4)，所以要先对表达式进行预处理，把在负数前添加一个0，变成 0-38+(0-8/4)。
 
void preprocess(std::string &str) {
	for (int i = 0; i < str.length(); i++) 
		if (str[i] == '-') {
			if (i == 0 || str[i - 1] == '(') {	//第一个数是负数，或者带括号的负数
				str.insert(i, 1, '0');	//在位置i前插入1个'0'
				++i;		//注意因为在i前插入一个'0'，str长度会变，i还要再自加一次
			}
		}
}
 
  2、操作数可能不止是一位，可能是多位比如24，但是我们遍历是一个一个字符遍历的，所以这里处理多位的数字，如果这一位是数字，那就判断下一位是否是数字，如果是那就这一位*10+下一位，循环直到下一位不是数字：
 
if (isNum(str[i])) {
	int n = str[i] - '0';
	while ((i + 1) < str.length() && isNum(str[i + 1])) {
		n = n * 10 + (str[i + 1] - '0');
		++i;
	}
	std::cout << "n: " << n << std::endl;
	num.push(n);
	continue;
}
 
  3、其实上面两步的步骤还不完善，比如一开始操作符栈是空时，无法取栈顶元素，因此我们要打个补丁，加多一个判断当栈空时直接插入操作符。但是这里我们直接使用一个哨兵’#‘，在遍历字符串时栈就不会空，就不需要加这个补丁，逻辑就能统一成上面的操作符比较优先级思路。所以在代码中，我们创建了操作符栈后，第一个压入的元素是’#'。
 
ArrayStack ops;
ops.push('#');
 
  4、如何写比较优先级的代码？我们可以把优先级定义在一个map中，然后遍历到操作符时在map里找到优先级大小就可以直接进行比较。
 
std::map priority;
void setPriority() {
	priority['#'] = 0;
	priority['('] = 1;
	priority[')'] = 1;
	priority['+'] = 2;
	priority['-'] = 2;
	priority['*'] = 3;
	priority['/'] = 3;
}
 
  #的优先级最小应该没有问题。可是括号的优先级不是应该是最高的吗？这里需要注意的是左括号(是有两个优先级的，入栈前是4，入栈后是1。为什么呢？
   入栈前也就是在表达式中的优先级，和我们平时的计算一样，括号是优先级最高的，最先计算的。
   入栈后，也就是我们要开始计算括号内的表达式了，这个时候我们单独只看括号及括号内的表达式时，括号的优先级是最低的。
   举个例子：1+(2+3)，在整个表达式中括号(的优先级是最高的，要先算括号内的表达式(2+3)，可是进到括号里面后，+的优先级应该比左括号高，+才能入栈，当遇到右括号时，右括号优先级比+低，才能弹出+计算2+3。或者换个角度说，括号里的+因为括号优先级变得比普通+高了。
   这里priority是用来比较入栈后的操作符的优先级的，所以这里的括号优先级是1，只比哨兵#高（因为哨兵#必须是最低优先级的才有意义）。
   而入栈前的左括号我们单独写一个逻辑，遍历字符串遍历到左括号时，这时未入栈的左括号优先级最高，直接入栈即可。
 
if (priority[str[i]] > priority[ops.top()] || str[i] == '(') {
	ops.push(str[i]);
	break;
}
 
  5、遍历完栈里可能还有没计算完的操作符和操作数，举个例子1+2*3-2:
 
num
ops
分析
1
#
1入栈
1
# +
优先级+>#，+入栈
1 2
# +
2入栈
1 2
# + *
优先级*>#，*入栈
1 2 3
# + *
3入栈
1 6
# +
遍历到减号，优先级-<*，计算2乘3，栈也弹出2、3、*，num入栈结果6
7
#
还是在减号这里，优先级-==+，计算1+6，栈也弹出1、6、+，num入栈结果7
7 2
# -
还是在减号这里，优先级->#，-入栈
  计算到这里后，还有个减号没有计算，这里可以遍历栈依次把栈中剩下的运算符计算完。也可以再加一个哨兵#，因为#比其他运算符优先级都小，所以最后加个#就能把栈中剩余的运算符计算完，逻辑也能统一成上面的操作符优先级比较的两个步骤，这里我们是使用这种方法，所以输入表达式的末尾要带个#。
   接上面最后再加个#
 
num
ops
7 2
# -
最后加个#
5
#
因为优先级#<-，所以计算7-2，并弹出7,2，-，结果5入栈，最后结果就存在num的栈顶
  最后来看完整代码：
 
std::map priority;
void setPriority() {
	priority['#'] = 0;
	priority['('] = 1;
	priority[')'] = 1;
	priority['+'] = 2;
	priority['-'] = 2;
	priority['*'] = 3;
	priority['/'] = 3;
}

void preprocess(std::string &str) {
	for (int i = 0; i < str.length(); i++) 
		if (str[i] == '-') {
			if (i == 0 || str[i - 1] == '(') {	//第一个数是负数，或者带括号的负数
				str.insert(i, 1, '0');	//在位置i前插入1个'0'
				++i;		//注意因为在i前插入一个'0'，str长度会变，i还要再自加一次
			}
		}
}

bool isNum(char c) {
	if (c >= '0' && c <= '9')return true;
	return false;
}


int ExpressionEvaluate(std::string &str) {
	preprocess(str);	//处理负数的情况
	setPriority();
	ArrayStack num;
	ArrayStack ops;
	ops.push('#');
	int left, right, result;

	for (int i = 0; i < str.length(); i++) {
		if (isNum(str[i])) {
			int n = str[i] - '0';
			while ((i + 1) < str.length() && isNum(str[i + 1])) {
				n = n * 10 + (str[i + 1] - '0');
				++i;
			}
			num.push(n);
			continue;
		}
		else if(priority.count(str[i])!=0){
			while (1) {		//注意这里要用while
				if (priority[str[i]] > priority[ops.top()] || str[i] == '(') {
					ops.push(str[i]);
					break;
				}
				else {
						if (ops.top() == '#')
							break;
						if (ops.top() == '(') {
							ops.pop();
							break;
						}
						right = num.top();
						num.pop();
						left = num.top();
						num.pop();
						switch (ops.top())
						{
						case '+':
							result = left + right;
							break;
						case '-':
							result = left - right;
							break;
						case '*':
							result = left * right;
							break;
						case '/':
							if (right == 0)
								std::cout << "除数为0n";
							result = left / right;
							break;
						}
						num.push(result);
						ops.pop();
				}
			}
		}
		else {
			std::cout << "非法表达式" << std::endl;
		}
	}
	return num.top();
}

int main() {
	std::string s1 = "24+(6-3)*10/3#";
	std::cout << ExpressionEvaluate(s1)<