[個人心得]數據結構之棧，隊列。

curried 發布于2019-08-21 17:55 / 1579人閱讀

摘要：另外棧也可以用一維數組或連結串列的形式來完成。壓棧就是，出棧就是。出棧成功第個節點是這是單鏈表形式的棧的源碼地址。隊列只允許在后端稱為進行插入操作，在前端稱為進行刪除操作。

維基百科

堆棧（英語：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就行了。鏈表式可以看看前幾遍文章。這里就附上隊列的源碼

GPU云服務器云服務器數據倉庫心得大數據培訓心得數據分析心得統計數據分析心得

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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