c++数据结构之栈

一、栈的定义栈（Stack）是由有限个数据类型相同元素组成的有序集合，对元素的操作只能在栈顶进行，遵循后进先出（Last In，First Out）的原则，其相关运算有创建空栈、判空、判满、入栈、出栈等。二、栈的ADT数据：有限个数据类型相同元素所组成的有序集合，用top纪录栈顶元素的位置。运算：Create()：创建一个空栈。IsEmpty()：若栈空，则返回1，否则返回0。IsFull()：若

@菜鸟一枚

11487人浏览 · 2021-09-22 09:21:59

@菜鸟一枚 · 2021-09-22 09:21:59 发布

一、栈的定义

栈（Stack）是由有限个数据类型相同元素组成的有序集合，对元素的操作只能在栈顶进行，遵循后进先出（Last In，First Out）的原则，其相关运算有创建空栈、判空、判满、入栈、出栈等。

二、栈的ADT

数据：
有限个数据类型相同元素所组成的有序集合，用top纪录栈顶元素的位置。
运算：
Create()：创建一个空栈。
IsEmpty()：若栈空，则返回1，否则返回0。
IsFull()：若栈满，则返回1，否则返回0。
Push()：让某元素入栈。
Pop()：让栈顶元素出栈。
Display()：输出栈元素

三、栈的数组实现

栈可以用数组来实现，定义数组data[MaxSize]用来存储栈元素，MaxSize是允许的最大容量，用变量top纪录栈顶元素的位置，top=-1表示空栈，这种栈称为顺序栈（Sequence Stack），用S或其它大写英文字母来表示。

#include<iostream>
using namespace std;
#define MaxSize 100//栈的最大容量
//顺序栈定义
struct SeqStack
{
	int data[MaxSize];//存放栈元素的数组
	int top;//栈顶指针
};
//创建空栈
void Create(SeqStack &S)
{
	S.top = -1;
}
//判空
int IsEmpty(SeqStack S)
{
	if (S.top == -1) return 1;
	else return 0;
}
//判满
int IsFull(SeqStack S)
{
	if (S.top >= MaxSize - 1) return 1;
	else return 0;
}
//入栈
void Push(SeqStack &S, int x)
{
	if (IsFull(S))//如果栈满
	{
		cout << "栈满,无法入栈" << endl;
		return;//什么都不做
	}
	S.data[++S.top] = x;//x入栈
}
//出栈
void Pop(SeqStack &S, int &x)
{
	if (IsEmpty(S))//如果栈空
	{
		cout << "栈空,无法出栈" << endl;
		return;//什么都不做
	}
	x = S.data[S.top--];//栈顶元素值赋给x后出栈
}
//输出顺序栈
void Display(SeqStack S)
{
	if (IsEmpty(S))
	{
		cout << "栈空,无元素输出" << endl;
		return;//什么都不做
	}
	int i = S.top;//定义循环控制变量i,让i取栈顶位置
	while (i >= 0)
		cout << S.data[i--] << " ";//输出栈中元素
	cout << endl;
}
//主函数
void main()
{
	SeqStack S;//定义栈
	Create(S);//创建空栈
	Push(S, 1);//入栈
	Push(S, 2);//入栈
	Display(S);
	int x;
	Pop(S, x);//出栈
	Display(S);
	Push(S, 3);//入栈
	Display(S);
}

四、栈的链表实现

顺序栈是用数组来存储栈中元素，由于数组的大小需事先声明，一般会将数组的存储空间预设的大一些，这有可能会造成内存空间的浪费。
利用链表来创建栈，可以克服顺序栈的这一缺点，一般将用链表创建的栈称之为链栈。链栈的优点是可以动态改变链表长度，不存在判别栈满的问题。由于链栈应遵循后进先出的原则，创建链栈时，应采用前插法来创建。

