1.顺序栈

#include <iostream>
#include<stdio.h>
using namespace std;
#define SElemType int
#define Status int
#define STACK_INIT_SIZE 100
#define STACKINCREMENT  10

typedef struct {
	SElemType* base; //栈底
	SElemType* top;  //栈顶
	int stacksize;
}SqStack;

Status InitStack(SqStack  &s)
{
	s.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
		if (!s.base)
			exit(_OVERFLOW);
		s.top = s.base;
		s.stacksize = STACK_INIT_SIZE;
		return 1;
}

Status DestoryStack(SqStack &s)
{
	free(s.base);
	s.base = NULL;
	s.top = NULL;
	s.stacksize = 0;
	return 1;
}

Status ClearStack(SqStack& s)
{
	if (!s.base)
		return 0;
	s.top = s.base;
	return 1;
}

Status StackEmpty(SqStack s)
{
	if (s.top == s.base)
		return 1;
	return 0;
}

Status StackLength(SqStack s)
{
	if (!s.base)
		return 0;
	return (int)(s.top - s.base);
}

Status GetTop(SqStack s, SElemType& e)
{
	if (s.base == s.top)
		return 0;
	e = *(s.top - 1);
	return 1;
}

Status Push(SqStack& s, SElemType e)
{
	if (!s.base)
		return 0;
	if (s.top - s.base >= s.stacksize)
	{
		s.base = (SElemType*)realloc(s.base, (s.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if (!s.base)
			exit(_OVERFLOW);
		s.top = s.base + s.stacksize;
		s.stacksize += STACKINCREMENT;
	}
	*s.top++ = e;
	return 1;
}

Status Pop(SqStack& s, SElemType& e)
{
	if (!s.base || s.top == s.base)
		return 0;
	e = *--s.top;
	return 1;
}

void visit(SElemType e)
{
	cout << e << " ";
}

Status StackTraverse(SqStack s, void(*visit)(SElemType))
{
	SElemType* p = s.base;
	if (!s.base)
		return 0;
	while (p < s.top)
		visit(*p++);
	cout << "\n";
	return 1;
}

2.算法3.1数制的转换

void conversion()
{
	SqStack S;
	InitStack(S);
	SElemType N, e;
	scanf_s("%d", &N);
	while (N)
	{
		Push(S, N % 8);
		N /= 8;
	}
	while (!StackEmpty(S))
	{
		Pop(S, e);
		cout << e;
	}
}

3.算法3.2括号匹配

void LineEdit()
{
	SqStack S;
	InitStack(S);
	SElemType c;
	char ch = getchar();
	while(ch != EOF)
	{
		while (ch != EOF && ch != '\n')
		{
			switch (ch)
			{
			case '#':
				Pop(S, c);
				break;
			case '@':
				ClearStack(S);
				break;
			default:
				Push(S, ch);
			}
			ch = getchar();
		}
		ClearStack(S);
		if (ch != EOF)
			ch = getchar();
	}
	DestoryStack(S);
}

4.算法3.3链式栈解决表达式求值

 #include <iostream>
using namespace std;
#define SElemType char
#define Status int
typedef char OperandType;

typedef struct SNode
{
	SElemType data;
	struct SNode* next;
}SNode, * LinkStack;

Status InitStack(LinkStack& S)
{
	S = (LinkStack)malloc(sizeof(SNode));
	if (!S)
		exit(_OVERFLOW);
	S->next = NULL;
	return 1;
}

Status DestroyStack(LinkStack& S)
{
	LinkStack p = S->next, ptmp;//p指向栈顶
	while (p)                  //p指向栈底时，循环停止
	{
		ptmp = p->next;
		free(p);               //释放每个数据节点的指针域
		p = ptmp;
	}
	free(S);
	return 1;
}

Status ClearStack(LinkStack& S)
{
	LinkStack p = S->next, ptmp;  //p指向栈顶
	while (p)
	{
		ptmp = p->next;
		free(p);
		p = ptmp;
	}
	S->next = NULL;
	return 1;
}

Status StackEmpty(LinkStack S)
{
	if (S->next == NULL)
		return 1;
	else
		return 0;
}

int  StackLength(LinkStack S)
{
	int n = 0;
	LinkStack p = S->next;
	while (p)
	{
		n++;
		p = p->next;
	}
	return  n;
}

Status GetTop(LinkStack S, SElemType& e)
{
	if (S->next == NULL)
		return 0;
	e = S->next->data;    //取栈顶元素
	return 1;
}

Status Push(LinkStack& S, SElemType e)
{
	LinkStack p = (LinkStack)malloc(sizeof(SNode));
	p->data = e;
	p->next = S->next;            //新结点指向栈顶
	S->next = p;                  //更新栈顶指针

	return 1;
}

Status Pop(LinkStack& S, SElemType& e)
{
	if (S->next == NULL)
		return 0;
	
	//若有一个以上元素
	e = S->next->data;           //将栈顶元素赋给e
	LinkStack ptmp = S->next->next;//用临时变量保存栈顶元素空间以备释放
	free(S->next);
	S->next = ptmp;             //栈顶指针
	//printf("删除栈顶的元素："); visit(e);
	return 1;
}

Status visit(SElemType e)
{
	printf(" %c\n", e);
	return 1;
}

//操作结果，从栈底到栈顶 依次对栈中每个数据元素调用函数visit()，一旦visit()失败，则操作失败
Status StackTraverse(LinkStack S, Status(*visit)(SElemType))
{
	if (S->next == NULL)
	{
		printf("栈为空!\n");
		return 0;
	}
	for (int i = StackLength(S); i > 0; i--)
	{
		LinkStack p = S->next;    //p指向栈顶
		int  j = 1;
		while (p && j < i)        //顺指针向后查找，直到p指向第i个元素或p为空
		{
			p = p->next;
			++j;
		}
		visit(p->data);
	}
	printf("\n");
	return 1;
}


//操作结果，从栈顶到栈底依次对栈中每个数据元素调用函数visit()，一旦visit()失败，则操作失败
Status StackTraverse_Top(LinkStack S, Status(*pfn_visit)(SElemType))
{
	if (S->next == NULL)
	{
		printf("栈为空!\n");
		return 0;
	}
	LinkStack p = S->next;        //p指向栈顶
	while (p)
	{
		visit(p->data);
		p = p->next;
	}
	printf("\n");
	return 1;
}

//算法部分
//判断运算符栈的（栈顶运算符）与（读入的运算符）之间的优先关系
SElemType Precede(SElemType t1, SElemType t2)
{
	SElemType t;
	switch(t1)
	{
	case'+':
	case'-':
		if (t2 == '*' || t2 == '/' || t2 == '(')
			t = '<';
		else
			t = '>';
		break;
	
	case '*':
	case'/':
		if (t2 == '(')
			t = '<';
		else
			t = '>';
		break;
	
	case'(':
		if (t2 == ')')
			t = '=';
		else if (t2 == '#')
			return 0;
		else t = '<';
		break;
	
	case')':
		if (t2 == '(')
			return 0;
		else t = '>';
		break;

	case'#':
		if (t2 == ')')
			return 0;
		else if (t2 == '#')
			t = '=';
		else t = '<';
		break;
	}
	return t;
}

//进行二元运算 
SElemType Operator(SElemType a, SElemType theta, SElemType b)
{
	SElemType ret;
	switch (theta)
	{
	case '+':
		ret = (a - 48) + (b - 48) + 48;
		break;
	case '-':
		ret = (a - 48) - (b - 48) + 48;
		break;
	case '*':
		ret = (a - 48) * (b - 48) + 48;
		break;
	case '/':
		ret = (a - 48) / (b - 48) + 48;
		break;
	}
	return ret;
}


Status In(SElemType c) //判定读入的字符ch是否为运算符
{
	switch (c)
	{
	case'+':
	case'-':
	case'*':
	case'/':
	case'(':
	case')':
	case'#':
	case'=':
		return 1;
		break;
	default:
		return 0;
	}
}

//算法3.4 
OperandType ExvaluateExpression()
{
	LinkStack OPTR;  //运算符栈：寄存运算符
	LinkStack OPND;  //运算数栈：寄存操作数或运算结果
	char c, x, theta, a, b, e;

	InitStack(OPTR);
	InitStack(OPND);
	Push(OPTR, '#');                //表达式起始符#为运算符栈的栈底元素

	printf("输入表达式：\n");
	c = getchar();
	GetTop(OPTR, e);

	while (c != '#' || e != '#')   //当前读入的字符 或 运算符栈顶元素不为#
	{
		if (!In(c))//不是运算符（操作数或结果）则进OPND栈
		{
			Push(OPND, c);
			c = getchar();
		}
		else      //是运算符，则和运算符栈顶的运算符比较优先级
		{
			GetTop(OPTR, e);
			switch (Precede(e, c))  //比较OPTR的栈底元素和ch的优先级
			{
			case'<':
				Push(OPTR, c);      //当前字符ch压入OPTR栈，读入下一个字符ch
				c = getchar();
				break;
			case'=':               //OPTR栈顶元素是（ 而且ch是 ）
				Pop(OPTR, x);      //弹出OPTR栈顶的是（，读入下一字符ch
				c = getchar();
				break;
			case'>':
				Pop(OPTR, theta);  //弹出OPTR栈顶的运算符
				Pop(OPND, b);      //弹出OPND栈顶的两个运算数
				Pop(OPND, a);
				Push(OPND, Operator(a, theta, b));//将运算结果压入OPND栈
				break;
			}
		}
		GetTop(OPTR, e);
	}
	GetTop(OPND, e);
	return e;
}

int main()
{
	char c;
	do {
		fflush(stdin);  //清空缓冲区
		c = ExvaluateExpression();
		printf("表达式的值：");
		printf("%d\n", c - 48);
		printf("是否继续（y/n）:");
	} while (scanf_s("%s", &c) != 0 && (c == 'y' || c == 'Y'));
	return 0;
}

5.算法3.4舞伴问题

6.算法3.5汉诺塔问题

int c = 0;
void move(char x, int n, char z)
{
	cout << ++c << ".Move disk" << n << "from" << x << "to" << z << "." << endl;
}

void hanoi(int n, char x, char y, char z)
{
	if (n == 1)
		move(x, 1, z);          //将编号为以一的圆盘从x开始移动到z
	else
	{
		hanoi(n - 1, x, z, y);
		move(x, n, z);         //将编号为n的圆盘从x移动到z
		hanoi(n - 1, y, x, z); //将y上编号为1到n-1的圆盘移动到z,x作辅助塔
	}
}