普通栈的算法

头文件

#include <iostream>
using namespace std;
typedef struct LNode
{
	int data;
	struct LNode *next;
} LNode, *Linklist;


//不带头节点的链表
Linklist aaaa();
//带头节点的链表
Linklist bbbb();

#include <iostream>
using namespace std;

#define maxsize 50
typedef struct
{
	int data[maxsize];
	int front, rear;
} queue;

//初始化
void init(queue &q);
bool enqueue(queue &q, int x);
int dequeue(queue &q);

#include <iostream>
using namespace std;
#define maxsize 50

typedef struct
{
	char data[maxsize];
	int top;
} stack;

//初始化
void Init(stack &s);

bool push(stack &s, int x);

int pop(stack &s);

#include <iostream>
using namespace std;
#define maxsize 50
//共享栈
typedef struct
{
	int data[maxsize];
	int top[2];
} stack1;

#include"0_linklist.h"
//不带头节点的链表
Linklist aaaa()
{
	LNode *L = new LNode;
	int a;
	cin >> a;
	L->data = a;
	LNode *p = L; //声明一个指针指向头结点，
	//生成链表
	cin >> a;
	while (a != 0)//输入0为循环的结束条件
	{
		LNode *q = new LNode;
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;
		cin >> a;
	}
	p->next = NULL;
	return L;
}

//带头节点的链表
Linklist bbbb()
{
	LNode *L = new LNode; //创建一个头结点
	LNode *p = L;         //声明一个指针指向头结点
	//生成链表
	int a;
	cin >> a;
	while (a != 0)
	{
		LNode *q = new LNode;
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;
		cin >> a;
	}
	p->next = NULL;
	return L;
}

#include"0_queue.h"
//初始化
void init(queue &q)
{
	q.rear = q.front = 0;
}
bool enqueue(queue &q, int x)
{
	//队列满的条件
	if ((q.rear + 1) % maxsize == q.front)
		return false;
	//先插入元素 再更新指针的位置
	q.data[q.rear] = x;
	q.rear = (q.rear + 1) % maxsize;
	return true;
}
int dequeue(queue &q)
{
	//队列空的条件
	if (q.rear == q.front)
		return -100;
	//先把元素保存 再移动指针
	int x = q.data[q.front];
	q.front = (q.front + 1) % maxsize;
	return x;
}

#include"0_stack.h"
//初始化
void Init(stack &s)
{
	s.top = -1;
}

bool push(stack &s, int x)
{
	if (s.top == maxsize - 1)
		return false;
	//先移动指针 再插入元素
	s.data[++s.top] = x;
	return true;
}

int pop(stack &s)
{
	if (s.top == -1)
		return false;
	//先返回元素 再移动指针
	return s.data[s.top--];
}

Q是一个队列，S是一个空栈，编写算法使得队列中元素逆置

void reverse(stack &s, queue &q)
{
	while (q.front != q.rear)//队列不为空时
		push(s, dequeue(q));//出队 入栈
	while (s.top != -1)//栈不为空时
		enqueue(q, pop(s));//出栈 入队
}

int main01()
{
	stack s;
	Init(s);
	queue q;
	init(q);
	int x;
	cin >> x;
	while (x != -1)
	{
		enqueue(q, x);
		cin >> x;
	}
	reverse(s, q);
	while (q.front != q.rear)
	{
		cout << q.data[q.front] << " ";
		q.front = (q.front + 1) % maxsize;
	}
	return EXIT_SUCCESS;
}

判断单链表的全部n个字符是否中心对称 用栈来实现

#include <iostream>
#include"0_queue.h"
#include"0_stack.h"
#include"0_linklist.h"
using namespace std;

/*
	判断单链表的全部n个字符是否中心对称 用栈来实现
	1 2 2 1
	1 2入栈 2 1出栈 与2 1比较

	1 2 3 2 1
	1 2入栈 3不管 2 1 出栈 与2 1比较
*/

int fun(LNode *L)
{
	int n = 0, j;//n是统计链表中元素的个数
	stack s;
	Init(s);//初始化栈
	LNode *p = L->next;
	//统计元素个数
	while (p != NULL)
	{
		++n;
		p = p->next;
	}
	//把p移动到第一个元素
	p = L->next;
	//把左边的元素放入栈中
	for (j = 0; j < n / 2; ++j)
	{
		push(s, p->data);
		p = p->next;//此时p移动到右边的第一个结点
	}
	//如果是奇数的话还要后移一位 因为此时的p指向的是中心的位置 不需要进行比较
	if (n % 2 != 0)
		p = p->next;
	while (p != NULL)
	{
		if (pop(s) == p->data)
			p = p->next;
		else
			return 0;
	}
	return 1;
}

int main02()
{
	stack s;
	LNode *L = bbbb();
	cout << fun(L) << endl;
	return EXIT_SUCCESS;
}

两个栈s1,s2都采用顺序存储，并共享一个存储区[0…,maxsize-1]。采用栈顶相向，迎面增长的存储方式，设计s1,s2入栈和出栈的操作。