#include<iostream>
using namespace std;
//结点定义
struct Node
{
	int data;//数据域
	Node *next;//指针域
};
//链栈定义
struct LinkStack
{
	Node *top;
};
//创建空链栈
void Create(LinkStack &S)
{
	S.top = NULL;
}
//判空
int IsEmpty(LinkStack S)
{
	if (S.top == NULL) return 1;
	else return 0;
}
//入栈
void Push(LinkStack &S, int x)
{
	Node *NewNode;//新结点
	NewNode = new Node;//新结点申请内存
	NewNode->data = x;//新结点数据域赋值
	NewNode->next = NULL;//新结点指针域赋值
	if (IsEmpty(S))//如果链栈为空
		S.top = NewNode;//链栈顶指针指向新结点
	else//如果链栈非空
	{
		NewNode->next = S.top;//新结点前插入链栈
		S.top = NewNode;//更新栈顶指针
	}
}
//出栈
void Pop(LinkStack &S, int &x)
{
	if (IsEmpty(S))
	{
		cout << "栈空,无法出栈" << endl;
		return; //什么都不做
	}
	Node *p = S.top;//定义探测指针p并指向栈顶结点
	if (p->next == NULL)//如果链栈仅含一个结点
	{
		x = p->data;//获取栈顶结点值
		S.top = NULL;//置链栈为空
		delete p;//删除原栈顶结点
	}
	else//如果链栈中至少含有两个结点
	{
		x = p->data;//获取栈顶结点值
		S.top = S.top->next;//栈顶指针后移
		delete p;//删除原栈顶结点
	}
}
//输出链栈
void Display(LinkStack S)
{
	if (IsEmpty(S))//如果链栈为空
	{
		cout << "栈空,无结点输出" << endl;
		return;//什么都不做
	}
	Node *p = S.top;//定义探测指针p并指向栈顶结点
	while (p != NULL)
	{
		cout << p->data << "=>";//输出栈顶结点值
		p = p->next;//p后移
	}
	cout << "NULL" << endl;
}
//主程序
void main()
{
	LinkStack S;//定义栈
	Create(S);//创建空栈
	Push(S, 1);//入栈
	Push(S, 2);//入栈
	Display(S);
	int x;
	Pop(S, x);//出栈
	Display(S);
	Push(S, 3); //入栈
	Display(S);
}

五、栈的运用

5.1算术表达式

算术表达式是由运算符（+、-、x、/）和运算数（0、1、2、…）所组成。
在计算机中，有中序、前序和后序三种算术表达式。由于中序法存在着优先级和结合性问题，在编译处理上实在不方便，而前（后）序法更适合于编译处理。

中序表示法为：＜运算数1＞＜运算符＞＜运算数2＞
例如“2x3-4x5”就是用中序表示法描述的算术表达式。

前序表示法为：＜运算符＞＜运算数1＞＜运算数2＞
例如“2x3-4x5”对应的前序表达式为“-x23x45”。

后序表示法为：＜运算数1＞＜运算数2＞＜运算符＞
例如“2x3-4x5”对应的后序表达式为“23x45x-”。**

5.2算术表达式求值

以2x3-4x5为例，介绍中序表达式的求值方法。
第一步创建两个空栈，分别用于存放运算符与运算数。
运算符栈
运算数栈
第二步 2入运算数栈，x入运算符栈，3入运算数栈。
运算符栈 x
运算数栈 2 3
第三步 -入运算符栈之前，先与运算符栈的栈顶元素x比较优先级，因-比x的优先级低，-暂不能入运算符栈，先让x出运算符栈，3与2出运算数栈，计算2x3=6，再将6入运算数栈，然后让-入运算符栈。
运算符栈 -
运算数栈 6
第四步 4入运算数栈，x入运算符栈之前，先与运算符栈的栈顶元素-比较优先级，因x比-的优先级高，让x入运算符栈，5入运算数栈。
运算符栈 - x
运算数栈 6 4 5
第五步中序表达式处理完毕之后，让5与4出运算数栈，x出运算符栈，计算4x5=20，再将20入运算数栈。
运算符栈 -
运算数栈 6 20
第六步 20与6出运算数栈，-出运算符栈，计算6-20=-14，再将-14入运算数栈。
运算符栈
运算数栈 -14
第七步运算符栈已空，让-14出运算数栈，使运算数栈也为空，-14就是中序表达式23-45的值。
运算符栈
运算数栈

