栈的链式存储结构简称为 链式栈
链式栈是通过单链表来实现的。每次入栈一个元素，向链表中添加一个节点(相当于头插法)，出栈一个元素，释放一个节点。
链式栈是通过单链表来实现的。每次入栈一个元素，向链表中添加一个节点，出栈一个元素，释放一个节点。因为栈具有“后进先出”的特点，如果每次在链表的尾部进行插入和删除，就要遍历整个链表来找到尾节点。而在头部进行插入和删除时，只需根据头指针即可找到链表的首元素结点。而无需遍历链表。所以链式栈的出，入栈通过对链表进行头删和头插来实现。
1. 链式栈的结点结构
链式栈是有单链表来实现的，所以与单链表的结点结构相同。由数据域和指向下一个结点的指针域（next域）组成。
//链式结构 =数据域+指针域
struct Node
{
int data;
struct Node *next;
};
2. 链式栈的初始化
与单链表的初始化相同，可以设置函数单独先对每个节点进行初始化操作。
// 2、创建节点 为插入做准备，学习数据的时候，一定要把功能划分明确
struct Node *createNode(int data)
{
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode; 返回指针变量
}
3、表头插入
// 插在头结点之后 插队插入，不能越过头结点
// 插队插入，不能越过头结点
void insertNodeByHead(struct Node *headNode, int data) //表头法插入
{
// 1、插入的新节点的定义变量
struct Node* newNode = createNode(data);
// 2、 插在头结点之后 插队插入，不能越过头结点
newNode->next = headNode->next;
headNode->next = newNode;
}
4、打印，浏览信息
void printList(struct Node *headNode) //打印，浏览信息
{
// 有表头，要从第二个节点开始打印
struct Node *pMove = headNode->next;
while (pMove != NULL)
{
printf("%dt", pMove->data);
pMove = pMove->next;
}
printf("n");
}
5、栈操作
struct stack
{
struct Node* stackTop; // 用栈顶指针表示整个链表
int size; // 数据结构中的万金油 记录数据结构中元素的个数
};
// 1、指针----->指针变量 动态内存申请
// 2、初始化变量
// 3、返回变量
struct stack *createStack()
{
//1、指针----->指针变量
struct stack *mystack = (struct stack*)malloc(sizeof(struct stack));
//2、初始化变量
mystack->size = 0;
mystack->stackTop = NULL;
//3、返回变量
return mystack;
}
//入栈函数
void push(struct stack *mystack, int data)
{
//入栈操作----->链表的表头插入
//无表头的链表
struct Node *newNode = createNode(data);
newNode->next = mystack->stackTop; //新来元素的下一个next指向栈顶指针，连续存储
mystack->stackTop = newNode; //用栈顶指针 永远指向新来的元素
mystack->size++;
}
int getTop(struct stack *mystack) //获取栈顶元素
{
if (mystack->size == 0)
{
printf("栈为空！，无法获取");
system("pause");
return mystack->size;
}
return mystack->stackTop->data;
}
void pop(struct stack *mystack)
{
if (mystack->size == 0)
{
printf("栈为空！，无法出栈");
system("pause");
}
else
{
// 无表头的链表进行删除
struct Node *nextNode = mystack->stackTop->next; //先保存记录
free(mystack->stackTop); //将原先节点的占用的内存释放
mystack->stackTop = nextNode;
mystack->size--;
}
}
int empty(struct stack *mystack)
{
if (mystack->size == 0)
{
return 0;
}
else
return 1;//返回1，代表栈不为空
}
6、总代码
#include#include //链式结构 =数据域+指针域 struct Node { int data; struct Node *next; }; // 2、创建节点 为插入做准备，学习数据的时候，一定要把功能划分明确 struct Node *createNode(int data) { struct Node *newNode = (struct Node *)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; return newNode; 返回指针变量 } // 3、表头插入 // 插在头结点之后 插队插入，不能越过头结点 // 插队插入，不能越过头结点 // 函数参数设计是具有含义的：插入那个链表？？插入的新节点的定义变量 void insertNodeByHead(struct Node *headNode, int data) //表头法插入 { // 1、插入的新节点的定义变量 struct Node* newNode = createNode(data); // 2、 插在头结点之后 插队插入，不能越过头结点 newNode->next = headNode->next; headNode->next = newNode; } // 4、表尾插入 void insertNodeByTail(struct Node *headNode, int data) { struct Node* newNode = createNode(data); struct Node* tailNode = headNode; while (tailNode->next != NULL) { tailNode = tailNode->next; } tailNode->next = newNode; } void printList(struct Node *headNode) //打印，浏览信息 { // 有表头，要从第二个节点开始打印 struct Node *pMove = headNode->next; while (pMove != NULL) { printf("%dt", pMove->data); pMove = pMove->next; } printf("n"); } // 用结构体封装一个栈 struct stack { struct Node* stackTop; // 用栈顶指针表示整个链表 int size; // 数据结构中的万金油 记录数据结构中元素的个数 }; // 1、指针----->指针变量 动态内存申请 // 2、初始化变量 // 3、返回变量 struct stack *createStack() { //1、指针----->指针变量 struct stack *mystack = (struct stack*)malloc(sizeof(struct stack)); //2、初始化变量 mystack->size = 0; mystack->stackTop = NULL; //3、返回变量 return mystack; } //入栈函数 void push(struct stack *mystack, int data) { //入栈操作----->链表的表头插入 //无表头的链表 struct Node *newNode = createNode(data); newNode->next = mystack->stackTop; //新来元素的下一个next指向栈顶指针，连续存储 mystack->stackTop = newNode; //用栈顶指针 永远指向新来的元素 mystack->size++; } int getTop(struct stack *mystack) //获取栈顶元素 { if (mystack->size == 0) { printf("栈为空！，无法获取"); system("pause"); return mystack->size; } return mystack->stackTop->data; } void pop(struct stack *mystack) { if (mystack->size == 0) { printf("栈为空！，无法出栈"); system("pause"); } else { // 无表头的链表进行删除 struct Node *nextNode = mystack->stackTop->next; //先保存记录 free(mystack->stackTop); //将原先节点的占用的内存释放 mystack->stackTop = nextNode; mystack->size--; } } int empty(struct stack *mystack) { if (mystack->size == 0) { return 0; } else return 1;//返回1，代表栈不为空 } int main() { //1、链表的实质：结构体变量 和结构体变量 连接在一起 struct stack *mystack = createStack(); push(mystack, 1); push(mystack, 2); push(mystack, 3); push(mystack, 4); push(mystack, 5); while (empty(mystack)) { printf("%d---->t", getTop(mystack)); pop(mystack); } printf("n"); system("pause"); return 0; }
将1 2 3 4 5 入栈，然后出栈
