栈

栈的定义 栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。入栈是从栈顶入，出栈也是先从栈顶出。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。是FILO(first in last out)结构。就像手机上子弹一样，先压进弹夹的子弹最后才出来。

栈和堆的区别

http://zhidao.baidu.com/link?url=CAp8ltIWxF5AKHKrLgmoQLDsrVDpeZStjYxJ_2x9zWhM-2haPNdJweRxrmFrpm3WMqznwSWxZ81GMwRTQ-a_3_

栈的应用 栈也分为顺序结构和链式结构，由于栈中不常需要在任意位置插入和删除，所以链式结构不常用。那么，栈可以用来做什么呢？首先，在大家都用过的word文档里面，有个撤销（undo）功能，这个就需要栈上场了。在输入一段字后，这段数据就会存入数据区。一旦要撤销这段字，那就使数据区里的这段字出栈。第二个是表达式求值，一般用于现在的计算器中。老式的计算器是没有括号的，即是一个加减乘除混合运算要分开优先级计算。而现在的计算器有括号了，那么计算的时候可以通过判断括号来区分优先级。而判断括号就需要用到栈了。首先“（”入栈，然后接着是数字以及操作符入栈，一旦发现有“）”，那么就栈内就开始运算，差不多就是这个原理。最后还有个两栈共享空间，有兴趣的可以自己去看下。 参考：

http://blog.csdn.net/pony_maggie/article/details/30802249

先看头文件

栈的头文件： class MyStack { public: MyStack(int size); //初始化栈 ~MyStack(); //构销函数 int GetLenth(); //得到栈内元素个数 bool StackFull(); //判断栈是否为满，满则无法入栈 bool StackEmpty(); //判断栈是否为空，空则无法出栈 bool EnStack(int element); //元素入栈 bool DeStack(int &element); //元素出栈 void StackClear(); //清空栈 void StackTravel(); //遍历栈 private: int *m_pStack; //栈指针 int m_iTop; //栈顶，栈顶m_itop即是栈的元素数量 int m_iSize; //栈的容量 };

进栈算法 ①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）； ②置TOP=TOP+1（栈指针加1，指向进栈地址）； ③S(TOP)=X，结束（X为新进栈的元素）；

退栈算法 ①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)； ②X=S(TOP)，（退栈后的元素赋给X）： ③TOP=TOP-1，结束（栈指针减1，指向栈顶）。

主要注意出栈时，由于由于栈顶下标是指向下一个空的储存单元的，所以top要减1，回到有数据的储存单元。

bool MyStack::DeStack(int &element) { if (StackEmpty()) //空则无法出栈 { return false; } //由于栈顶下标是指向下一个空的储存单元的，所以top要减1，回到有数据的储存单元中 m_iTop--; element = m_pStack[m_iTop]; //此时element才能得到栈顶的元素 return true; }

遍历的话可以从底部开始遍历也可以从顶部开始遍历。 以下是全部文件：

文件：MyStack.cpp #include "MyStack.h" #include <iostream> using namespace std; MyStack::MyStack(int size) { m_iSize = size; m_iTop = 0; m_pStack = new int[m_iSize]; } MyStack::~MyStack() { delete []m_pStack; m_pStack = NULL; } int MyStack::GetLenth() { return m_iTop; //此时栈顶即是栈内元素个数 } bool MyStack::StackEmpty() { if (m_iTop == 0) { return true; } return false; } bool MyStack::StackFull() { if (m_iTop == m_iSize) { return true; } return false; } void MyStack::StackClear() { m_iTop = 0; //只是栈顶清零，而储存空间不变 } bool MyStack::EnStack(int element) { if (StackFull()) //满则无法入栈 { return false; } m_pStack[m_iTop] = element; m_iTop++; //入栈后栈顶加1 return true; } bool MyStack::DeStack(int &element) { if (StackEmpty()) //空则无法出栈 { return false; } //由于栈顶下标是指向下一个空的储存单元的，所以top要减1，回到有数据的储存单元中 m_iTop--; element = m_pStack[m_iTop]; //此时element才能得到栈顶的元素 return true; } void MyStack::StackTravel() { for (int i = 0; i < GetLenth(); i++) //从底部遍历栈 { cout << m_pStack[i] << endl; } /*栈的遍历可以从底部遍历也可以从顶部遍历 如果是从顶部遍历的话： for (int i = GetLenth(); i >=0 ; i++) { cout << m_pStack[i] << endl; } */ } #include "MyStack.h" #include <iostream> using namespace std; int main() { MyStack *p = new MyStack(4); int e = 0; cout << "now the lenth is:" << p->GetLenth() << endl; //得到此时长度为0 p->DeStack(e); //栈为空，无法出栈 p->EnStack(1); //入栈 p->EnStack(2); p->StackTravel(); //打印出1，2 cout << endl << "now the lenth is:" << p->GetLenth() << endl; //得到此时长度为2 p->DeStack(e); //出队 cout << e << endl<<endl; //打印出2 p->StackTravel(); //只打印出1 cout << endl; p->EnStack(2); //入队 p->EnStack(3); p->EnStack(4); p->EnStack(5); //此时栈为满不能入栈 p->StackTravel(); //打印出1，2，3，4 cout << endl << "now the lenth is:" << p->GetLenth() << endl; //得到此时长度为4 p->StackClear(); //清空栈 p->StackTravel(); //什么都打不出 p->~MyStack(); //构销栈 system("pause"); }