以“-x23x45”为例，介绍前序表达式的求值方法。
第一步创建两个栈，一个用来存放前序表达式字符，一个用来存放运算数。
前序表达式栈 - x 2 3 x 4 5
运算数栈
第二步 5与4出前序表达式栈，入运算数栈。
前序表达式栈 - x 2 3 x
运算数栈 5 4
第三步 x出前序表达式栈，4与5出运算数栈，计算4x5=20，再将20入运算数栈。
前序表达式栈 - x 2 3
运算数栈 20
第四步 3与2出前序表达式栈，入运算数栈。
前序表达式栈 - x
运算数栈 20 3 2
第五步 *出前序表达式栈，2与3出运算数栈，计算2x3=6，再将6入运算数栈。
前序表达式栈 -
运算数栈 20 6
第六步 -出前序表达式栈，6与20出运算数栈，计算6-20=-14，再将-14入运算数栈。
前序表达式栈
运算数栈 -14
第七步前序表达式栈已空，让-14出运算数栈，使运算数栈也为空，-14就是前序表达式-2345的值。
前序表达式栈
运算数栈

以“23x45x-”为例，介绍后序表达式的求值方法。
第一步创建两个栈，一个用来存放后序表达式字符（注意：逆序装入），一个用来存放运算数。
后序表达式栈 - x 5 4 x 3 2
运算数栈
第二步 2与3出后序表达式栈，入运算数栈。
后序表达式栈 - x 5 4 x
运算数栈 2 3
第三步 x出后序表达式栈，3与2出运算数栈，计算2x3=6，再将6入运算数栈。
后序表达式栈 - x 5 4
运算数栈 6
第四步 4与5出后序表达式栈，入运算数栈。
后序表达式栈 - x
运算数栈 6 4 5
第五步 x出后序表达式栈，5与4出运算数栈，计算4x5=20，再将20入运算数栈。
后序表达式栈 -
运算数栈 6 20
第六步 -出后序表达式栈，20与6出运算数栈，计算6-20=-14，再将-14入运算数栈。
后序表达式栈
运算数栈 -14
第七步后序表达式栈已空，让-14出运算数栈，使运算数栈也为空，-14就是后序表达式2345-的值。
后序表达式栈
运算数栈

比较三种算术表达式的求值方法，不难发现：中序表达式符合我们的阅读习惯，但运算符的入栈需要考虑其优先级。因为在运算符栈中，只允许优先级高的运算符“压在”优先级低的运算符之上。前序（后序）表达式求值法，避免了运算符优先级的讨论，更适合于计算机去处理；由于后序表达式的入栈次序是逆序的，相比较而言，前序表达式求值方法更为方便。

5.3中序转前序或者后序

利用栈，可将中序表达式转换成前序表达式。在转换过程中，需要借助一个运算符栈和一个输出栈。还需要计算运算符的ISP值与ICP值。ISP（In Stack Priority）是指运算符的“栈内优先级”，而ICP（In Coming Priority）是指运算符的“输入优先级”。

中序转前序的算法如下：

（1）规定运算符“)”在运算符栈内的优先级ISP最小，“(”的ISP最大；而运算符“)”在运算符栈外的优先级ICP最大，“（”的ICP最小。
总结：遇到’)’直接读入运算符栈，入栈后’)’变为最小的ISP，后续的运算符(除了’)’外)都可以直接读入。
总结：遇到’(’，先将’)’前面的运算符全部收入到输出栈，然后将’(’与‘)’消除。

（2）由右至左依次读入中序表达式中的每一个

（3）如果读入的是运算数，则直接进入输出栈。

（4）如果读入的是运算符，当读入运算符的ICP ≤ 运算符栈顶元素的ISP时，将运算符栈顶元素出栈并进入输出栈，直到运算符栈为空或者运算符栈顶元素的ISP小于ICP为止，然后再让读入的运算符入运算符栈。
（备注：可以简单理解为icp>isp为入栈条件）

（5）如果读入的是运算符“（”，让运算符栈顶元素出栈并进入输出栈，直到第一个“）”出栈为止。

（6）当中序表达式读完后，让运算符栈元素全部出栈并进入输出栈。

