JavaScript - Queue and Stack

[編程] JavaScript 的列隊 (Queue) 和堆疊 (Stack)

在JavaScript中,我們也可以使用到列隊(Queue)和堆疊(Stack)這兩個數據結構。最簡單的方法是使用JS內置的陣列(Array)和內置的方法模仿列隊(Queue)和堆疊(Stack),達至先進先出(FIFO, First-In-First-Out)和後進先出(LIFO, Last In First Out)的原理。

內置push, pop, shift和unshift方法

JavaScript的陣列提供了4個方法,分別是push()、pop()、shift()和unshift()。我們先看看下面的圖片了解運用的方式。

如果我們假設左邊是頭(front),右邊是尾(rear)。如果要將新的元素加入數據結構之中,可以使用push()方法將元素加至數據結構的尾(rear),使用unshift()方法則可以加至數據結構的頭(front)。如果要刪除數據結構內的元素,可以使用pop()方法將元素由數據結構的尾(rear)刪除並返回,使用shift()方法將元素由數據結構的頭(front)刪除並返回。

JavaScript - Queue and Stack

很明顯,我們可以使用push()和shift()兩個方法做到先進先出(FIFO, First-In-First-Out)的原理。另外,unshift()和pop()兩個方法也可以做到先進先出(FIFO, First-In-First-Out)的原理;而push()和pop()兩個方法做到後進先出(LIFO, Last In First Out)的原理。shift()和unshift()兩個方法也可以做到後進先出(LIFO, Last In First Out)的原理。

使用push()和shift()兩個方法的列隊(Queue)例子

var fifoQueue = new Array();
// 建立新的Queue

fifoQueue.push("FoolEgg.com");
fifoQueue.push(123456789);
var ptr = fifoQueue.push(98.7654321);
// 將「FoolEgg.com」字串、「123456789」整數和「98.7654321」浮點數加入Queue

document.writeln("ptr is " + ptr + "<br />");
document.writeln("The length of queue is " + fifoQueue.length + " and the elements are [" + fifoQueue + "]<br />");

document.writeln("Delete the element [" + fifoQueue.shift() + "]<br />");
// 刪除並返回最頭的元素「FoolEgg.com」字串

document.writeln("The length of queue is " + fifoQueue.length + " and the elements are [" + fifoQueue + "]<br />");

document.writeln("Delete the element [" + fifoQueue.shift() + "]<br />");
// 刪除並返回最頭的元素「123456789」整數

document.writeln("The length of queue is " + fifoQueue.length + " and the elements are [" + fifoQueue + "]<br />");

document.writeln("Delete the element [" + fifoQueue.shift() + "]<br />");
// 刪除並返回最頭的元素「98.7654321」浮點數

document.writeln("Delete the element [" + fifoQueue.shift() + "]<br />");
// 刪除並返回最頭的元素

document.writeln("ptr is " + ptr + "<br />");
document.writeln("The length of queue is " + fifoQueue.length + " and the elements are [" + fifoQueue + "]<br />");

以下是輸出的結果︰

ptr is 3
The length of queue is 3 and the elements are [FoolEgg.com,123456789,98.7654321]
Delete the element [FoolEgg.com]
The length of queue is 2 and the elements are [123456789,98.7654321]
Delete the element [123456789]
The length of queue is 1 and the elements are [98.7654321]
Delete the element [98.7654321]
Delete the element [undefined]
ptr is 3
The length of queue is 0 and the elements are []

使用unshift()和pop()兩個方法的列隊(Queue)例子

var fifoQueue = new Array();
// 建立新的Queue

fifoQueue.unshift("FoolEgg.com");
fifoQueue.unshift(123456789);
var ptr = fifoQueue.unshift(98.7654321);
// 將「FoolEgg.com」字串、「123456789」整數和「98.7654321」浮點數加入Queue

document.writeln("ptr is " + ptr + "<br />");
document.writeln("The length of queue is " + fifoQueue.length + " and the elements are [" + fifoQueue + "]<br />");

document.writeln("Delete the element [" + fifoQueue.pop() + "]<br />");
// 刪除並返回最頭的元素「FoolEgg.com」字串

document.writeln("The length of queue is " + fifoQueue.length + " and the elements are [" + fifoQueue + "]<br />");

document.writeln("Delete the element [" + fifoQueue.pop() + "]<br />");
// 刪除並返回最頭的元素「123456789」整數

document.writeln("The length of queue is " + fifoQueue.length + " and the elements are [" + fifoQueue + "]<br />");

document.writeln("Delete the element [" + fifoQueue.pop() + "]<br />");
// 刪除並返回最頭的元素「98.7654321」浮點數

