[IT技術30篇挑戰] 資料結構和演算法實作 DAY4

章節連結

指令
LeetCode 練習記錄
系列文章

一個遵循FIFO(First In First Out)後進先出的原則。現實中的例子就是排隊，先來先服務的概念。以 JavaScript 的 array 陣列相關函式來呈現這個資料結構，算是滿輕鬆寫意的。

指令

/*Queue*/
function Queue(){
	var items=[];
	this.enqueue = element =>{
		return items.push(element)
	}

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

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

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

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

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

	this.print = () =>{
		return console.log(items.toString())
	}
}

/*Queue with different priority*/
function PriorityQueue(){
	let items = []

	//以函式產生佇列內的各個元素實例(instance)
	function QueueElement(element,priority){
		this.element = element
		this.priority = priority
	}

	this.enqueue = (element,priority) =>{
		let queueElement = new QueueElement(element,priority)
		let added = false
		for (let i=0; i<items.length; i++){
    		if (queueElement.priority < items[i].priority){
      		items.splice(i,0,queueElement)
      		added = true
      		break
    		}
  		}
  		if (!added){
    		items.push(queueElement)
  		}
		
	}

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

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

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

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

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

	this.print = () =>{
  		return console.log(items)
 	};
}

let priorityQueue = new PriorityQueue()
priorityQueue.enqueue("John",2)
priorityQueue.enqueue("Sandy",4)
priorityQueue.enqueue("Mandy",2)
priorityQueue.enqueue("Jack",1)
priorityQueue.enqueue("Camila",1)
priorityQueue.enqueue("Tom",3)
priorityQueue.print()

/*Queue*/

function Queue(){

var items=[];

this.enqueue = element =>{

return items.push(element)

}

this.dequeue = () =>{

return items.shift()

}

this.front = () =>{

return items[0]

}

this.isEmpty = () =>{

return items.length === 0

}

this.clear = () =>{

return items = []

}

this.size = () =>{

return items.length

}

this.print = () =>{

return console.log(items.toString())

}

/*Queue with different priority*/

function PriorityQueue(){

let items = []

//以函式產生佇列內的各個元素實例(instance)

function QueueElement(element,priority){

this.element = element

this.priority = priority

}

this.enqueue = (element,priority) =>{

let queueElement = new QueueElement(element,priority)

let added = false

for (let i=0; i<items.length; i++){

if (queueElement.priority < items[i].priority){

items.splice(i,0,queueElement)

added = true

break

}

if (!added){

items.push(queueElement)

}

this.dequeue = () =>{

return items.shift()

}

this.front = () =>{

return items[0]

}

this.isEmpty = () =>{

return items.length === 0

}

this.clear = () =>{

return items = []

}

this.size = () =>{

return items.length

}

this.print = () =>{

return console.log(items)

};

}

let priorityQueue = new PriorityQueue()

priorityQueue.enqueue("John",2)

priorityQueue.enqueue("Sandy",4)

priorityQueue.enqueue("Mandy",2)

priorityQueue.enqueue("Jack",1)

priorityQueue.enqueue("Camila",1)

priorityQueue.enqueue("Tom",3)

priorityQueue.print()

LeetCode 練習記錄

// 622. Design Circular Queue https://leetcode.com/problems/design-circular-queue/
var MyCircularQueue = function(k) {
    this.items = []
    this.size = k+1
    this.front = 0
    this.rear = 0
};

MyCircularQueue.prototype.enQueue = function(value) {
    if(!this.isFull()){
        this.items[this.rear] = value
        this.rear = (this.rear+1)%this.size
        return true
    }
    return false
};

MyCircularQueue.prototype.deQueue = function() {
    if(!this.isEmpty()){
        this.front = (this.front+1)%this.size
        return true
    }
    return false
};

MyCircularQueue.prototype.Front = function() {
    if(!this.isEmpty()){
        return this.items[this.front]
    }
    return -1
};

MyCircularQueue.prototype.Rear = function() {
    if(!this.isEmpty()){
        return this.items[(this.rear+this.size-1)%this.size]
    }
    return -1
};

MyCircularQueue.prototype.isEmpty = function() {
    return this.front === this.rear
};

MyCircularQueue.prototype.isFull = function() {
    return (this.rear+1)%this.size === this.front
};

/** 
 * Your MyCircularQueue object will be instantiated and called as such:
 * var obj = new MyCircularQueue(k)
 * var param_1 = obj.enQueue(value)
 * var param_2 = obj.deQueue()
 * var param_3 = obj.Front()
 * var param_4 = obj.Rear()
 * var param_5 = obj.isEmpty()
 * var param_6 = obj.isFull()
 */