例题：将中序表达式“(A+B)D+E/(F+AD)+C”转换成前序表达式。
答：创建一个运算符栈和一个输出栈（假定两个栈的左端为栈顶），由右至左逐一读取中序表达(A+B)D+E/(F+AD)+C的每一个字符，转换过程如下图。

注意：我们一般默认左边为栈底，现在默认左边为栈顶，主要是在输出栈中可以直接看出表达式而不需要再进行栈的输出。

所求的前序表达式为+x+ABD+/E+FxADC。
注意上述用x代替了*。

c++代码实现中序转前序：

#include<iostream>
using namespace std;
#define MaxSize 100//存放中序表达式字符数组的最大容量
//优先级结构体定义
struct Priority
{
	char C;//运算符
	int P;//优先级
};
//优先级结构体数组赋初值(全局变量)
Priority ISP[8] = { { ')', 0 }, { ';', 1 }, { '=', 2 }, { '+', 3 }, { '-', 3 }, { '*', 4 }, { '/', 4 }, { '(', 5 } };
Priority ICP[8] = { { '(', 0 }, { ';', 1 }, { '=', 2 }, { '+', 3 }, { '-', 3 }, { '*', 4 }, { '/', 4 }, { ')', 5 } };
//结点定义
struct Node
{
	char data;//数据域
	Node* next;//指针域
};
//链栈定义
struct Stack
{
	Node* top;
};
//创建空链栈
void Create(Stack& S)
{
	S.top = NULL;
}
//判空
int IsEmpty(Stack S)
{
	if (S.top == NULL) return 1;
	else  return 0;
}
//入栈
void Push(Stack& S, char x)
{
	Node* NewNode;//新结点
	NewNode = new Node;//新结点申请内存
	NewNode->data = x;//新结点的数据域赋值
	NewNode->next = NULL;//新结点的指针域赋值
	if (IsEmpty(S))//如果链栈为空
		S.top = NewNode;//链栈顶指针指向新结点
	else//如果链栈非空
	{
		NewNode->next = S.top;//新结点前插入链栈
		S.top = NewNode;//链栈顶指针指向新结点
	}
}
//出栈
void Pop(Stack& S, char& x)
{
	if (IsEmpty(S))
	{
		cout << "栈空,无法出栈" << endl;
		return;
	}
	Node* p = S.top;//定义探测指针p并指向栈顶结点
	if (p->next == NULL)//如果链栈中仅含一个结点
	{
		x = p->data;//获取栈顶结点值
		S.top = NULL;//置链栈为空
		delete p;//删除原栈顶结点
	}
	else//如果链栈中至少含有两个结点
	{
		x = p->data;//获取栈顶结点值
		S.top = S.top->next;//栈顶指针后移
		delete p;//删除原栈顶结点
	}
}
//输出链栈
void Display(Stack S)
{
	if (IsEmpty(S))//如果链栈为空
	{
		cout << "栈空,无结点输出" << endl;
		return;//什么都不做
	}
	Node* p = S.top;//定义探测指针p并指向栈顶结点
	while (p != NULL)
	{
		cout << p->data;//输出栈顶结点值
		p = p->next;//p后移
	}
	cout << endl;
}
//输入中序表达式
void Input(char Infix[], int& n)
{
	cin >> Infix;//输入中序表达式
	n = 0;
	while (Infix[n] != '\0')//获取字符数组的长度
		n++;
}
//运算符优先级比较
int Compare(char InfixSymbol, char StackSymbol)
{
	int isp = 0, icp = 0;
	while (ISP[isp].C != StackSymbol)
		isp++;//查找运算符栈的栈顶运算符在ISP数组中位置isp
	while (ICP[icp].C != InfixSymbol)
		icp++;//查找读入运算符在ICP数组中的位置icp
	//若读入运算符的ICP大于栈顶运算符的ISP，返回1。否则，返回0
	return (ICP[icp].P > ISP[isp].P ? 1 : 0);
}
//中序转前序
void Infix2Prefix(char Infix[], int n, Stack& S, Stack& O)
{
	char x, y;
	do
	{
		y = Infix[n];//从右至左读取中序表达式字符
		switch (y)
		{	//y为(
		case '(':
			while (S.top->data != ')')//当栈顶元素字符不等于）时
			{
				Pop(S, x);//运算符栈的栈顶元素出栈
				Push(O, x);//再入输出栈
			}
			Pop(S, x);//让)出栈
			break;
			//y为);=+-*/
		case ')':
		case ';':
		case '=':
		case '+':
		case '-':
		case '*':
		case '/':
			if (IsEmpty(S))//如果运算符栈为空
				Push(S, y);//y直接入运算符栈
			else//如果运算符栈非空
			{	//当y的ICP小于或等于运算符栈顶元素的ISP时
				while (!Compare(y, S.top->data))
				{
					Pop(S, x);//运算符栈的栈顶元素出栈
					Push(O, x);//再入输出栈
					if (IsEmpty(S))//如果运算符栈为空
						break;
				}
				Push(S, y);//y入运算符栈
			}
			break;
			//y为运算数
		default:
			Push(O, y);//y入输出栈
			break;
		}
		n--;//下标减1
	} while (n != -1);
	//中序表达式字符读入完毕,让运算符栈元素出栈入输出栈
	while (!IsEmpty(S))//当运算符栈非空时
	{
		Pop(S, x);//运算符栈的栈顶元素出栈
		Push(O, x);//再入输出栈
	}
}
//主函数
void main()
{
	char Infix[MaxSize];//定义中序表达式字符数组
	Stack S, O;//定义运算符栈,输出栈
	Create(S);//创建空运算符栈
	Create(O);//创建空输出栈
	int n;//n表示中序表达式的字符长度
	cout << "输入中序表达式" << endl;
	Input(Infix, n);//调用中序表达式输入函数
	Infix2Prefix(Infix, n, S, O);//调用中序转前序函数
	cout << "输出前序表达式" << endl;
	Display(O);//显示输出栈
}

