1. 试按照以下的要求把栈中的元素逆置

（1）使用额外的两个栈

（2）使用额外的一个队列

（3）使用额外的一个栈，外加一些非数组的变量

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

void ReverseStack1(stack<int>& s)
{
	stack<int> tempStack1, tempStack2;

	while (!s.empty())
	{
		tempStack1.push(s.top());
		s.pop();
	}

	while (!tempStack1.empty())
	{
		tempStack2.push(tempStack1.top());
		tempStack1.pop();
	}

	while (!tempStack2.empty())
	{
		s.push(tempStack2.top());
		tempStack2.pop();
	}
}

void ReverseStack2(stack<int>& s)
{
	queue<int> q;

	while (!s.empty())
	{
		q.push(s.top());
		s.pop();
	}

	while (q.empty())
	{
		s.push(q.front());
		q.pop();
	}
}

void ReverseStack3(stack<int>& s)
{
	stack<int> tempStack;
	int temp;
	while (!s.empty()) {
		temp = s.top();   
		s.pop();   
		tempStack.push(temp); 
	}

	while (!tempStack.empty()) {
		temp = tempStack.top();
		tempStack.pop();
		s.push(temp);
	}
}
void PrintStack(stack<int> s)
{
	while (!s.empty())
	{
		cout << s.top() << " ";
		s.pop();
	}
	cout << endl;
}

int main()
{
	stack<int> s;

	s.push(1);
	s.push(2);
	s.push(3);
	s.push(4);

	cout << "原始栈:";
	PrintStack(s);

	ReverseStack1(s);

	cout << "逆置后的栈";
	PrintStack(s);

	return 0;

}

2. 试给出用栈所定义的队列

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

class QueueUsingStacks {
private:
	stack<int> pushs, pops;
public:
	void pushQueue(int x)
	{
		pushs.push(x);
	}

	int popQueue()
	{
		if (pops.empty())
		{
			if (pushs.empty())
			{
				runtime_error("Queue is empty!");
			}
			while (!pushs.empty())
			{
				pops.push(pushs.top());
				pushs.pop();
			}
		}

		int front = pops.top();
		pops.pop();
		return front;
	}

	int front()
	{
		if (pops.empty())
		{
			if (pushs.empty())
			{
				throw runtime_error("Queue is empty!");
			}
			while (!pushs.empty())
			{
				pops.push(pushs.top());
				pushs.pop();
			}
		}

		return pops.top();
	}

	bool isEmpty()
	{
		return pushs.empty() && pops.empty();
	}
};

int main()
{
	QueueUsingStacks q;

	q.pushQueue(1);
	q.pushQueue(2);
	q.pushQueue(3);
	q.pushQueue(4);

	cout << "popQueue: " << q.popQueue() << endl; // 1
	cout << "Front: " << q.front() << endl;     // 2

	q.pushQueue(5);
	cout << "Dequeue: " << q.popQueue() << endl; // 2
	cout << "Dequeue: " << q.popQueue() << endl; // 3
	cout << "Dequeue: " << q.popQueue() << endl; // 4
	cout << "Dequeue: " << q.popQueue() << endl; // 5

	return 0;
}

3. 试在一个长度为n的数组中实现两个栈，使得二者在元素的总数目为n之前都不溢出，并且保证push和pop操作时间代价为O（1）

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

class TwoStacks {
private:
	int* arr; //存储两个栈的数组
	int size;
	int top1;
	int top2;
public:
	TwoStacks(int n)
	{
		size = n; 
		arr = new int[n];
		top1 = -1; //栈1从索引0开始增长
		top2 = n; //栈2从索引n-1开始增长
	}

	void push1(int value)
	{
		if (top1 + 1 < top2)
		{
			arr[++top1] = value;
		}
		else
		{
			cout << "Stack OverFlow in Stack1" << endl;
		}
	}

	void push2(int value)
	{
		if (top1 + 1 < top2)
		{
			arr[--top2] = value;
		}
		else {
			cout << "Stack OverFlow in Stack2" << endl;
		}
	}

