前言

第一次学数据结构，代码写的可能不是很好，大神勿喷，指出来就行。

读本文之前建议先学下链表

• C 实现链表 (如果觉得写得不好请评论)

栈(zhan, 第四声)

栈(stack)是很基本的数据结构。
可以这么理解，栈可以看作为一个筒状有弹簧的储钱罐，你把一枚硬币压进去就相当于入栈的操作，但是压入很多硬币之后，你也只能一个个得取出，这个过程就是十分基本的栈操作了。

下表便是一个简单的栈：

栈顶元素 n
元素 n-1
元素 n-2
……
元素 2
元素 1
栈底元素 0

操作

函数	操作
push()	向栈顶添加元素
pop()	移除栈顶的元素
top()	读取栈顶的元素
size()	栈元素的数量
empty()	看栈是否为空

图解push()
图解pop()

有了这些预备只是便可以用C语言来实现简单的栈了。

C语言用链表的简单实现(大神勿喷)

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

// 每个节点
struct Node
{
    int data; // 数据
    struct Node *pNext; // 下一个数据的指针
};

// 栈结构体
struct Stack
{
    struct Node *pNode; // 当前元素的指针
    int size; // 数量
};

// Operations

// 读取栈顶的元素
int top(struct Stack s)
{
    return (s.pNode) -> data;
}

// 向栈顶压入新的元素
int push(int data,struct Stack *s)
{
    struct Node *n = (struct Node*) malloc(sizeof(struct Node)); // 创建新的内存空间以便存放链表的元素
    n -> data = data; // 把数据塞到节点里
    if (s -> pNode == NULL)
    {
        n -> pNext = NULL; // 设置栈底的指针为空
    } else {
        n -> pNext = s -> pNode; // 设置上一个节点的指针
    }
    s -> pNode = n; // 设置栈顶的节点指针
    (s -> size) ++; // 元素数量+1
    return data;
}

// 删除栈顶的元素
void pop(struct Stack *s)
{
    struct Node *current = s -> pNode; // 获得当前节点
    if (current -> pNext != NULL) s -> pNode = current -> pNext; // 如果没到栈底，那就把d栈顶元素指向下一个节点
    else s -> pNode = NULL; // 到链表底部了，那就把栈的指针指向空
    free(current); // 释放移除元素的内存空间
    (s -> size) --; // 元素数量-1
}

// 看栈是否为空
int empty(struct Stack s)
{
    return s.size == 0;
}

// 测试
int main()
{
    struct Stack mStack = {NULL, 0}; // 初始化一个栈
    printf("pushed + %d! size = %d\n", push(10, &mStack), mStack.size); // 给栈压入新的元素10
    printf("pushed + %d! size = %d\n\n", push(3,&mStack), mStack.size); // 给栈压入新的元素3
    printf("top = %d\n", top(mStack)); // 输出此时栈顶的元素
    pop(&mStack); // 移除栈顶的元素
    printf("poped! size = %d\n", mStack.size); // 输出元素个数
    printf("top = %d\n", top(mStack)); // 输出此时栈顶的元素
    pop(&mStack); // 移除栈顶的元素
    printf("poped! size = %d\n", mStack.size); // 输出元素个数
    printf("isEmpty = %d\n", empty(mStack));
    return 0;
}