JavaScript中棧和佇列的演算法解析

這篇文章帶給大家的內容是關於JavaScript中棧和佇列的演算法解析，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

一、認識資料結構

什麼是資料結構？以下是維基百科的解釋

資料結構是電腦儲存、組織資料的方式

資料結構意味著接口或封裝：一個資料結構可被視為兩個函數之間的接口，或是由資料類型聯合組成的儲存內容的存取方法封裝

我們每天的編碼中都會用到資料結構，因為陣列是最簡單的記憶體資料結構，以下是常見的資料結構

• 陣列（Array）

• #堆疊（Stack）

• #佇列（Queue）

• 鍊錶（Linked List）

• 樹（Tree）

• 圖（Graph）

• 堆（Heap）

• 散列表（Hash）

下面來學習學習堆疊和佇列..

二、堆疊

2.1 堆疊資料結構

#堆疊是一種遵循後進先出（LIFO）原則的有序集合。新加入的或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧裡，新元素都接近棧頂，舊元素都接近棧底。

類比生活中的物件：一疊書或推放在一起的盤子

2.2 堆疊的實作

普通的堆疊常用的有以下幾個方法：

push 增加一個（或幾個）新元素到堆疊頂部

pop 溢出棧頂元素，同時傳回移除的元素

peek 回傳棧頂元素，不對棧做修改

isEmpty 棧內無元素回傳true，否則回傳false

size 回傳棧內元素數

clear 清空堆疊

class Stack {
  constructor() {
    this._items = []; // 储存数据
  }
  // 向栈内压入一个元素
  push(item) {
    this._items.push(item);
  }
  // 把栈顶元素弹出
  pop() {
    return this._items.pop();
  }
  // 返回栈顶元素
  peek() {
    return this._items[this._items.length - 1];
  }
  // 判断栈是否为空
  isEmpty() {
    return !this._items.length;
  }
  // 栈元素个数
  size() {
    return this._items.length;
  }
  // 清空栈
  clear() {
    this._items = [];
  }
}

現在再回頭想想資料結構裡面的堆疊是什麼。

突然發現並沒有那麼神奇，僅僅只是對原有資料進行了一次封裝而已。而封裝的結果是：並不關心其內部的元素是什麼，只是去操作棧頂元素，這樣的話，在編碼中會更可控一些。

2.3 堆疊的應用

（1）十進制轉任意進位

要求: 給定一個函數，輸入目標數值和進制基數，輸出對應的進制數（最大為16進制）

baseConverter(10, 2) ==> 1010
baseConverter(30, 16) ==> 1E

分析: 進制轉換的本質：將目標值一次一次除以進制基數，得到的整值為新目標值，記錄下餘數，直到目標值小於0，最後將餘數逆序組合即可。利用棧，記錄餘數入棧，組合時出棧

// 进制转换
function baseConverter(delNumber, base) {
  const stack = new Stack();
  let rem = null;
  let ret = [];
  // 十六进制中需要依次对应A~F
  const digits = '0123456789ABCDEF';

  while (delNumber > 0) {
    rem = Math.floor(delNumber % base);
    stack.push(rem);
    delNumber = Math.floor(delNumber / base);
  }

  while (!stack.isEmpty()) {
    ret.push(digits[stack.pop()]);
  }

  return ret.join('');
}

console.log(baseConverter(100345, 2)); //输出11000011111111001
console.log(baseConverter(100345, 8)); //输出303771
console.log(baseConverter(100345, 16)); //输出187F9

（2）逆波蘭表達式計算

要求: 逆波蘭表達式，也叫後綴表達式，它將複雜表達式轉換為可以依靠簡單的運算得到計算結果的表達式，例如(a b)*(c d)轉換為a b c d *

