文档介绍：?网络游戏算法设计?第2章算法分析与数据结构主要内容:学习目标:?第2章算法分析与数据结构?栈的基本运算?栈的存储结构?迷宫问题的实现?了解栈的基本运算?了解栈的存储结构?了解迷宫问题的实现重点:难点:?第2章算法分析与数据结构?栈的基本运算?栈的存储结构?迷宫问题的实现?栈的基本运算?栈的存储结构? 栈栈是一种只允许在一端进行插入和删除的线性表,它是一种操作受限的线性表。在表中只允许进行插入和删除的一端称为栈顶,另一端称为栈底。栈的插入操作通常称为入栈或进栈,而栈的删除操作则称为出栈或退栈。当栈中没有数据元素时,称为空栈。 线性表栈通常用指针top指示栈顶的位置,用指针bottom指向栈底。栈顶指针top动态反映栈的当前位置。入栈时,新加入的元素变成新的栈顶,栈顶指针top指向新加入的元素;出栈时,它指向出栈元素的下一个元素, 线性表?栈的基本运算栈的基本运算包括以下6种:1)StackFull判断是否栈满;2)Empty() 栈的空判断:若栈为空,则返回TRUE;否则,返回FALSE;3)Push(x) 入栈:在栈的顶部插入元素x,若栈满,则返回FALSE;否则,返回TRUE;4)Pop() 出栈:若栈不空,则返回栈顶元素,并从栈顶中删除该元素;否则,返回空元素NULL;5)GetTop() 取栈元素:若栈不空,则返回栈顶元素;否则返回空元素NULL;6)SetEmpty() 置栈空操作:置栈为空栈。 线性表?栈的存储结构const unsigned STACKSIZE = 10; // 定义栈的最大容量class Stack{unsigned m_nTop; int m_StackData[STACKSIZE];public:Stack() : m_nTop(0) {}bool Empty()const; // 判断栈是否为空bool StackFull() const; // 判断栈是否满void Push(int data); // 将data数据压入栈中int Pop(); // 将栈顶数据弹出int GetTop() const; // 获取栈顶数据void SetEmpty(); // 将栈设为空}; 线性表1)Push(x)入栈void GameCollege::Stack::Push(int data){if (StackFull()){Exception e("栈已经满,无法进行压入操作");throw e;}m_StackData[m_nTop++] = data; // 将数据压入栈中}m_nTop用来表示栈顶位置,它对应m_StackData数组单元的位置,当有数据需要压入栈中,只要通过m_nTop找到m_StackData数组相对应的单元, 线性表2)Pop()出栈int GameCollege::Stack::Pop(){if (Empty()){Exception e("栈已空,无法进行出栈操作");throw e;}return m_StackData[--m_nTop];} 线性表3)StackFull判断是否栈满bool GameCollege::Stack::StackFull()const {return m_nTop == STACKSIZE; }4)Empty()空栈判断。bool GameCollege::Stack::Empty() const{return m_nTop == 0;}