数据结构-栈

一.简介

栈的特点：
1）先进后出，即最先进栈的元素最后出栈。
2）栈只能从表的一端存取数据，另一端是封闭的。
上图中1是最先入栈的数据，其次是2,3,4。如果想把数据1从栈中取出，分别需要按顺序先取出数字4,3,2。

栈的开口端（头部）称为栈顶，封口端（尾部）称为栈底。上图中，栈顶元素是4，栈底元素是1。

二.链栈

链栈：使用链表实现栈存储结构
上图中的head指针指向栈顶节点，链表的头部节点作为栈顶节点。
数据入栈操作：将数据作为新的节点插入链表头部。
数据出栈操作：删除链表头部节点。

三.数据入栈

将数字1，2，3存入栈中，步骤如下：

1）创建head指针。

2）添加元素1：

head->1->NULL。head指针指向新增节点1。

3）添加元素2：

head->2->1->NULL。head指针指向新增节点2，节点2指向节点1。

4）添加元素3：

head->3->2->1->NULL。head指针指向新增节点3，节点3指向节点2，节点2指向节点1。

四.数据出栈

初始链栈：head->3->2->1->NULL。

1）元素3出栈：

head->2->1->NULL。

2）元素2出栈：

head->1->NULL。

3）元素1出栈：

head->NULL。

五.源代码

#include <stdio.h>
#include <stdlib.h>
typedef struct ListStack{
    int data;
    struct ListStack *pNext;
}ListStack;

//入栈
ListStack *pushStack(ListStack *pHead,int data)
{
    //创建新节点
    ListStack *pNode = (ListStack *)malloc(sizeof(ListStack));
    pNode->data = data;
    //头结点和新节点建立联系
    pNode->pNext = pHead;
    printf("入栈元素：%d\n",data);
    //更新头指针的指向
    pHead = pNode;
    return pHead;
}

//出栈
ListStack *popStack(ListStack *pHead)
{
    if(pHead != NULL)
    {
        //出栈节点
        ListStack *pNode = pHead;
        printf("出栈元素：%d\n",pNode->data);
        //更新头指针
        pHead = pNode->pNext;
        if(pHead == NULL)
        {
            printf("栈已空\n");
        }

        free(pNode);
        pNode = NULL;
    }
    else
    {
        printf("栈内没有元素\n");
    }
    return pHead;
}

int main() {
    printf("链式栈：入栈、出栈!\n");
    ListStack *pHead = NULL;//创建头节点指针
    pHead = pushStack(pHead,1);
    pHead = pushStack(pHead,2);
    pHead = pushStack(pHead,3);

    pHead = popStack(pHead);
    pHead = popStack(pHead);
    pHead = popStack(pHead);
    pHead = popStack(pHead);

    return 0;
}

六.运行效果

使用CLion IDE创建工程，编译运行结果如下：