栈
一.定义
栈又称堆栈（stack），是一种可以实现“先进后出”的储存结构。“先进后出”意为只能在栈顶添加或删除数据等操作，而不能在栈底操作。栈就类似于一个箱子，只能从箱子的顶部放入，第一个放进去的在箱子的最下端，最后一个放进去的在箱子最顶端。若想删除栈中的数据，则应按从最顶端向下直至最下端的顺序删除。
二.分类
栈分为两类，第一为静态栈，第二为动态栈，动态栈与链表相似，只是对链表有所限制。
三.基本操作
栈的基本操作包括创建栈、销毁栈、出栈、入栈、获取栈顶元素、获取栈的大小、清空栈。
1.入栈
p->next=ln->next;
ln->next=p;
2.出栈
p=ln->next;
*x=p->data;
ln->next=p->next;
free(p);
3.栈链的实现
#include<stdio.h>
#include<stdlib.h>
typedef struct Lnode
{
int data;
struct Lnode *next;
}Lnode;
//初始化链栈
void initStack(Lnode *ln)
{
ln=(Lnode *)malloc(sizeof(Lnode));
ln->next=NULL;
}
//判断链栈是否为空
int StackEmpty(Lnode *ln)
{
return (ln->next==NULL?1:0);
}
//进栈
void push(Lnode *ln,int x)
{
Lnode *p;
p=(Lnode *)malloc(sizeof(Lnode));
if(p ==NULL){
printf("ERROR");
exit(0);
}
p->next=NULL;
p->data=x;
p->next=ln->next;
ln->next=p;
}
//出栈
int pop(Lnode *ln,int *x)
{
Lnode *p=ln->next;
if(p ==NULL){
return 0;
}
*x=p->data;
ln->next=p->next;
free(p);
return 1;
}
void printStack(Lnode *ln)
{
Lnode *p=ln->next;
while(p!=NULL){
printf("%d\n",p->data);
p=p->next;
}
}
void main()
{
Lnode ln;
int x;
initStack(&ln);
push(&ln,1);
push(&ln,2);
push(&ln,3);
push(&ln,4);
pop(&ln,&x);
printf("出栈元素为：%d\n",x);
printStack(&ln);
}
按照先进后出的储存方式，那么输出的结果应为，4,3,2,1，而不是1,2,3,4。
四.栈的应用
1.函数调用
2.中断
3.表达式求值（自制计算器）
4.内存分配
5.缓冲处理
6.迷宫