["4", "13", "5", "/", "+"] ==> (4 + (13 / 5)) = 6
["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
==> ((10 * (6 / ((9 + 3) * -11))) + 17) + 5

分析: 以符號為觸發節點，一旦遇到符號，就將符號前兩個元素依照該符號運算，並將新的結果入棧，直到堆疊內僅一個元素

function isOperator(str) {
  return ['+', '-', '*', '/'].includes(str);
}
// 逆波兰表达式计算
function clacExp(exp) {
  const stack = new Stack();
  for (let i = 0; i <p><strong>（3）利用普通堆疊實作一個有<code>min</code>方法的堆疊</strong></p><p>##想法:<strong> 使用兩個堆疊來儲存數據，其中一個命名為</strong>dataStack<code>，專門用來儲存數據，另一個命名為</code>minStack<code>，專門用來儲存堆疊裡最小的資料。總是保持兩個堆疊中的元素個數相同，壓棧時判別壓入的元素與</code>minStack<code>棧頂元素比較大小，如果比棧頂元素小，則直接入棧，否則複製棧頂元素入棧；彈出棧頂時，兩者皆彈出即可。這樣</code>minStack<code>的棧頂元素總是最小值。 </code></p><pre class="brush:php;toolbar:false">class MinStack {
  constructor() {
    this._dataStack = new Stack();
    this._minStack = new Stack();
  }

  push(item) {
    this._dataStack.push(item);
    // 为空或入栈元素小于栈顶元素，直接压入该元素
    if (this._minStack.isEmpty() || this._minStack.peek() > item) {
      this._minStack.push(item);
    } else {
      this._minStack.push(this._minStack.peek());
    }
  }

  pop() {
    this._dataStack.pop();
    return this._minStack.pop();
  }

  min() {
    return this._minStack.peek();
  }
}

const minstack = new MinStack();

minstack.push(3);
minstack.push(4);
minstack.push(8);
console.log(minstack.min()); // 3
minstack.push(2);
console.log(minstack.min()); // 2

三、佇列

3.1 佇列資料結構佇列是遵循先進先出（FIFO，也稱為先來先服務）原則的一組有序的項。佇列在尾部新增元素，並從頂部移除元素。最新加入的元素必須排在佇列的末端

類比：日常生活中的購物排隊

3.2 佇列的實作

普通的佇列常用的有以下幾個方法：

• enqueue 將一個(或多個)新增一個(或多個)新的項

• dequeue 移除佇列的第一個(即排在佇列最前面的)項，並傳回被移除的元素

  ###### ###head### 傳回佇列第一個元素，佇列不做任何變更###############tail### 傳回佇列最後一個元素，佇列不做任何變更# ##

• isEmpty 队列内无元素返回true，否则返回false

• size 返回队列内元素个数

• clear 清空队列

class Queue {
  constructor() {
    this._items = [];
  }

  enqueue(item) {
    this._items.push(item);
  }

  dequeue() {
    return this._items.shift();
  }

  head() {
    return this._items[0];
  }

  tail() {
    return this._items[this._items.length - 1];
  }

  isEmpty() {
    return !this._items.length;
  }

  size() {
    return this._items.length;
  }

  clear() {
    this._items = [];
  }
}

与栈类比，栈仅能操作其头部，队列则首尾均能操作，但仅能在头部出尾部进。当然，也印证了上面的话：栈和队列并不关心其内部元素细节，也无法直接操作非首尾元素。

3.3 队列的应用

（1）约瑟夫环（普通模式）

要求: 有一个数组a[100]存放0~99；要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数。

分析: 按数组创建队列，依次判断元素是否满足为指定位置的数，如果不是则enqueue到尾部，否则忽略，当仅有一个元素时便输出

// 创建一个长度为100的数组
const arr_100 = Array.from({ length: 100 }, (_, i) => i*i);

function delRing(list) {
  const queue = new Queue();
  list.forEach(e => { queue.enqueue(e); });
  
  let index = 0;
  while (queue.size() !== 1) {
    const item = queue.dequeue();
    index += 1;
    if (index % 3 !== 0) {
      queue.enqueue(item);
    }
  }

  return queue.tail();
}

console.log(delRing(arr_100)); // 8100 此时index=297

（2）菲波那切数列（普通模式）

要求: 使用队列计算斐波那契数列的第n项
分析: 斐波那契数列的前两项固定为1，后面的项为前两项之和，依次向后，这便是斐波那契数列。

function fibonacci(n) {
    const queue = new Queue();
    queue.enqueue(1);
    queue.enqueue(1);
    
    let index = 0;
    while(index <p><strong>（3）用队列实现一个栈</strong></p><p><strong>要求:</strong> 用两个队列实现一个栈<br><strong>分析:</strong> 使用队列实现栈最主要的是在队列中找到栈顶元素并对其操作。具体的思路如下：</p><ol class=" list-paddingleft-2">
<li><p>两个队列，一个备份队列<code>emptyQueue</code>，一个是数据队列<code>dataQueue</code>；</p></li>
<li><p>在确认栈顶时，依次<code>dequeue</code>至备份队列，置换备份队列和数据队列的引用即可</p></li>
</ol><pre class="brush:php;toolbar:false">class QueueStack {
  constructor() {
    this.queue_1 = new Queue();
    this.queue_2 = new Queue();
    this._dataQueue = null; // 放数据的队列
    this._emptyQueue = null; // 空队列,备份使用
  }

  // 确认哪个队列放数据,哪个队列做备份空队列
  _initQueue() {
    if (this.queue_1.isEmpty() && this.queue_2.isEmpty()) {
      this._dataQueue = this.queue_1;
      this._emptyQueue = this.queue_2;
    } else if (this.queue_1.isEmpty()) {
      this._dataQueue = this.queue_2;
      this._emptyQueue = this.queue_1;
    } else {
      this._dataQueue = this.queue_1;
      this._emptyQueue = this.queue_2;
    }
  };

  push(item) {
    this.init_queue();
    this._dataQueue.enqueue(item);
  };

  peek() {
    this.init_queue();
    return this._dataQueue.tail();
  }

  pop() {
    this.init_queue();
    while (this._dataQueue.size() > 1) {
      this._emptyQueue.enqueue(this._dataQueue.dequeue());
    }
    return this._dataQueue.dequeue();
  };
};

学习了栈和队列这类简单的数据结构，我们会发现。数据结构并没有之前想象中那么神秘，它们只是规定了这类数据结构的操作方式：栈只能对栈顶进行操作，队列只能在尾部添加在头部弹出；且它们不关心内部的元素状态。

以上是JavaScript中棧和佇列的演算法解析的詳細內容。更多資訊請關注PHP中文網其他相關文章！