数据结构之栈

栈的顺序存储实现

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <iostream>
using namespace std;

#define Stack_Init_Size 100
#define StackIncrement 10
typedef int SElemType;

typedef struct{
	SElemType *top;
	SElemType *base;
	int stacksize;
}SqStack;

int InitStack(SqStack &s){
	//栈的初始化
	s.base = (SElemType *)malloc(Stack_Init_Size * sizeof(SElemType));
	if (!s.base) exit(-1);	//存储分配失败
	s.top = s.base;
	return 1;
}

int GetTop(SqStack s, SElemType &e){
	//获取栈顶元素
	if (s.base == s.top) return -1;		//栈为空
	e = *(s.top - 1);
	return 1;
}

int Push(SqStack &s, SElemType e){
	//插入元素e
	if (s.top - s.base >= s.stacksize){
		s.base = (int *)realloc(s.base, (s.stacksize + StackIncrement) * sizeof(int));
		if (!s.base) exit(-1);	//存储分配失败
		s.top = s.base + StackIncrement;
		s.stacksize += StackIncrement;
	}
	*s.top++ = e;
	return 1;
}

int Pop(SqStack &s, SElemType &e){
	//删除栈顶元素
	if (s.base == s.top) return -1;		//栈为空
	e = *--s.top;
	return 1;
}

void printStack(SqStack s){
	if (s.base == s.top) printf("栈为空！\n");
	int *t = s.base;
	printf("当前栈的元素为：\n");
	while(t < s.top){
		printf("%d ", *t);
		t++;
	}
	printf("\n");
}

int main(){
	SqStack s;
	InitStack(s);
	int e;
	for(int i = 1; i <= 10; i++)
		Push(s, i);
	printStack(s);
	printf("删除栈顶元素----\n");
	Pop(s, e);
	printStack(s);
	return 0;
}

运行结果:

当前栈的元素为：
1 2 3 4 5 6 7 8 9 10
删除栈顶元素----
当前栈的元素为：
1 2 3 4 5 6 7 8 9
Hit any key to close this window...

栈的应用：进制转换

void conversion(){
	//进制转换，转8进制，可以自根据需要改相应的进制
	SqStack s;
	InitStack(s);
	int n, e;
	scanf("%d",&n);	//输入十进制的数
	printf("%d的8进制为: ", n);
	while(n){
		Push(s, n % 8);
		n /= 8;
	}
	while(s.base != s.top){
		Pop(s, e);
		printf("%d",e);
	}
	printf("\n");
}

栈的应用：括号匹配

如([]())这种是匹配的，([)(])这种是不匹配的
算法：每读入一个左括号，把它进行压栈，后压的元素总比前面的元素优先级高（正好
和栈的后进先出对应），每读入一个右括号，把它和栈顶元素进行匹配，若是相同类型
，则删除栈顶元素然后继续匹配，若不匹配，则返回false。最后匹配完成后，如果栈
为空，则成功配对，否则也配对失败

bool check(char *str){
	SqStack s;
	InitStack(s);
	int len = strlen(str);
	for(int i = 0; i < len; i++){
		char x = str[i];
		int e;
		switch(x){
			case '(':
			case '[':
				Push(s, x);
				break;
			case ')':
				Pop(s, e);
				if (e != '(')
					return false;
				break;
			case ']':
				Pop(s, e); 
				if (e != '[')
					return false;
				break;
		}
	}
	if (s.base == s.top) return true;//匹配完所有括号最后要求栈中为空
	return false;
}

栈的应用：表达式求值

表达式分为两种(前缀表达式和后缀类似，就不介绍了)：

中缀表达式：A+B(C-D)-E/F, 例如9+(3-1)3+10/2
后缀表达式：ABCD-+EF/-, 例如9 3 1 - 3 * + 10 2 / +

其中中缀表达式是人们日常使用的形式，然而计算机喜欢的是后缀表达式，因为计算机
可以很轻松地通过栈来计算后缀表达式的值。
后缀表达式计算规则：

从左到右扫描表达式的每个数字和符号，遇到数字就进栈
，遇到符号就将处于栈顶的两个数字出栈然后跟这个符号进行运算，最后将计算结果进
栈，直到最终获得结果.

下面举例后缀表达式9 3 1 - 3 * + 10 2 / +计算过程:

首先读取到9，3，1三个数字，分别进栈，然后读取到-号，1和3出栈，并计算3-1
的结果2进栈，此时栈里变成了9，2。然后读取到3并进栈，读取到*, 2和3出栈并计算
2*3的结果进栈，此时栈里变成了9，6。读取到+, 9和6出栈，计算9+6的结果进栈。
此时栈里变成了15。然后10，2进栈，读取到/, 10和2出栈并计算10/2的结果然后进栈
，此时栈里变成了15，5。读取到+,15和5出栈，计算15+5的值并进栈，最后栈里只剩1
个元素，就是该表达式的值

中缀表达式转换后缀表达式的方法：

按运算符优先级对所有运算符和他的运算数加括号
把运算符移到对应的括号后
去掉括号