概述
栈是一种限定仅在一端进行插入和删除的线性表。这一端被称为栈顶（top），栈的另一端叫做栈底（bottom）。通常，最先被压入栈中的元素会被放在栈底，后被压入的元素处于栈顶，出栈时，取出栈顶元素，因此通常为后进先出。
栈的经典应用有符号平衡的判断，后缀表达式求值等等问题。具体代码将在下一篇文章中给出。
基于栈的特性，一般常用的操作有：进栈push、出栈pop、读栈顶top、判断栈是否为空isEmpty和判断栈是否已满isFull。以下为C++的抽象数据类型定义，包含基本操作。
栈类抽象数据类型定义
下面给出C++类模板，名字为Stack，模板参数为元素类型T。
template <class T>
class Stack{
public:
void clear();
bool push(const T item);
bool pop(T & item);
bool top(T & item);
bool isEmpty();
bool isFull();
基本操作
基本操作分为进栈push、出栈pop、读栈顶top等。
-
push进栈
首先判断栈是否已满，即top指针是否指向栈顶，判断句为：
//判断栈是否已满
if(top == mSize - 1){
cout << "stack is full, cannot push element!" << endl;
类似的，判断栈是否为空，即top指针是否指向栈底下一位，一般为-1，判断句为：
//判断栈是否为空
if(top == -1){
cout << "empty" << endl;
当入栈时，将top指针的元素内容设定为value，然后将top指针上移一位修改栈顶指针，实现代码如下：
//入栈
void push(T item){
if(top == mSize - 1){
cout << "stack is full, cannot push element!" << endl;
return;
}
else{
st[++top]=item;
cout<<"入栈："<<item<<endl;
}
}
-
pop出栈
出栈时，每次只能移出栈顶元素。首先设定栈顶元素为item=stack[top]，再将top指针向下移动一位，即top--。如果top=-1时（栈为空），则无法出栈，输出empty。具体实现代码如下：
void pop(int &m){
// should be equal, not assignment
if(top == -1){
cout << "empty" << endl;
}
else{
m=st[top--];
cout<<"出栈："<<m<<endl;
}
}
-
top读取栈顶元素
即读取栈顶元素但不弹出。仅让item=stack[top]，top不做改变。代码 如下：
void getop(int &t){
if(top ==-1){
cout<<"empty!"<<endl;
}
else{
t=st[top];
cout<<"获得栈顶元素："<<t<<endl;
}
}
栈总体程序
实现功能：
1.首先输入栈长度。
2.输入操作指令：1、入栈。2、出栈。3、查看栈顶元素。4、查看栈信息（最大长度与现在长度）。
#include <iostream>
#include <stdio.h>
using namespace std;
template <class T>
class arrStack{
private:
int mSize;
int top;
T *st;
public:
arrStack(int size){
mSize=size;
top=-1;
st=new T[mSize];
}
~arrStack(){
delete[]st;
}
void clear(){
top=-1;
}
void push(T item){
if(top == mSize - 1){
cout << "stack is full, cannot push element!" << endl;
return;
}
else{
st[++top]=item;
cout<<"入栈："<<item<<endl;
}
}
void pop(int &m){
if(top == -1){
cout << "empty" << endl；
}
else{
m=st[top--];
cout<<"出栈："<<m<<endl;
}
}
void getop(int &t){
if(top ==-1){
cout<<"empty!"<<endl;
}
else{
t=st[top];
cout<<"获得栈顶元素："<<t<<endl;
}
}
int getMessage(int &m, int &n){
m=mSize;
n=top+1;
cout<<"栈最大长度为："<<m<<"\n栈长为："<<n<<endl;
return 0;
}
};
int main(){
int a;//length
int e;//switch
int i=0;
int m;//message
int n;//message
int f;//pop
int t;//getop
int num;
printf("请输入栈长度：");
cin>>a;
arrStack<int> s(a);
while(1){
cout<<"-----------------------------------------------\n"<<endl;
cout<<"请输入操作单位：\n1：入栈\n2：出栈\n3：获取栈顶元素\n4：获取栈信息\n"<<endl;
cin>>e;
switch(e){
case(1):
cout<<"请输入入栈元素："<<endl;
cin >>num;
s.push(num);
break;
case(2):
s.pop(f);
break;
case(3):
s.getop(t);
break;
case(4):
s.getMessage(m,n);
break;
}
}
system("pause");
return 1;
}
结果：
总结
新手上路，有缺陷的地方望指出，进步你我他~
现在再从头写一遍栈的内容，感觉老师讲过的东西都能明白了，也能明白她为什么这么讲。
一开始刚接触算法，不知道如何将算法和main函数结合起来，感谢导师帮我写了个简单的push(1/2/3)例子，让我能顺水推舟的把整个程序写完。
第二个遇到的是语法上的问题。比如说指针如何使用，int函数里返回值应该写什么，pop函数括号里为空时如何执行，有具体数值时如何执行。最后我把它们都弄懂了，也算是巨大的飞跃！估计下一个链式应该写的更顺一些。
这是我的第一篇简书！也是我除了hellow world的第一个真正意义上自己动手写的c++程序！！希望十年后可以再回头来看看它。