#include <iostream>
#include "0_stack[].h"
using namespace std;
/*
	两个栈s1,s2都采用顺序存储，并共享一个存储区[0...,maxsize-1]。
	采用栈顶相向，迎面增长的存储方式，设计s1,s2入栈和出栈的操作。
	
	typedef struct
	{
		int data[maxsize];
		int top[2];
	} stack1;

*/

//共享栈的初始化
void Init(stack1 &s)
{
	//顺序存储
	s.top[0] = -1;
	s.top[1] = maxsize;
}

//x为入栈的元素 i表示0、1共享栈的两边进行操作的 x是插入的元素
bool push(stack1 &s, int i, int x)
{
	//非法数据
	if (i < 0 || i > 1)
		return false;
	//共享栈满了
	if (s.top[1] - s.top[0] == 1)
		return false;
	switch (i)
	{
	case 0:
		s.data[++s.top[0]] = x;
		break;
	case 1:
		s.data[--s.top[1]] = x;
		break;
	}
	return true;
}

int pop(stack1 &s, int i)
{
	//非法数据
	if (i < 0 || i > 1)
		return -1;
	switch (i)
	{
	case 0:
		if (s.top[0] == -1)
			return -1;
		else
			return s.data[s.top[0]--];
		break;
	case 1:
		if (s.top[1] == maxsize)
			return -1;
		else
			return s.data[s.top[1]++];
		break;
	}
	//return 0;
}

int main03()
{
	stack1 s;
	Init(s);
	push(s, 0, 15);
	push(s, 0, 13);
	push(s, 1, 10);
	pop(s, 0);
	cout << s.data[s.top[0]];
	return EXIT_SUCCESS;
}

判断一个表达式中括号是否配对(假设只包含圆括号)

#include <iostream>
#include"0_stack.h"
using namespace std;

/*
	判断一个表达式中括号是否配对(假设只包含圆括号)

	1、遍历整个字符串 遇到左括号入栈
*/

bool fun(stack &s, string str)
{
	int i = 0;
	while (str[i] != '\0')
	{
		switch (str[i])
		{
		case '(':
			push(s, '(');
			break;
		case '{':
			push(s, '{');
			break;
		case ')':
			//栈顶为（匹配成功 栈顶不为(则匹配失败
			if (pop(s) != '(')//如果不成立则进行了出栈操作
				return false;
			break;
		case '}':
			if (pop(s) != '{')
				return false;
			break;
		default:
			break;
		}
		++i;//数组下标后移
	}
	if (s.top == -1)
		return true;
	else
		return false;
}

int main04()
{
	stack s;
	Init(s);
	string S = "(15+()))";
	//string S = "(({{(1212})}))";err
	cout << "结果为：";
	bool q = fun(s, S);
	if (q == true)
		cout << "括号匹配!" << endl;
	else
		cout << "括号不匹配!" << endl;
	return EXIT_SUCCESS;
}

假设一个序列为HSSHHHS，运用栈的知识，编写算法将S全部提到H之前,即为SSSHHHH

#include <iostream>
#include "0_stack.h"
using namespace std;
/*
	假设一个序列为HSSHHHS，运用栈的知识，编写算法将S全部提到H之前,即为SSSHHHH

	1、定义一个字符串 如果遍历到H的时候入栈 
	2、如果遍历到S就加入定义的字符串中 进行覆盖操作
	3、定义的字符串就是SSS 进行出栈操作把HHHH放入其后就可以了
*/
void fun(string S) 
{
	stack s;
	Init(s);
	string newS = "0000000";
	int i = 0, j = 0;
	while (S[i] != '\0')
	{
		if (S[i] == 'H')
			push(s, S[i++]);
		else
			newS[j++] = S[i++];
	}
	while (s.top != -1)
		newS[j++] = pop(s);
	i = 0;
	while (newS[i] != '\0')
		cout << newS[i++];
}

int main05()
{
	string S = "HSSHHHS";
	fun(S);
	return EXIT_SUCCESS;
}

利用栈实现递归函数的非递归算法

#include <iostream>
using namespace std;
#define maxsize 50
/*
	利用栈实现递归函数的非递归算法
	利用一个栈实现以下递归函数的非递归计算：
	
	     =  1                          n=0
	Pn(x)=  2x                         n=1
	     =  2xPn-1(x)-2(n-1)Pn-2(x)   n>1


	栈存的是表达式top指针的0对应n
			      top指针的n对应0
*/

/*
	top     n

	7		0
	6		1
	5		2
	4		3
	3		4
	2		5
	1		6
	0		7
*/


double fun2(int n, double x) {
	int top = n - 2;//top的初始值为n-2   用于后面的中止条件
	double *p = new double[n];//动态数组的申请
	double fv1 = 1;
	double fv2 = 2 * x;
	n = 2;//设n=2初值 非递归算法循环进行递归函数
	while (top > -1)
	{
		p[top] = 2 * x * fv2 - 2 * (n - 1) * fv1;
		fv1 = fv2;
		fv2 = p[top];
		++n;
		top--;//top--进行下一次的递归
	}

	delete[] p;

	if (n == 0)
		return fv1;
	return fv2;
}
int main06()
{
	int n = 2;
	cout << fun2(n, 5);
	return EXIT_SUCCESS;
}