『資料結構』堆疊 Stack

前言

準備好歡迎我們第二週的主題“堆疊”了嗎！
在電腦科學的江湖上流傳著一句話：

程式設計＝資料結構＋演算法

在各大專院校裡，這幾門課都列為必修課之一，但是大多缺乏語言的基礎，反而在這裡頭迷失了，學完就好像睡了一覺，模模糊糊迷迷茫茫…，我就是這樣😂

本篇將使用 JavaScript 來學習堆疊(Stack)的資料結構。

堆疊是什麼？

堆疊是一種按照後進先出 (LIFO, Last In First Out)的有序結構，舉個例子：日常生活中的疊盤子。先疊的盤子會在最下面，後面開始會疊在上方，一層一層往上，當要拿盤子時一定是從最上面拿。

建立堆疊

開始進入實作的階段，GOGO🤟🏻

類別

首先，建立一個類別為 Stack:

1
2
3

function Stack(){
  //宣告內部屬性和方法
}

屬性

我們下面會用 Array 的方式進行，所以宣告起來。

1	let items = [];

方法

新增 push(element)、刪除 pop()

// 新增元素
this.push = function(element){
  items.push(element);
}

// 刪除元素：會返回被移除的元素
this.pop = function(){
  return items.pop();
}

最上方元素為何 peek(), top()

// 返回最上方元素
this.peek = function(){
  return items[items.length - 1];
}

堆疊還有元素嗎 isEmpty()

// 堆疊內部是否還有元素存在 true, false
this.isEmpty = function(){
  return items.length === 0;
}

元素共有幾個 size()

// 堆疊內部有多少元素
this.size = function(){
  return items.length;
}

清空堆疊 clear()

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

完整程式碼

function Stack() {
  let items = [];

  this.push = function(element){
    items.push(element);
  }

  this.pop = function(){
    return items.pop();
  }

  this.peek = function(){
    return items[items.length - 1];
  }

  this.isEmpty = function(){
    return items.length === 0;
  }

  this.size = function(){
    return items.length;
  }

  this.clear = function(){
    return items = [];
  }
}

動手做做看

快速測試可以打開 chrome 的 console 操作看看。

var stack = new Stack();

stack.push('plateA');
stack.push('plateB');
stack.push('plateC');
console.log(stack); // ['plateA', 'plateB', 'plateC']

stack.pop()
console.log(stack); // ['plateA', 'plateB']

stack.size() // 2
stack.peek() // 'plantB'
stack.clear() // []
stack.isEmpty() // true

最後到 leetcode 驗收一下自己學習的成果吧！
232. Implement Queue using Stacks
20. Valid Parentheses

延伸閱讀

What is a Stack?
前端工程師用 javaScript 學演算法
堆疊- 維基百科，自由的百科全書 - Wikipedia