JavaScript中棧和佇列的演算法解析
- 不言轉載
- 2019-01-16 09:36:363088瀏覽
這篇文章帶給大家的內容是關於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，也稱為先來先服務）原則的一組有序的項。佇列在尾部新增元素，並從頂部移除元素。最新加入的元素必須排在佇列的末端
enqueue
將一個(或多個)新增一個(或多個)新的項-
dequeue
###### ###head### 傳回佇列第一個元素，佇列不做任何變更###############tail### 傳回佇列最後一個元素，佇列不做任何變更# ##移除佇列的第一個(即排在佇列最前面的)項，並傳回被移除的元素 isEmpty队列内无元素返回true，否则返回falsesize返回队列内元素个数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中文網其他相關文章！