在这里插入图片描述

中序转后序的算法如下：
（1）规定运算符“(”在运算符栈内的优先级ISP最小，“)”的ISP最大；而运算符“(”在运算符栈外的优先级ICP最大，“)”的ICP最小。（同中序转前序相反）
（2）由左至右依次读入中序表达式中的每一个字符。（同中序转前序相反）
（3）如果读入的是运算数，则直接输出。
（4）如果读入的是运算符，当读入运算符的ICP ≤ 运算符栈顶元素的ISP时，将运算符栈顶元素出栈并输出，直到运算符栈为空或者运算符栈顶元素的ISP小于ICP为止。然后再让读入的运算符入运算符栈。
（备注：可以简单理解为icp>isp为入栈条件,同中序转前序一样）
（5）如果读入的是运算符“)”，让运算符栈顶元素出栈并输出，直到第一个“(”出栈为止。（同中序转前序一样）
（6）当中序表达式读完后，让运算符栈元素全部出栈并输出。（同中序转前序一样）
显然，实现中序转后序算法，只需创建一个运算符栈。

c++代码实现中序转后序：

#include<iostream>
#include<stack>
#include<string>
using namespace std;
int priority(char ch)
{
	if (ch == '*' || ch == '/')
		return 1;
	if (ch == '+' || ch == '-')
		return 0;
	if (ch == '(')
		return -1;
}
int main()
{
	string input = "(A+B)*D+E/(F+A*D)+C";         //待处理中序表达式
	string output;
	stack<char> st;
	for (const auto& p : input)
	{
		if (p == '+' || p == '-' || p == '*' || p == '/' || p == '(')
		{
			if (p == '(')
				st.push(p);
			else
			{
				while ((!st.empty()) && (priority(p) <= priority(st.top())))
				{
					output += st.top();
					st.pop();
				}
				st.push(p);
			}
		}
		else if (p == ')')
		{
			while (st.top() != '(')
			{
				output += st.top();
				st.pop();
			}
			st.pop();
		}
		else                         //如果是操作数,直接输入到输出
			output += p;
	}
	while (!st.empty())
	{
		output += st.top();
		st.pop();
	}
	cout << output << endl;
	return 1;
}