一.堆栈的定义
何为堆栈
堆栈（简称栈）是一种最常用和最重要的数据结构，是一种只能在一段进行插入或删除数据操作的线性表。表中允许需进行插入、删除操作的一段称为栈顶。栈顶当前位置是动态的，由一个称为栈顶指针的位置指示器表示。表的另一端成为栈底。当战中没有数据元素是，称为空栈。栈的插入操作通常称为进栈或入栈。站的删除操作通常称为退栈或出栈。
栈的主要特点是“后进先出”（FILO )(First in last out)，即后入栈的元素先弹出。每次进栈的数据元素都放在当前栈顶元素之上，成为新的栈顶元素，每次出栈的都是原当前栈顶元素。
栈的基本操作
常用操作如下：
1.初始化栈------init();
2.入栈------push();
3.出栈------pop();
4.取栈顶元素------gettop();
5.判断栈是否为空------empty();
6.显示栈元素------display();
7.释放栈------setnull();
二.指针仿真堆栈（其实根本不用这么麻烦）
#include <iostream>
#include <cstdio>
using namespace std;
typedef struct Stack * link;
typedef struct Stack Snode;
struct Stack
{
int data;
struct Stack *next;
};
link init() //初始化栈
{
link p;
p=NULL;
return p;
}
link push(link Head,int x) //入栈
{
link p;
p=new Snode;
if(p==NULL)
{
cout<<"\nMemory Error\n";
return Head;
}
p->data=x;
p->next=Head;
return p;
}
link pop(link Head) //出栈
{
link p;
p=Head;
if(p==NULL)
cout<<"\nStack Is Empty\n";
else
{
p=p->next;
delete(Head);
}
return p;
}
link setnull(link Head) //释放栈
{
link p;
p=Head;
while(p!=NULL)
{
p=p->next;
delete(Head);
Head=p;
}
return Head;
}
int lenth(link Head) //获得栈内元素个数
{
int len=0;
link p;
p=Head;
while(p!=NULL)
{
len++;
p=p->next;
}
return len;
}
int gettop(link Head) //获得栈顶元素
{
if(Head==NULL)
{
cout<<"\nStack Is Empty\n";
return -1;
}
else
return Head->data;
}
void display(link Head) //显示栈内元素
{
link p;
p=Head;
if(p==NULL)
cout<<"\nStack Is Empty\n";
else
do
{
cout<<p->data<<" ";
p=p->next;
}while(p!=NULL);
}
int empty(link Head) //判断栈是否为空
{
if(Head==NULL)
return 1;
else
return 0;
}
int main()
{
int i,x;
link head1;
head1=init();
while(i!=6)
{
system("cls");
cout<<"\n1.Input a stack data";
cout<<"\n2.Output a stack data";
cout<<"\n3.Empty or Not";
cout<<"\n4.Display a top or stack";
cout<<"\n5.Display the lenth of the stack";
cout<<"\n6.Exit and Free Stack\n";
display(head1);
cout<<"\n";
cin>>i;
switch(i)
{
case 1:while(1)
{
system("cls");
cout<<"\ninput a number: until enter -1:\n";
cin>>x;
if(x==-1)
break;
head1=push(head1,x);
}
break;
case 2: head1=pop(head1);
break;
case 3:if(empty(head1))
cout<<"\nStack is empty\n";
else
cout<<"\nStack is not empty";
system("pause");
break;
case 4:cout<<"\nThe top is"<<gettop(head1)<<endl;
system("pause");
break;
case 5:cout<<"\n The length of stack is"<<lenth(head1)<<endl;
system("pause");
break;
}
}
system("cls");
head1=setnull(head1);
display(head1);
getchar();
return 0;
}
三.C++自带STL大法
C++自带的STL给我们提供了很多方便，stack就是其中之一！
STL中stack有5个常用操作：
top()------取栈顶元素；
push()------入栈；
pop()------出栈；
size()------返回栈中数据个数；
empty()------判断栈是否为空。
于是实现栈操作的代码变得十分简单...
#include <stack> //记住要引用<stack>库
#include <cstdio>
using namespace std;
int main()
{
stack<int>,a;
for (int i = 0; i < 10; i++) //入栈
{
a.push(i);
}
printf("%d\n", a.size()); //输出栈的大小
while (!a.empty()) //取栈项元素并将数据出栈
{
printf("%d ", a.top());
a.pop();
}
putchar('\n');
return 0;
} 但大部分情况，手写stack要快于stl的stack
所以如果考试怕被卡常数，或者时间足够，还是要手写哦!
（当然我上面手写的是最麻烦的一种^_^）
