JavaScript數(shù)據(jù)結(jié)構(gòu)02 - 棧

legendaryedu 發(fā)布于2019-08-23 10:22 / 1783人閱讀

摘要：它們就是棧和隊(duì)列。概念棧是一種遵循后進(jìn)先出原則的有序集合。新添加的或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。棧也被用在編程語(yǔ)言的編譯器和內(nèi)存中保存變量方法調(diào)用等，比如函數(shù)的調(diào)用棧。

一、定義 1.1 背景

通過(guò)前面一節(jié)《JavaScript數(shù)據(jù)結(jié)構(gòu)01 - 數(shù)組》我們知道，可以在數(shù)組的任意位置上刪除或添加元素。然而，有時(shí)候我們還需要一種在添加或刪除元素時(shí)有更多控制的數(shù)據(jù)結(jié)構(gòu)。

有兩種數(shù)據(jù)結(jié)構(gòu)類似于數(shù)組，但在添加和刪除元素時(shí)更為可控。

它們就是棧和隊(duì)列。

1.2 概念

棧是一種遵循后進(jìn)先出（LIFO）原則的有序集合。新添加的或待刪除的元素都保存在棧的末尾，稱作棧頂，另一端就叫棧底。

在棧里，新元素都靠近棧頂，舊元素都接近棧底。

棧也被用在編程語(yǔ)言的編譯器和內(nèi)存中保存變量、方法調(diào)用等，比如函數(shù)的調(diào)用棧。

二、棧的實(shí)現(xiàn) 2.1 創(chuàng)建一個(gè)類來(lái)表示棧

這里我還是用構(gòu)造函數(shù)的形式來(lái)書寫，大家有興趣可以用ES6的Class來(lái)重寫一遍。

// Stack類
function Stack () {
  this.items = [];

  this.push = push;
  this.pop = pop;
  this.peek = peek;
  this.isEmpty = isEmpty;
  this.clear = clear;
  this.size = size;
  this.print = print;
}

棧里面有一些聲明的方法：

push(element)：添加一個(gè)（或幾個(gè)）新元素到棧頂

pop()：移除棧頂?shù)脑兀瑫r(shí)返回被移除的元素

peek()：返回棧頂?shù)脑兀粚?duì)棧做任何修改

isEmpty()：如果棧里沒(méi)有任何元素就返回true，否則返回false

clear()：移除棧里的所有元素

size()：返回棧里的元素個(gè)數(shù)

2.2 實(shí)現(xiàn)棧中的輔助方法

// 添加新元素到棧頂
function push (element) {
  this.items.push(element);
}

// 移除棧頂元素，同時(shí)返回被移除的元素
function pop () {
  return this.items.pop();
}

// 查看棧頂元素
function peek () {
  return this.items[this.items.length - 1];
}

// 判斷是否為空棧
function isEmpty () {
  return this.items.length === 0;
}

// 清空棧
function clear () {
  this.items = [];
}

// 查詢棧的長(zhǎng)度
function size () {
  return this.items.length;
}

// 打印棧里的元素
function print () {
  console.log(this.items.toString());
}

2.3 創(chuàng)建實(shí)例進(jìn)行測(cè)試

// 創(chuàng)建Stack實(shí)例
var stack = new Stack();

console.log(stack.isEmpty());     // true
stack.push(5);                    // undefined
stack.push(8);                    // undefined
console.log(stack.peek());        // 8
stack.push(11);                   // undefined
console.log(stack.size());        // 3
console.log(stack.isEmpty());     // false
stack.push(15);                   // undefined
stack.pop();                      // 15
console.log(stack.size());        // 3
stack.print();                    // 5,8,11
stack.clear();                    // undefined
console.log(stack.size());        // 0

三、結(jié)束

本文會(huì)同步到我的個(gè)人博客，完整代碼可以到我的github倉(cāng)庫(kù)查看，如果對(duì)你有幫助的話歡迎點(diǎn)一個(gè)Star~~

歡迎關(guān)注我的公眾號(hào)