数据结构第三章，栈、队列、数组，期末不挂科指南，第3篇

栈和队列可以看做是特殊的线性表 。它们的特殊性表现在它们的基本运算是线性表运算的子集，它们是运算受限的线性表

• 初始化 InitStack(S) 构造一个空栈S


• 判断栈空 EmptyStack(S) 若栈为空，返回1，否则返回0


• 进栈Push(S,x) 将元素x插入栈S中


• 出栈Pop(S) 删除栈顶元素


• 取栈顶GetTop(S) 返回栈顶元素

链栈将链表头部作为栈顶的一端，可以避免在实现数据“入栈”和“出栈”操作时做大量遍历链表的耗时操作

链表的头部作为栈顶，有如下的好处

1. 入栈 操作时，只需要将数据从链表的头部插入即可


2. 出栈 操作时，只需要删除链表头部的首结点即可

结论：链表实际上就是一个只能采用头插法插入或删除的链表

例子：将元素1，2，3，4依次入栈，等价于将各元素采用头插法依次添加到链表中

图片来源网络

完整代码如下

由于比较简单，直接贴上了

#include
#include
typedef struct node{
int data; //数据域
struct node *next; //链域
} LkStk;
//初始化
void init(LkStk *ls){
printf("初始化操作n");
ls = (LkStk *)malloc(sizeof(LkStk));
ls->next = NULL;
}
// 进栈
void push(LkStk *ls,int x){
printf("进栈操作n");
LkStk *temp;
temp = (LkStk*)malloc(sizeof(LkStk));//给temp新申请一块空间
temp->data = x;
temp->next = ls->next;
ls->next = temp;
printf("%d进栈成功n",x);
}
int empty(LkStk *ls){
if(ls->next ==NULL){
return 1;
}
else return 0;
}
// 出栈
int pop(LkStk *ls){
LkStk *temp;
//判断栈是否为空
if(!empty(ls)){
temp= ls->next; // 准备出栈的元素指向ls的下一结点
ls->next = temp->next; // 原栈顶的下一个结点称为新的栈顶
printf("栈顶元素：%dn",temp->data);
free(temp); //释放原栈顶的结点空间
return 1;
}
return 0;
}
int main()
{
LkStk ls;
init(&ls);

push(&ls,1);
push(&ls,2);

pop(&ls);
pop(&ls);
return 0;
}


这就是链栈的基本进栈和出栈了，当然，我们还可以获取一下栈顶元素

设一个链栈的输入序列为A、B、C，试写出所得到的所有可能的输出序列，即输出出栈操作的数据元素序列

写答案的时候，记住先进后出原则

从A开始写

A进，A出，B进，B出，C进，C出

A进，B进，B出，C进，C出，A出

… …

继续写下去就可以了，一定不要出现A进，B进，B出，C进，A出 注意，A出不去，A前面有C呢

在来一个例题

如图所示，在栈的输入端元素的输入顺序为A，B，C，D，进栈过程中可以退栈，写出在栈的输出端以A开头和以B开头的所有输出序列。

这个就是把A开头和B开头的都写出来

1. ABCD、ABDC、ACBD、ACDB、ADCB


2. BACD、BADC、BCAD、BCDA、BDCA

主要仔细，就能写对，套路就是，先进后出