JS中數據結構之隊列

隊列是一種列表，不同的是隊列只能在隊尾插入元素，在隊首刪除元素。隊列用于存儲按順序排列的數據，先進先出。

隊列的兩種主要操作是：向隊列中插入新元素和刪除隊列中的元素。插入操作也叫做入隊，刪除操作也叫做出隊。入隊操作在隊尾插入新元素，出隊操作刪除隊頭的元素。

用數組實現的隊列

function Queue() {
　　this.dataStore = [];
　　this.enqueue = enqueue;
　　this.dequeue = dequeue;
　　this.front = front;
　　this.back = back;
　　this.toString = toString;
　　this.empty = empty;
}

enqueue() 方法向隊尾添加一個元素：

function enqueue(element) { 
　　this.dataStore.push(element); 
}

dequeue() 方法刪除隊首的元素：

function dequeue() { 
　　return this.dataStore.shift(); 
}

front()，back() 方法讀取隊首和隊尾的元素：

function front() {
　　return this.dataStore[0];
}
function back() {
　　return this.dataStore[this.dataStore.length-1];
}

toString() 方法顯示隊列內的所有元素：

function toString() {
　　var retStr = "";
　　for (var i = 0; i < this.dataStore.length; ++i) {
　　　　retStr += this.dataStore[i] + "\n";
　　}
　　return retStr;
}

empty() 方法判斷隊列是否為空：

function empty() {
　　if (this.dataStore.length == 0) {
　　　　return true;
　　}
　　else {
　　　　return false;
　　}
}

優先隊列

在一般情況下，從隊列中刪除的元素，一定是率先入隊的元素。從優先隊列中刪除元素時，需要考慮優先權的限制，在刪除元素時不必遵守先進先出的約定。高優先級的元素優先處理。

重新定義 dequeue() 方法，使其刪除隊列中擁有最高優先級的元素。我們規定：優先碼的值最小的元素優先級最高。

function dequeue() {
  var priority = this.dataStore[0].code;
  var num = 0;
  for (var i = 1; i < this.dataStore.length; ++i) {
    if (this.dataStore[i].code < priority) {
      priority = this.dataStore[i].code;
      num = i;
    }
  }
  return this.dataStore.splice(num, 1);
}

posted @ 2019-01-16 12:39 wenxuehai 閱讀(570) 評論(0) 收藏舉報

刷新頁面返回頂部

//右下角添加目錄

提升自己，才有選擇的能力和勇氣

JS中數據結構之隊列

公告