备案控制台
探索云世界
开发者社区 云计算 文章 正文

数据结构——栈

2016-05-18 1175
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

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");
}


转载：http://blog.csdn.net/foreverling/article/details/43114303

文章标签：
云数据库 ClickHouse
存储
关键词：
数据结构栈
shy丶gril
目录
相关文章
Kevin_17
|
18天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列（二）：队列
深入理解栈和队列（二）：队列
Kevin_17
33 0
起飞的风筝
|
1月前
【栈】数据结构栈的实现
【栈】数据结构栈的实现
起飞的风筝
32 0
诡异森林。
|
1月前
|
存储
数据结构--栈和队列
数据结构--栈和队列
诡异森林。
34 1
鲜于言悠
|
1月前
|
存储 算法 数据处理
数据结构从入门到精通——栈
栈，作为一种后进先出（LIFO）的数据结构，在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而，如果我们跳出传统思维的束缚，会发现栈的用途远不止于此。
鲜于言悠
58 0
GOTXX
|
1月前
|
C语言
数据结构之栈详解（C语言手撕）
数据结构之栈详解（C语言手撕）
GOTXX
37 1
图灵重生我名苏泽
|
1月前
R7-2 栈的实现及基本操作
R7-2 栈的实现及基本操作
图灵重生我名苏泽
19 1
Y小夜
|
1月前
|
存储 算法
数据结构— —栈的基本操作（顺序栈和链栈）
数据结构— —栈的基本操作（顺序栈和链栈）
Y小夜
58 0
yma16
|
1天前
|
C语言
数据结构中顺序栈的进栈和出栈用C语言表示
数据结构中顺序栈的进栈和出栈用C语言表示
yma16
10 1
时雨h
|
11天前
|
存储 算法 调度
数据结构期末复习（3）栈和队列
数据结构期末复习（3）栈和队列
时雨h
18 0
阿森要自信
|
23天前
|
存储 缓存 算法
【算法与数据结构】栈的实现详解
【算法与数据结构】栈的实现详解
阿森要自信
18 0

热门文章

最新文章

  • 1
    数据结构期末复习（fengkao课堂）
  • 2
    【C/C++ 数据结构 】从零开始实现哈希表：C++实践指南
  • 3
    Java数据结构与算法-java数据结构与算法（二）
  • 4
    【数据结构】【版本2.0】【树形深渊】——二叉树入侵
  • 5
    【C/C++ 数据结构 树】探索C/C++中的二叉树：从理论到实践
  • 6
    【C/C++ 数据结构 线性表】深入理解与实现栈：从基础到应用的全面探索
  • 7
    数据结构-概念版（七）
  • 8
    Java数据结构与算法-java数据结构与算法（五）
  • 9
    【C/C++ 数据结构】深入探索数据结构中算法复杂度：从C++和数学的视角
  • 10
    python学习-函数模块，数据结构，字符串和列表（下）
  • 1
    【手撕数据结构】二分查找(好多细节)
    16
  • 2
    【数据结构与算法】—— 手撕红黑树
    37
  • 3
    【排序算法】数据结构排序详解
    42
  • 4
    【链式二叉树】数据结构链式二叉树的（万字详解）
    42
  • 5
    【堆】数据结构堆的实现（万字详解）
    52
  • 6
    【树和二叉树】数据结构二叉树和树的概念认识
    25
  • 7
    【双向链表】数据结构双向链表的实现
    21
  • 8
    数据结构——单链表的基本操作
    11
  • 9
    数据结构——排序算法之快速排序
    34
  • 10
    数据结构——二叉树的链式结构
    36

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）