栈的简介

栈是所有数据结构中最常用的之一，栈是一个行动受限的线性表。
它具有后进先出的特点，这一点区别于队列的先进先出。他仅允许插入栈首和弹出栈首的操作，不被允许任意的插入和清除。

基本的API

1. push
2. pop
3. size

写栈结构的简单思路

已知栈是一个线性表，我们所能想到的第一个就是用链表来实现它。

链表是采用不连续的内存地址来存储数据，各个地址间用指针来相连。

链表节点基本的结构 ：

// 定义 Node 结构体 
typedef struct Node {
    int val;
    struct Node* next;
} Node;

完整代码

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

/*
* 用链表写出栈结构
* 栈结构具有的API：push, pop, size, sort(用来给链表根据数据重新排序), 
*/

/*
* 基本流程：
* 一、写出链表
*              1. Node结构体；
*              2. linkedList 作为 Node 结构体的指针；
* 二、写出栈
*              1.主要API函数的编写；还需要写一个生成栈的函数； 
*              2.测试         
*/ 


// 定义 Node 结构体 
typedef struct Node {
    int val;
    struct Node* next;
} Node;

// 定义linkedList 作为指向 Node 结构的指针 
typedef Node* linkedList;

// 测试 Node 结构以及 linkedList 是否成功定义的函数 
void testNode() {
    Node node = {1, NULL};
    // 输出结果 ： 1 
    printf("%d\n", node.val);
    linkedList pointer = &node;
    pointer->val = 2;
    // 输出结果 ： 2 
    printf("%d\n", node.val);
}


// 生成一个栈的函数，返回一个 Node 类型的指针 
linkedList gen_stack() {
    // 生成一个头部，作为栈的入口
    linkedList head = (linkedList) malloc(sizeof(Node));
    //  头部无 val ，next指向 NULL； 
    head->next = NULL; 
    return head; 
} 

// 测试 gen_stack 的函数
void test_gen_stack() {
    linkedList stack = gen_stack();
    stack->val = 1;
    // 输出 ： 1 
    printf("%d", stack->val);
} 


// 打印 queue 的函数
void print_stack(const linkedList stack) {
    // 从头部的下一个开始打印 val
    linkedList current = stack->next;
    while (current != NULL) {
        printf("%d -> ", current->val);
        // 指针指向下一个 
        current = current->next;
    }
    printf("%s", "NULL");
    printf("\n");   
} 


// 生成一个节点的函数
linkedList gen_Node(int val) {
    linkedList node = (linkedList) malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
} 

// API : push 放到栈首
void push(linkedList stack, int val) {
    // 生成一个节点
    linkedList node = gen_Node(val);
    // 栈首就是链接到头部的 next
    // 储存原来头部的 next 
    linkedList tmp = stack->next;
    // 将 node 连接
    stack->next = node;
    //  node 的 next 接 tmp
    node -> next = tmp;
}

// 测试 push 的函数
void test_push() {
    linkedList stack = gen_stack();
    push(stack, 1);
    push(stack, 2);
    push(stack, 3);
    // 打印 : 3 -> 2 -> 1 -> NULL 
    print_stack(stack);
} 


// API : pop 弹出栈首的 Node 的 val 
int pop(linkedList stack) {
    linkedList origin = stack->next;
    int val = origin->val;
    stack->next = stack->next->next;
    // 释放掉弹出的元素空间 
    free(origin);
    return val;
}

// 测试 pop 
void test_pop() {
    linkedList stack = gen_stack();
    push(stack, 1);
    push(stack, 2);
    push(stack, 3);
    int val = pop(stack);
    // 打印 ：2 -> 1 -> NULL
    print_stack(stack);
    // 打印 ：3 
    printf("%d\n", val);
}  


// API ：size 返回栈中元素的个数
int size(linkedList stack) {
    int ret = 0;
    linkedList current = stack->next;
    while (current != NULL) {
        ret++;
        current = current->next;
    }
    return ret;
} 

// 测试 size 函数
void test_size() {
    linkedList stack = gen_stack();
    push(stack, 1);
    push(stack, 2);
    push(stack, 3);
    // 输出 : 3 
    printf("%d\n", size(stack));
    pop(stack);
    // 输出 : 2 
    printf("%d\n", size(stack));
}
 

// API : sort 根据 val 从小到大排序 一般 stack 并不具备这个功能，写着玩的
void sort(linkedList stack) {
    // 采用冒泡排序
    int size_of_stack = size(stack);
    int i;
    for (i = size_of_stack - 1; i > 0; i--) {
        linkedList current = stack->next;
        while (current->next != NULL) {
            // 需要交换的情况 
            if (current->val > current->next->val) {
                int tmp = current->val;
                current->val = current->next->val;
                current->next->val = tmp;
            }
            current = current->next;
        }
    }
}  

// 测试 sort 的函数
void test_sort() {
    linkedList stack = gen_stack();
    push(stack, 1);
    push(stack, 2);
    push(stack, 3);
    push(stack, 4);
    sort(stack);
    // 打印 : 1 -> 2 -> 3 -> 4 -> NULL 
    print_stack(stack);  
}  

// 测试汇总 
void test() {
    // testNode(); 测试通过 
    // test_gen_stack(); 测试通过 
    // test_push(); 测试通过 
    // test_pop(); 测试通过 
    // test_size(); 测试通过 
    // test_sort(); 测试通过
}


// 主函数 
int main() {
    test();
    return 0;
}

代码需要注意的点

• 尽管该代码很简单，也应该尽量每写完一个函数就测试，确保每一个模块的正确性。
• 生成每一个节点都需要申请内存空间，栈弹出之后，一定记得将pop掉的节点的内存空间释放掉，否则会造成内存泄漏。
• 当你想在函数中改变某个参数的值时，就要将该参数的地址作为参数传入函数。

写代码遇到的问题

C语言没有对象，写出的“栈”无法像面向对象语言那样方便地使用。当然这很可能是我的见识不够的问题。

视频教程

视频教程