数据结构——栈-阿里云开发者社区

1 栈具有后进先出（LIFO）的操作特点，是操作受限的线性表。栈的存储有顺序栈和链栈两种。

2 在顺序存储方式下，采用一维数组（即向量）来模拟连续的存储空间。通常将0下表作为栈底，栈的第一个元素（即栈底元素）存放在0下表位置。顺序栈的实现：

//SqStack.h
#ifndef _SQSTACK_
#define _SQSTACK_
template<class T>
class SqStack
{
public:
	SqStack(int);
	~SqStack();
	void Clear();
	bool Empty() const;
	int Length() const;
	T& Top() const;
	void Push(const T&);
	void Pop();
private:
	T* m_base;
	int m_top;
	int m_size;
};

template<class T> SqStack<T>::SqStack(int m)
{
	m_top = 0;
	m_base = new T[m];
	m_size = m;
}

template<class T> SqStack<T>::~SqStack()
{
	if (m_base != NULL) delete [] m_base;
}

template<class T> void SqStack<T>::Clear()
{
	m_top = 0;
}

template<class T> bool SqStack<T>::Empty() const
{
	return m_top == 0;
}

template<class T> int SqStack<T>::Length() const
{
	return m_top;
}

template<class T> T& SqStack<T>::Top() const
{
	if (m_top != 0)
	{
		return m_base[m_top-1];
	}
}

template<class T> void SqStack<T>::Push(const T& e)
{
	if (m_top >= m_size)
	{
		T* newbase = new T[m_size+10];
		for (int i = 0; i < m_size; i++)
		{
			newbase[i] = m_base[i];
		}
		delete [] m_base;
		m_base = newbase;
		m_size += 10;
	}
	m_base[m_top++] = e;
}

template<class T> void SqStack<T>::Pop()
{
	m_top--;
}
#endif

3 用链式存储结构实现的栈成为链栈。当栈非空时，top指向栈顶元素结点；而当栈为空时，top为空指针。链栈的实现：

//LinkStack.h
#ifndef _LINKSTACK_
#define _LINKSTACK_
template<class T>
struct LinkNode
{
	T data;
	LinkNode<T>* next;
};

template<class T>
class LinkStack
{
public:
	LinkStack();
	~LinkStack();
	void Clear();
	int Length() const;
	bool Empty() const;
	T& Top() const;
	void Push(const T&);
	void Pop();
private:
	LinkNode<T> *top;
};

template<class T> LinkStack<T>::LinkStack()
{
	top = NULL;
}

template<class T> LinkStack<T>::~LinkStack()
{
	Clear();
}

template<class T> void LinkStack<T>::Clear()
{
	LinkNode<T>* p;
	while(top)
	{
		p = top;
		top = top->next;
		delete p;
	}
}

template<class T> bool LinkStack<T>::Empty() const
{
	return top == NULL;
}

template<class T> int LinkStack<T>::Length() const
{
	LinkNode<T>* p = top;
	int i = 0;
	while (p)
	{
		i++;
		p = p->next;
	}
	return i;
}

template<class T> T& LinkStack<T>::Top() const
{
	if (top)
	{
		return top->data;
	}
}

template<class T> void LinkStack<T>::Push(const T& e)
{
	LinkNode<T>* p = new LinkNode<T>;
	p->data = e;
	p->next = top;
	top = p;
}

template<class T> void LinkStack<T>::Pop()
{
	LinkNode<T>* p = top;
	top = top->next;
	delete p;
}
#endif

4 栈的应用

4.1 回文判断。

所谓回文，是指一个字符串的字符序列（不包括空格）顺读和逆读是一样的。例如“dad”，"noon"都是回文。程序实现如下：

#include <iostream>
#include "SqStack.h"
#include "LinkStack.h"
using namespace std;

#define MAX_STRING_LEN 100
bool ispalindrome(char*);

void main(int argc, char* argv[])
{
	char instring[MAX_STRING_LEN];
	cin.getline(instring,MAX_STRING_LEN);
	if (ispalindrome(instring))
	{
		cout<<"YES"<<endl;
	}
	else
	{
		cout<<"NO"<<endl;
	}
	system("pause");
}    

//回文判断
bool ispalindrome(char* in_string)
{
	SqStack<char> s(MAX_STRING_LEN);
	char deblankstring[MAX_STRING_LEN],c;
	int i = 0;
	while (*in_string)
	{
		if (*in_string != ' ')
		{
			deblankstring[i++] = *in_string;
		}
		in_string++;
	}
	deblankstring[i] = '\0';

	i = 0;
	while (deblankstring[i])
	{
		s.Push(deblankstring[i++]);
	}
	int k = 0;
	while (!s.Empty())
	{
		c = s.Top();
		s.Pop();
		if (c != deblankstring[k++])
		{
			return false;
		}
	}
	return true;
}