document.writeln("Delete the element [" + fifoQueue.pop() + "]<br />");
// 刪除並返回最頭的元素

document.writeln("ptr is " + ptr + "<br />");
document.writeln("The length of queue is " + fifoQueue.length + " and the elements are [" + fifoQueue + "]<br />");

以下是輸出的結果︰

ptr is 3
The length of queue is 3 and the elements are [98.7654321,123456789,FoolEgg.com]
Delete the element [FoolEgg.com]
The length of queue is 2 and the elements are [98.7654321,123456789]
Delete the element [123456789]
The length of queue is 1 and the elements are [98.7654321]
Delete the element [98.7654321]
Delete the element [undefined]
ptr is 3
The length of queue is 0 and the elements are []

使用push()和pop()兩個方法的堆疊(Stack)例子

var lifoStack = new Array();
// 建立新的Stack

lifoStack.push("FoolEgg.com");
lifoStack.push(123456789);
var ptr = lifoStack.push(98.7654321);
// 將「FoolEgg.com」字串、「123456789」整數和「98.7654321」浮點數加入Stack

document.writeln("ptr is " + ptr + "<br />");
document.writeln("The length of stack is " + lifoStack.length + " and the elements are [" + lifoStack + "]<br />");

document.writeln("Delete the element [" + lifoStack.pop() + "]<br />");
// 刪除並返回最頂的元素「98.7654321」浮點數

document.writeln("The length of stack is " + lifoStack.length + " and the elements are [" + lifoStack + "]<br />");

document.writeln("Delete the element [" + lifoStack.pop() + "]<br />");
// 刪除並返回最頂的元素「123456789」整數

document.writeln("The length of stack is " + lifoStack.length + " and the elements are [" + lifoStack + "]<br />");

document.writeln("Delete the element [" + lifoStack.pop() + "]<br />");
// 刪除並返回最頂的元素「FoolEgg.com」字串

document.writeln("Delete the element [" + lifoStack.pop() + "]<br />");
// 刪除並返回最頂的元素

document.writeln("ptr is " + ptr + "<br />");
document.writeln("The length of stack is " + lifoStack.length + " and the elements are [" + lifoStack + "]<br />");

以下是輸出的結果︰

ptr is 3
The length of stack is 3 and the elements are [FoolEgg.com,123456789,98.7654321]
Delete the element [98.7654321]
The length of stack is 2 and the elements are [FoolEgg.com,123456789]
Delete the element [123456789]
The length of stack is 1 and the elements are [FoolEgg.com]
Delete the element [FoolEgg.com]
Delete the element [undefined]
ptr is 3
The length of stack is 0 and the elements are []

使用shift()和unshift()兩個方法的堆疊(Stack)例子

var lifoStack = new Array();
// 建立新的Stack

lifoStack.unshift("FoolEgg.com");
lifoStack.unshift(123456789);
var ptr = lifoStack.unshift(98.7654321);
// 將「FoolEgg.com」字串、「123456789」整數和「98.7654321」浮點數加入Stack

document.writeln("ptr is " + ptr + "<br />");
document.writeln("The length of stack is " + lifoStack.length + " and the elements are [" + lifoStack + "]<br />");

document.writeln("Delete the element [" + lifoStack.shift() + "]<br />");
// 刪除並返回最頭的元素「98.7654321」浮點數

document.writeln("The length of stack is " + lifoStack.length + " and the elements are [" + lifoStack + "]<br />");

document.writeln("Delete the element [" + lifoStack.shift() + "]<br />");
// 刪除並返回最頭的元素「123456789」整數

document.writeln("The length of stack is " + lifoStack.length + " and the elements are [" + lifoStack + "]<br />");

document.writeln("Delete the element [" + lifoStack.shift() + "]<br />");
// 刪除並返回最頭的元素「FoolEgg.com」字串

document.writeln("Delete the element [" + lifoStack.shift() + "]<br />");
// 刪除並返回最頭的元素

document.writeln("ptr is " + ptr + "<br />");
document.writeln("The length of stack is " + lifoStack.length + " and the elements are [" + lifoStack + "]<br />");

以下是輸出的結果︰

ptr is 3
The length of stack is 3 and the elements are [98.7654321,123456789,FoolEgg.com]
Delete the element [98.7654321]
The length of stack is 2 and the elements are [123456789,FoolEgg.com]
Delete the element [123456789]
The length of stack is 1 and the elements are [FoolEgg.com]
Delete the element [FoolEgg.com]
Delete the element [undefined]
ptr is 3
The length of stack is 0 and the elements are []