一、特点
1. 栈——的特点是 “先进后出”；
像火车的进出站一样：
二、栈种类顺序栈和链栈
顺序栈：
初始化：
typedef struct zhan
{
int *top;
int *end;
int maxsize;
}jian;
入栈：
void chuangjian()
{
int x,n;
int *p;
L.top=(int* )malloc(L.maxsize* sizeof(int)); //为int类型的申请的空间
//S.base =new SElemType[MAXSIZE]；也可用c++申请空间的方法申请空间（了解一下malloc和new的区别）
printf("输入栈的最大的空间\n");
scanf("%d",&L.maxsize);
L.end = L.top;
printf("输入数据\n");
while((L.top-L.end)<L.maxsize)
{
scanf("%d",&x);
*L.top=x;
L.top++;
}
}
打印：
void shuchu()
{
int *p;
p=L.end;
while(p!=L.top)
{
printf("%d ",*p);
p++;
}
}
出栈：
void shanchu()
{
int n;
printf("输出需要删除的数量\n");
scanf("%d",&n);
for(;n>=1&&(L.top!=L.end);n--)
{
L.top--;
}
shuchu();
}
完整代码：
#include<stdio.h>
#include<stdlib.h>
typedef struct zhan
{
int *top;
int *end;
int maxsize;
}jian;
jian L;
void chuangjian()
{
int x,n;
int *p;
L.top=(int* )malloc(L.maxsize* sizeof(int)); //为int类型的申请的空间
//S.base =new SElemType[MAXSIZE]；也可用c++申请空间的方法申请空间（了解一下malloc和new的区别）
printf("输入栈的最大的空间\n");
scanf("%d",&L.maxsize);
L.end = L.top;
printf("输入数据\n");
while((L.top-L.end)<L.maxsize)
{
scanf("%d",&x);
*L.top=x;
L.top++;
}
}
void shuchu()
{
int *p;
p=L.end;
while(p!=L.top)
{
printf("%d ",*p);
p++;
}
}
void shanchu()
{
int n;
printf("输出需要删除的数量\n");
scanf("%d",&n);
for(;n>=1&&(L.top!=L.end);n--)
{
L.top--;
}
shuchu();
}
int main()
{
chuangjian();
shuchu();
shanchu();
return 0;
}
链栈：
初始化：
typedef struct zhan
{
int data;
struct zhan *next;
}zhan;
入栈：
void shuru()
{
int n;
zhan *p;
//头插法建立链栈
L=(zhan *)malloc(sizeof(zhan));
L->next=NULL;
printf("需要输入数据的个数\n");
scanf("%d\n",&n);
for(;n>0;n--)
{
p=(zhan *)malloc(sizeof(zhan));
scanf("%d",&p->data);
p->next=L;
L=p;
//此处不能free(p)或delete p 因为p和L为同一个节点释放p即使是删除L
}
}
出栈：
void shanchu()
{
int n;
printf("\n");
printf("输入需要删除的数量\n");
scanf("%d",&n);
while(n>=1&&L->next!=NULL)
{
L=L->next;
n--;
}
shuchu();
}
完整代码：
#include<stdio.h>
#include<stdlib.h>
typedef struct zhan
{
int data;
struct zhan *next;
}zhan;
zhan *L;
void shuru()
{
int n;
zhan *p;
//头插法建立链栈
L=(zhan *)malloc(sizeof(zhan));
L->next=NULL;
printf("需要输入数据的个数\n");
scanf("%d\n",&n);
for(;n>0;n--)
{
p=(zhan *)malloc(sizeof(zhan));
scanf("%d",&p->data);
p->next=L;
L=p;
//此处不能free(p)或delete p 因为p和L为同一个节点释放p即使是删除L
}
}
void shuchu()
{
zhan *p;
p=(zhan *)malloc(sizeof(zhan));
p=L;
while(p->next!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
}
void shanchu()
{
int n;
printf("\n");
printf("输入需要删除的数量\n");
scanf("%d",&n);
while(n>=1&&L->next!=NULL)
{
L=L->next;
n--;
}
shuchu();
}
int main()
{
shuru();
shuchu();
shanchu() ;
}
三、常考题：
一个栈的入栈序列是 a,b,c,d,e,则栈的不可能的输出序列是（ ）
a) edcba
b) decba
c) dceab
d) abcde
c答案是错的 a b c d入栈然后d c 出栈 然后e入栈然后出栈接着此时a在b下一层根据先入后出，无法输出a b