线性数据结构--栈（stack）

栈是一种线性数据结构，栈的特征是数据的插入和删除只能通过一端来实现，这一端称为“栈顶”，相应的另一端称为“栈底”。说到线性结构，得先了解一下数据的逻辑结构，数据的逻辑结构分为线性结构、集合结构、树形结构和图形结构，如下图所示，栈是一种特殊的线性表，是线性结构的一种。

数据的逻辑结构

栈（stack）的特点

栈(Stack)是一种线性存储结构，它具有如下特点：

栈中的数据元素遵守“先进后出"(First In Last Out)的原则，简称FILO结构。（后进先出的叫法，也是可以的）；限定只能在栈顶进行插入和删除操作。栈（stack）的相关概念栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。压栈(push)：栈的插入操作，叫做进栈，也称压栈、入栈。弹栈(pop)：栈的删除操作，也叫做出栈。栈（stack）的两种实现方法基于数组的栈 —— 以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向基于单链表的栈 —— 以链表为底层的数据结构时，以链表头为栈顶，便于节点的插入与删除，压栈产生的新节点将一直出现在链表的头部。

基于数组的栈

压栈操作：

int StackPush(struct Stack* stack, int data){    if(stack->size >= LENGHT)    {        printf("stack is full\n");        return (-1);    }    stack->stack_array[stack->size] = data;    stack->size++;    printf("push:%d size:%d\n",data,stack->size);    return 0;}

基于数组的栈图示

出栈操作：

int StackPop(struct Stack* stack, int* data){    stack->size--;    if(IsStackEmpty(stack))        return -1;    *data = stack->stack_array[stack->size];    printf("pop:%d size:%d\n",*data, stack->size);    return 0;}

压栈操作：

int StackPush(struct Stack* stack, int data){    struct List* temp = (struct List*)malloc(sizeof(struct List));    temp->data = data;    temp->next = stack->head->next;    stack->head->next = temp;    stack->size++;    printf("push:%d \n",data);    return 0;}

基于单链表的栈图示

基于单链表的栈简易图示

出栈操作：

int StackPop(struct Stack* stack, int* data){    struct List* temp = NULL;    if(IsStackEmpty(stack))        return -1;        temp = stack->head->next;    *data = temp->data;    stack->head->next = temp->next;    stack->size--;    free(temp);    printf("pop:%d\n",*data);    return 0;}

完整代码：

基于单链表实现栈：

#include<stdio.h>#include<stdlib.h>#include<string.h>struct List{    int data;    struct List* next;};struct Stack{    struct List* head;    int size;};struct Stack* StackInit(void){    struct Stack* stack = NULL;    stack = (struct Stack*)malloc(sizeof(struct Stack));    stack->head = (struct List*)malloc(sizeof(struct List));    stack->head->next = NULL;    stack->size = 0;    return stack;}int StackPush(struct Stack* stack, int data){    struct List* temp = (struct List*)malloc(sizeof(struct List));    temp->data = data;    temp->next = stack->head->next;    stack->head->next = temp;    stack->size++;    printf("push:%d \n",data);    return 0;}int IsStackEmpty(struct Stack* stack){    if(stack->head->next == NULL)    {        return 1;    }    else    {        return 0;    }  }int StackPop(struct Stack* stack, int* data){    struct List* temp = NULL;    if(IsStackEmpty(stack))        return -1;        temp = stack->head->next;    *data = temp->data;    stack->head->next = temp->next;    stack->size--;    free(temp);    printf("pop:%d\n",*data);    return 0;}int main(){    int i = 0;    struct Stack* stack = NULL;    stack = StackInit();    for ( i = 0; i < 5; i++)    {        StackPush(stack, i);    }    for ( i = 0; i < 5; i++)    {       int data = 0;       StackPop(stack, &data);       printf("%d \n",data);    }    return 0;}

基于数组实现栈：

#include<stdio.h>#include<stdlib.h>#define LENGHT (100)struct Stack{    int stack_array[LENGHT];    int size;};struct Stack* StackInit(void){    struct Stack* stack = NULL;    stack = (struct Stack*)malloc(sizeof(struct Stack));    stack->size = 0;    return stack;}int StackPush(struct Stack* stack, int data){    if(stack->size >= LENGHT)    {        printf("stack is full\n");        return (-1);    }    stack->stack_array[stack->size] = data;    stack->size++;    printf("push:%d size:%d\n",data,stack->size);    return 0;}int IsStackEmpty(struct Stack* stack){    if(stack->size < 0)    {        return 1;    }    else    {        return 0;    }  }int StackPop(struct Stack* stack, int* data){    stack->size--;    if(IsStackEmpty(stack))        return -1;    *data = stack->stack_array[stack->size];    printf("pop:%d size:%d\n",*data, stack->size);    return 0;}int main(){    int i = 0;    struct Stack* stack = NULL;    stack = StackInit();    for ( i = 0; i < 5; i++)    {        StackPush(stack, i);    }    for ( i = 0; i < 6; i++)    {       int data = 0;       StackPop(stack, &data);       printf("%d \n",data);    }    printf("\n");    return 0;}

LeetCode系列：

leetcode2. 两数相加-c语言-python3

LeetCode5.0-最长回文子串-中心扩展法-C语言

LeetCode5.2-动态规划求解最长回文子串

LeetCode4. 寻找两个正序数组的中位数

LeetCode5.1-马拉车算法求解最长回文子串

LeetCode7.翻转整数-C语言与python的异同点

确定有限状态机(DFA)-Leet

字符串转换成一个 32 位有符号整数-atoi 函数Leet

python系列：

使用python实现已有c代码

c语言转学Python3——8条实用经验

leetcode2. 两数相加-c语言-python3

如何在VS Code中编写、编译、调试Python代码

Python源码阅读9-负整数和小整数对象池

CPython源码阅读6-对象的创建过程

CPython源码阅读10-整数运算

Cpython源码阅读11-你真的了解bytes和str吗

CPython源码阅读13-bytes对象合并底层原理

CPython源码阅读12-bytes对象和类型对象

Cpython源码阅读17-list自动扩容原理

CPython_PyObject_HEAD_EXTRA的作用

LeetCode7.翻转整数-C语言与python的异同点

Cpython源码阅读文章目录汇总

Cpython源码阅读18-从底层实现看列表与元组的区别

CPython源码阅读5-垃圾回收机制

CPython源码阅读3-基类与元类型-变长与定长对象

CPython源码阅读2-对象头如何初始化

CPython源码阅读8-变长对象的柔性数组

CPython源码阅读7-对象的销毁-空闲对象缓冲池

CPython源码阅读4-实例对象与类型对象的联系

Cpython源码阅读14-bytes对象合并要使用join

CPython源码阅读15-字符串对象为何unicode命名

Cpython源码阅读16-Unicode字符串底层存储结构

二叉树系列：

判断二叉树是否为平衡二叉树

平衡二叉树 构建平衡二叉树

如何优雅地画好二叉树

二叉树遍历的思维导图

二叉树的层序遍历及应用

平衡二叉树的结点删除操作

不平衡二叉树的旋转（LL、RR、LR、RL）

二叉查找树（BST：Binary Search Tree）