4.2 迷宫问题

#include <iostream>
#include "SqStack.h"
#include <fstream>
using namespace std;

#define MAXSIZE 30

struct PosType
{
	int x; //行
	int y; //列
};

struct DataType
{
	PosType seat; //位置
	int di; //方向
};

class Maze
{
public:
	Maze(int, int);
	~Maze();
	bool MazePath(PosType, PosType);
	void Input();
	void Print();
private:
	PosType NextPos(PosType, int);
	int ** m_maze;
	int m_row;
	int m_col;
};

Maze::Maze(int m, int n)
{
	m_row = m + 2;
	m_col = n + 2;
	m_maze = new int*[m_row];
	for (int i = 0; i < m_row; i++)
	{
		m_maze[i] = new int[m_col];
	}
}

Maze::~Maze()
{
	for (int i = 0; i < m_row; i++)
	{
		if (m_maze[i] != NULL)
		{
			delete [] m_maze[i];
		}
	}
	if (m_maze != NULL)
	{
		delete [] m_maze;
	}
}

bool Maze::MazePath(PosType start, PosType end)
{
	SqStack<DataType> path(MAXSIZE);
	PosType curpos;
	DataType e;
	curpos = start;
	int curstep = 1;
	do 
	{
		if (m_maze[curpos.x][curpos.y] == 0)
		{
			m_maze[curpos.x][curpos.y] = curstep;
			e.seat.x = curpos.x;
			e.seat.y = curpos.y;
			e.di = 0;
			path.Push(e);
			curstep++;
			if (curpos.x == end.x && curpos.y == end.y) //达到终点
			{
				return true;
			}
			curpos = NextPos(curpos, e.di);
		}
		else
		{
			if (!path.Empty())
			{
				e = path.Top();
				path.Pop();
				curstep--;
				while (e.di == 3 && !path.Empty())
				{
					m_maze[e.seat.x][e.seat.y] = -1; //留下不能通过的标记
					e = path.Top(); //退回一步
					path.Pop();
					curstep--;
				}
				if (e.di < 3) //没到最后一个方向
				{
					e.di++; //换下一个方向搜索
					path.Push(e);
					curstep++;
					curpos = NextPos(e.seat,e.di);
				}
			}
		}
	} while (!path.Empty());
	return false;
}

void Maze::Input()
{
	int i,j;
	ifstream input("input.txt");
	cout<<"请输入"<<m_row-2<<"*"<<m_col-2<<"的迷宫:"<<endl;
	for (i = 1; i <= m_row - 2; i++)
	{
		for (j = 1; j <= m_col - 2; j++)
		{
			input>>m_maze[i][j];
		}
	}

	for (i = 0; i < m_row; i++)
	{
		m_maze[i][0] = 1;
		m_maze[i][m_col-1] = 1;
	}

	for (j = 0; j < m_col; j++)
	{
		m_maze[0][j] = 1;
		m_maze[m_row-1][j] = 1;
	}
}

void Maze::Print()
{
	int i, j;
	for (i = 0; i < m_row; i++)
	{
		for (j = 0; j < m_col; j++)
		{
			if (m_maze[i][j] >= 0 && m_maze[i][j] < 10)
			{
				cout<<"  "<<m_maze[i][j];
			}
			else
			{
				cout<<" "<<m_maze[i][j];
			}
		}
		cout<<endl;
	}
}

PosType Maze::NextPos(PosType c, int d)
{
	PosType direct[4] = {{0,1},{1,0},{0,-1},{-1,0}};
	c.x += direct[d].x;
	c.y += direct[d].y;
	return c;
}

void main(int argc, char* argv[])
{
	PosType begin, end;
	int m, n;
	cout<<"请输入迷宫的行数和列数："<<endl;
	cin>>m>>n;
	Maze maze(m,n);
	maze.Input();
	maze.Print();

	cout<<"请输入入口位置（行数，列数）";
	cin>>begin.x>>begin.y;
	cout<<"请输入出口位置（行数，列数）";
	cin>>end.x>>end.y;
	bool b = maze.MazePath(begin, end);
	if (b)
	{
		cout<<"此迷宫从入口到出口的一条路径如下："<<endl;
		maze.Print();
	}
	else
	{
		cout<<"此迷宫没有从入口到出口的路径"<<endl;
	}
	system("pause");
}