	int pop1() {
		if (top1 >= 0) {
			return arr[top1--];
		}
		else {
			cout << "Stack1 is empty!" << endl;
			return -1;
		}
	}

	int pop2() {
		if (top1 >= 0) {
			return arr[top2++];
		}
		else {
			cout << "Stack2 is empty!" << endl;
			return -1;
		}
	}

	void PrintStacks()
	{
		cout << "Stack1:";
		for (int i = 0; i <= top1; i++) {
			cout << arr[i] << " ";
		}
		cout << "\nStack2:";
		for (int i = size - 1; i >= top2; i--)
		{
			cout << arr[i] << " ";
		}
		cout << endl;
	}

	~TwoStacks()
	{
		delete[] arr;
	}
};

int main()
{
	TwoStacks ts(10);

	ts.push1(1);
	ts.push1(2);
	ts.push1(3);
	ts.push2(9);
	ts.push2(8);
	ts.push2(7);

	ts.PrintStacks();

	cout << "Popped from Stack1: " << ts.pop1() << endl;
	cout << "Popped from Stack2: " << ts.pop2() << endl;

	ts.PrintStacks();

	return 0;
}

4. 试利用栈计算后缀表达式1289 * +，并明确写出每个步骤以及每个步骤的栈的状态

#include <iostream>
#include <stack>
using namespace std;

int evaluatePostfix(string expression)
{
	stack<int> s;

	for (char c : expression)
	{
		if (isdigit(c)) //c是否是0-9字符
		{
			s.push(c - '0'); //数字入栈
		}
		else
		{
			int operand2 = s.top();
			s.pop();
			int operand1 = s.top();
			s.pop();
			int result = 0;

			if (c == '+')
				result = operand1 + operand2;
			else if (c == '-')
				result = operand1 - operand2;
			else if (c == '*')
				result = operand1 * operand2;
			else if (c == '/')
				result = operand1 / operand2;

			s.push(result); //碰到字符后，两个栈顶元素运算后重新入栈

			cout << "执行" << c << "操作后，栈状态：";
			stack<int> temp = s;
			while (!temp.empty())
			{
				cout << temp.top() << " ";
				temp.pop();
			}
			cout << endl;
		}
	}

	return s.top(); //最终栈顶元素是计算结果
}

int main()
{
	string postfix = "1289*+";
	cout << "计算后缀表达式：" << postfix << endl;
	int result = evaluatePostfix(postfix);
	cout << "最终计算结果：" << result << endl;
	return 0;
}

5. 试利用栈将中缀表达式a*(b*c-d)+e转换成后缀表达式

#include <iostream>
#include <stack>
#include <cctype>

using namespace std;

int precedence(char op)
{
	if (op == '*' || op == '/')
		return 2;
	if (op == '+' || op == '-')
		return 1;
	return 0;
}

string infixToPostfix(string infix)
{
	stack<char> s;
	string postfix;

	for (char c : infix)
	{
		if (isalpha(c)) //c是否是字母a-z或A-Z
		{
			postfix += c;
		}
		else if(c=='(') //左括号直接入栈
		{
			s.push(c);
		}
		else if (c == ')') //右括号，弹出所有运算符直到遇到左括号
		{
			while (!s.empty() && s.top() != '(')
			{
				postfix += s.top();
				s.pop();
			}
			s.pop(); //弹出左括号
		}
		else {
			while (!s.empty() && precedence(s.top()) >= precedence(c)) //栈顶运算符优先级>=当前运算符的所有元素
			{
				postfix += s.top(); //s栈顶的优先级大 ，加到后缀表达式后弹出，把c的加进来
				s.pop();
			}
			s.push(c);
		}
	}
	while (!s.empty())
	{
		postfix += s.top();
		s.pop();
	}

	return postfix;
}

int main()
{
	string infix = "a*(b*c-d)+e";
	string postfix = infixToPostfix(infix);
	cout << "后缀表达式：" << postfix << endl;
}