数据结构之栈-白红宇

数据结构之栈

阅读量：3900 次

发布时间：2019-05-23

本文共 1613 字，大约阅读时间需要 5 分钟。

什么是栈

栈是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。一句话描述栈的特性就是先进后出

如何实现栈

实现一个栈我们一般有两种方法：

顺序结构

顾名思义，就是使用数组来实现栈的特性。数组实现简单，我们只需要预先定义好数组的大小、在数组的末尾进行元素的入栈操作或者出栈操作即可。时间复杂度为 O(1)。但是我们栈的大小有限，动态调整栈大小的代价较高，且要求有连续的地址空间。

链式结构

我们可以使用链表来实现。我们在进行出栈操作和入栈操作的时间复杂度都是 O(1)。同时可以动态的管理栈的大小。

栈的实现

元素节点定义（这是展示的是链表实现的方式）：

#include 
   
    #include 
    
     // 栈节点元素typedef struct Node{    /* data */    int val;    struct Node *next;    struct Node *prev;} Node;// 头节点元素Node *head = NULL;// 记录栈元素的数量int size = 0;

栈的初始化操作

void init(){    head = NULL;    size = 0;}

入栈操作

void push(int val){    Node *node = (Node *)malloc(sizeof(Node));    node->val = val;    node->prev = node->next = NULL;    if (head == NULL)    {        head = node;    }    else    {        head->next = node;        node->prev = head;        head = node;    }    size++;}

出栈操作

int pop(){    if (head == NULL)    {        return 0xFFFFFF;    }    Node *old = head;    head = head->prev;    if (head != NULL)    {        head->next = NULL;    }    old->prev = NULL;    int val = old->val;    size--;    free(old);    return val;}

获取栈容量

int stackSize(){    return size;}

启动函数

int main(){    init();    push(1);    push(2);    printf("%d\n", pop());    printf("%d\n", pop());    printf("%d", stackSize());    return 0;}/*210*/

栈的应用

栈在计算机中十分常见。比如我们写代码的递归就会使用到栈。浏览器页面的前进后退都会使用到栈。可见栈的的重要性还是比较高的，需要我们好好掌握。后续有时间会结合栈和算法写一篇文章，欢迎阅读。

数据结构中相关的代码我已上传到 gitlab:

此后的数据结构代码我都会上传在这个仓库中，需要的同学可以自己下载

以上就是本期的全部内容。在这里给大家拜个早年，祝大家新的一年牛气冲天！

感谢你能看到这里，欢迎关注我的微信公众号：BitLegend，学习更多的知识！我们下期再见！

转载地址：http://etden.baihongyu.com/

你可能感兴趣的文章