用链表实现栈结构

大二真的不能颓废了，只能好好学习了。以后坚持每周一篇数据结构的文章吧

进入正题

线性结构中有表、栈、队列，其中，表的结构较为简单，也容易实现，任何一门高级语言都可以轻松实现表这个线性结构——数组，就是数组。数组这里就不在多讲了，今天主要讲的是栈这个数据结构以及用链表去实现这个数据结构。

栈这个数据结构先介绍一下，栈的数据出入很特别，后进先出，只能从一头进去，也只能从这头出来，就像装水的瓶子，永远是最接近瓶口的水先被倒出来，同时，最接近瓶口的水也是最后才进到水瓶中的。现在我觉得你大致了解了栈这个结构的特点了吧，那就开始用语言来实现吧

第一步，先定义一个结构体和一些数据以及操作函数

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

struct Node {
        //该结构体存储的数据信息
        ElementType element;
        //下一个元素的位置
        Position Next;
};

//初始链表为空
List MakeEmpty(List L);
//检查链表是否为空
int IsEmpty(List L);
//判断当前元素是否为下一个
int IsLast(Position x, List L);
//出栈
void Delete(List L);
//入栈
void Insert(int x, List L);
//删除一个链表
void DeleteList(List L);
//找到头节点的位置
Position Header(List L);
//返回第一个元素的位置
Position First(List L);
//遍历栈输出里面内容
void ShowStackInfo(List L);

这些信息我们定义在一个名为Stack.h的头文件当中

现在我们来实现具体的栈操作用

#include <stdio.h>
#include <stdlib.h>
#include "Stack.h"

//初始链表为空
List MakeEmpty(List L) {
    while (L -> Next != NULL)
        L -> element = 0;
    return L;
}
//检查链表是否为空
int IsEmpty(List L) {
    if (L -> Next == NULL)
        return 1;
    return 0;
}
//出栈
void Delete(List L) {
    Position position, tempCell;
    tempCell = L -> Next;
    position = tempCell -> Next;
    L -> Next = position;
    position -> previous = L;
    free(tempCell);
}
//入栈
void Insert(int x, List L) {
    Position position;
    position = malloc(sizeof(*L));
    if (position == NULL)
        return;
    position -> element = x;
    position -> Next = L -> Next;
    L -> Next = position;
}
//删除一个链表
void DeleteList(List L) {
    while (L -> Next != NULL)
        free(L -> Next);
    return;
}
//创建一个链表并返回头结点
Position Header() {
    Position L = malloc(sizeof(*L));
    if (L == NULL)
        return NULL;
    L -> Next = NULL;
    return L;
}
//返回第一个元素的位置
Position First(List L) {
}

//遍历栈输出里面内容
void ShowStackInfo(List L) {
    while(L != NULL &amp;&amp; L -> Next != NULL) {
        printf("%d ", L -> Next -> element);
        L = L -> Next;
    }
    return;
}

int main() {
    List L = Header();
    Insert(10, L);
    Insert(8, L);
    Insert(6, L);
    Insert(4, L);
    Insert(2, L);
    Insert(0, L);
    ShowStackInfo(L);
}