4.3 表达式求值，例如求取表达式“7+(9-12/3)*4=”的值。

#include <iostream>
#include "SqStack.h"
#include <fstream>
using namespace std;

#define MaxExpLength 100
char ops[7] = {'+','-','*','/','(',')','='};
char cmp[7][7] = {
	{'>','>','<','<','<','>','>'},
	{'>','>','<','<','<','>','>'},
	{'>','>','>','>','<','>','>'},
	{'>','>','>','>','<','>','>'},
	{'<','<','<','<','<','=',' '},
	{'>','>','>','>',' ','>','>'},
	{'<','<','<','<','<',' ','='}
};

//判断ch是否为运算符
bool IsOperator(char ch)
{
	for (int i = 0; i < 7; i++)
	{
		if (ch == ops[i])
		{
			return true;
		}
	}
	return false;
}

//比较运算符的优先级
char Compare(char ch1, char ch2)
{
	char priority;
	int m,n;
	for (int i = 0; i < 7; i++)
	{
		if (ch1 == ops[i])
		{
			m = i;
		}
		if (ch2 == ops[i])
		{
			n = i;
		}
	}
	priority = cmp[m][n];
	return priority;
}

//计算z=x<op>y，若除数为0，则返回false
bool Compute(double x, char op, double y, double& z)
{
	switch (op)
	{
	case '+':
		z = x + y;
		break;
	case '-':
		z = x - y;
		break;
	case '*':
		z = x * y;
		break;
	case '/':
		if (y != 0.0)
		{
			z = x / y;
			break;
		}
		else
		{
			cout<<"除数为0，出错！"<<endl;
			return false;
		}
	}
	return true;
}

bool ExpEvaluation(char* str, double& result)
{
	double a, b, v;
	char ch, op;
	int temp, i = 0;
	SqStack<char> optr(20);
	SqStack<double> opnd(20);
	optr.Push('=');
	ch = str[i++];
	while (ch != '=' || optr.Top() != '=')
	{
		while (ch == ' ')
		{
			ch = str[i++];
		}
		if (IsOperator(ch)) //ch是操作符
		{
			switch(Compare(optr.Top(), ch))
			{
			case '<':
				optr.Push(ch);
				ch = str[i++];
				break;
			case '=':
				optr.Pop();
				ch = str[i++];
				break;
			case '>':
				op = optr.Top();
				optr.Pop();
				b = opnd.Top();
				opnd.Pop();
				a = opnd.Top();
				opnd.Pop();
				if (Compute(a,op,b,v))
				{
					opnd.Push(v);
					break;
				}
				else
				{
					result = 0;
					return false;
				}
			}
		}
		else //ch是数字
		{
			temp = ch - '0';
			ch = str[i++];
			while (!IsOperator(ch) && ch != ' ')
			{
				temp = temp * 10 + ch - '0';
				ch = str[i++];
			}
			opnd.Push(temp);
		}
	}
	result = opnd.Top();
	return true;
}

void main(int argc, char* argv[])
{
	int i = 0;
	double result;
	char* str;
	cout<<"请输入一个正确的四则表达式（以\"=\"结束，运算符为正整数）："<<endl;
	str = new char[MaxExpLength];
	ifstream input("input.txt");
	input>>str[i];
	while (str[i] != '=')
	{
		input>>str[++i];
	}
	if (ExpEvaluation(str, result))
	{
		cout<<"表达式的值是"<<result<<endl;
	}
	else
	{
		cout<<"ERROR"<<endl;
	}
	delete [] str; system("pause");
}

4.4 汉诺塔问题

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

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

int times;
//将第n个圆盘从x柱移到z柱
void move(int n, char x, char z)
{
	cout<<"第"<<++times<<"步，将"<<n<<"号盘从"<<x<<"移到"<<z<<endl;
}

//将a柱上按直径自上而下，由小到大编号为1至n的n个圆盘按规则搬到c柱上，b用作辅助柱
void hanoi(int n, char a, char b, char c)
{
	if (n == 1)
	{
		move(n, a, c);
	}
	else
	{
		hanoi(n-1, a, c, b);
		move(n, a, c);
		hanoi(n-1, b, a, c);
	}
}
void main(int argc, char* argv[])
{
	int n;
	cout<<"3个柱为a、b、c，圆盘最初在a柱，借助b柱移到c柱，请输入圆盘数：";
	cin>>n;
	hanoi(n, 'a', 'b', 'c');
	system("pause");
}

数据结构——栈

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构——栈

热门文章

最新文章

相关课程

相关电子书