AI 助理
备案控制台
开发者社区 云计算 文章 正文

数据结构——栈

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

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
目录
相关文章
ephemerals__
|
7天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
71 9
德国都芳最好
|
1天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
26 21
html的七十二变
|
4天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
14 2
dufadayang
|
6天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
27 4
java冯坚持
|
29天前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
26 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
肾透侧视攻城狮
|
10天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
15 1
禁默
|
29天前
初步认识栈和队列
初步认识栈和队列
禁默
57 10
星霜旅人
|
23天前
数据结构（栈与列队）
数据结构（栈与列队）
星霜旅人
16 1
java冯坚持
|
29天前
|
算法
数据结构与算法二：栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用，并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
java冯坚持
41 3
神明木佑
|
28天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
神明木佑
63 1

热门文章

最新文章

  • 1
    数据结构~在页面上渲染树型结构
  • 2
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 3
    数据结构学习笔记【持续更新】
  • 4
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 5
    学数据结构，只需要基本的编程体验
  • 6
    算法导论第十四章 数据结构的扩张
  • 7
    【数据结构】C语言实现链式二叉树(附完整运行代码)
  • 8
    Python中的基础数据结构：列表（List）详解
  • 9
    攻克数据结构和算法——第五天：查找
  • 10
    数据结构上机实践第二周项目3——体验复杂度
  • 1
    `geopandas`是一个开源项目，它为Python提供了地理空间数据处理的能力。它基于`pandas`库，并扩展了其对地理空间数据（如点、线、多边形等）的支持。`GeoDataFrame`是`geopandas`中的核心数据结构，它类似于`pandas`的`DataFrame`，但包含了一个额外的地理列（通常是`geometry`列），用于存储地理空间数据。
    66
  • 2
    “解锁Python高级数据结构新姿势：图的表示与遍历，让你的算法思维跃升新高度
    39
  • 3
    Redis数据结构—跳跃表 skiplist 实现源码分析
    59
  • 4
    逆袭之路！用 Python 玩转图的 DFS 与 BFS，让数据结构难题无处遁形
    62
  • 5
    Python中的列表（List）和元组（Tuple）是两种重要的数据结构
    50
  • 6
    【数据结构OJ题】链表分割
    29
  • 7
    【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】
    43
  • 8
    【数据结构常见七大排序（二）】—选择排序篇【直接选择排序】And【堆排序】
    29
  • 9
    【数据结构常见七大排序（一）】—插入排序篇【直接插入排序】And【希尔排序】
    42
  • 10
    【数据结构OJ题】链表的回文结构
    36

    • 相关课程

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

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    DataWorks售前咨询