[筆記] Master The Coding Interview – 10 @地瓜大的飛翔旅程

章節連結

課程相關資訊
內容
範例程式碼
相關文章

這篇是 Udemy 上的知名課程 – Master the Coding Interview 的部分進修心得。這篇對應的內容是「Data Structures: Stacks + Queues」關於堆疊和序列的第一部分簡介。

課程對應章節：107~112

請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。

內容

1. Stacks：LIFO，最後進的，可以最先被取出。
查詢 lookup – O(n)；取出最上面的項目 pop – O(1)；把項目放到最上面 push – O(1)；觀看最上面的值 – peek – O(1)
在 JavaScript 中，可以用 Array 或是 Linked List 實作
2. Queues：FIFO，先進的，可以最先執行，跟 Stacks 剛好相反
查詢 lookup – O(n)；取出最一開始的項目 dequeue – O(1)；把項目放到最後面 enqueue – O(1)；觀看最後一個的值 – peek – O(1)
在 JavaScript 中，建議使用 Linked List 實作。Array 實作固然可，但 Array 的若有新增或是刪除，其 index 是需要重新調整的。Linked List 因為本身的前後關係是有聯繫的，只要將對應的值刪除就行。

範例程式碼

// stacks
function Stack(){
    var items = []
        this.push = function(element){
            return items.push(element)
        }
        this.pop = function(){
            return items.pop()
        }
        this.peek = function(){
             return items[items.length-1]
        }
        this.size = function(){
            return items.length
        }
        this.clear = function(){
             return items = []
        }
}

// queues
// 以 Array 的實作，要注意 index 問題
function Queue(){
        var items=[];
        this.enqueue = element =>{
               return items.push(element)
         }

         this.dequeue = () =>{
	return items.shift()
         }

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

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

         this.size = () =>{
	return items.length
          }
}