[个人心得]数据结构之栈，队列。

curried 发布于2019-08-21 17:55 / 1487人阅读

摘要：另外栈也可以用一维数组或连结串列的形式来完成。压栈就是，出栈就是。出栈成功第个节点是这是单链表形式的栈的源码地址。队列只允许在后端称为进行插入操作，在前端称为进行删除操作。

维基百科

堆栈（英语：stack）又称为栈，是计算机科学中一种特殊的串列形式的抽象资料型别，其特殊之处在于只能允许在链接串列或阵列的一端（称为堆叠顶端指标，英语：top）进行加入数据（英语：push）和输出数据（英语：pop）的运算。另外栈也可以用一维数组或连结串列的形式来完成。

特点：先入后出，后入先出。除头尾节点之外，每个元素有一个前驱，一个后继。

从上面可知，有两种形式，数组形式和链表的形式。

如果是数组（Array）的形式，那就很简单啦。压栈就是push，出栈就是pop。

链表形式的，每个元素都有一个指向前的指针和一个指向后的指针......等等，那这不就是双向链表吗（双向链表），那栈顶就是链表的尾，栈底就是链表的头（head）咯。

下面是我以单链表形式写的栈。（这是我写的单链表文章）

class Node {
  constructor (element) {
    this.element = element;
    this.next = null;
  }
}

class LinkedStack {
  constructor () {
    this.top = null;                   // 栈顶指针
    this.bottom = null;                // 栈底指针
    this.length = 0;
  }

  push (element) {
    let node = new Node(element);

    if (!this.top) {                  // 栈顶为空
      this.top = this.bottom = node;  // 栈顶为node
    } else {
      let front = this.top;
      this.top = front.next = node;   // 前一个的next 和 栈顶 都指向 node
    }
    this.length++;
    console.log("压栈成功啦！");
  }

  pop () {
    let node = this.bottom, front;
    if (!node) {                      // 栈底为空？ 那就是空栈咯。
      console.log("null stack");
    } else {
      while (node.next) {             // 当node.next为null，退出循环
        front = node;                 // 当node.next不为null，那么front指向这个node
        node = front.next;            // node 重新指向 front的下一个
      }
      this.top = front;               //node的next为null时，说明node为栈顶了，那么栈顶要指向前一个front
      front.next = null;              // front.next就为null了，不能指向node了，因为node出栈咯。
    }
    this.length--;
    console.log("出栈成功！");
  }

  print () {
    let arr = [this.bottom];
    let node = this.bottom;
    while (node.next) {
      node = node.next;
      arr.push(node);
    }
    arr.map( (x, index) => {
      console.log(`第${index + 1}个节点是:`);
      console.log(x);
    });
  }
}

这是单链表形式的栈的源码地址。

维基百科

队列，又称为伫列（queue），是先进先出（FIFO, First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。

有上面可知：

队列也有链表式和数组形式。

队列的特点是，从队尾入队，在队头出队，即先进先出。

数组形式就要数组（Array）的api就行了。链表式可以看看前几遍文章。这里就附上队列的源码

服务器托管云服务器数据仓库心得大数据培训心得数据分析心得统计数据分析心得

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/90220.html

源码|jdk源码之栈、队列及ArrayDeque分析

摘要：栈队列双端队列都是非常经典的数据结构。结合了栈和队列的特点。因此，在中，有栈的使用需求时，使用代替。迭代器之前源码源码之与字段中分析过，容器的实现中，所有修改过容器结构的操作都需要修改字段。栈、队列、双端队列都是非常经典的数据结构。和链表、数组不同，这三种数据结构的抽象层次更高。它只描述了数据结构有哪些行为，而并不关心数据结构内部用何种思路、方式去组织。本篇博文重点关注这三种数据结构...

ZHAO_ 2019-08-19 11:08 评论0 收藏0
学习数据结构与算法之栈与队列

摘要：于是翻出了机房里的这本学习数据结构与算法开始学习程序员的基础知识。这本书用了我最熟悉的来实现各种数据结构和算法，而且书很薄，可以说是一本不错的入门教程。队列在头部删除元素，尾部添加元素。本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算...

pingan8787 2019-08-20 18:37 评论0 收藏0
Javascript数组系列一之栈与队列

摘要：所谓数组英语，是有序的元素序列。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。在栈中添加数据和删除数据也被称为推入和弹出，而且推入和弹出只会发生在栈的顶部。栈是一种数据结构，而队列则是一种的数据结构，即先进先出。所谓数组（英语：Array），是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称...

sunsmell 2019-08-23 11:49 评论0 收藏0
实战PHP数据结构基础之栈

摘要：栈和队列栈和队列和之前讲到的实战数据结构基础之双链表一样都是线性结构。来看基于数组的栈实现得益于强大的结构，我们轻而易举的写出来了栈的基本操作方法。专题系列基础数据结构专题系列目录地址主要使用语法总结基础的数据结构和算法。栈和队列栈和队列和之前讲到的实战PHP数据结构基础之双链表一样都是线性结构。栈有什么特点栈遵循后进先出的原则(LIFO)。这意味着栈只有一个出口用来压入元素...

banana_pi 2019-07-01 10:08 评论0 收藏0
Python - 收藏集 - 掘金

摘要：首发于我的博客线程池进程池网络编程之同步异步阻塞非阻塞后端掘金本文为作者原创，转载请先与作者联系。在了解的数据结构时，容器可迭代对象迭代器使用进行并发编程篇二掘金我们今天继续深入学习。 Python 算法实战系列之栈 - 后端 - 掘金原文出处：安生栈(stack)又称之为堆栈是一个特殊的有序表，其插入和删除操作都在栈顶进行操作，并且按照先进后出，后进先出的规则进行运作。如...

546669204 2019-07-31 10:57 评论0 收藏0