圖說演算法使用JavaScript(十四)

6-6鏈結串列實作佇列

佇列除了能以陣列的方式來實作外，我們也可以鏈結串列來實作佇列。在宣告佇列類別中，除了和佇列類別中相關的方法外，還必須有指向佇列前端及佇列尾端的指標，即front及rear。例如我們以學生姓名及成績的結構資料來建立佇列串列的節點，及front與rear指標宣告如下：

class student  {
   constructor() {
       this.name='';
       this.score=0;
       this.next=null;
    }
}
front=new student();
rear=new student();
front=null;
rear=null;

至於在佇列串列中加入新節點，等於加入此串列的最後端，而刪除節點就是將此串列最前端的節點刪除。加入與刪除運算法如下：

var enqueue=(name, score)=> {  //置入佇列資料
    new_data= new student();   //配置記憶體給新元素
    new_data.name=name;        //設定新元素的資料
    new_data.score = score;
    if (rear==null)            //如果rear為null，表示這是第一個元素
       front = new_data;
    else
       rear.next = new_data;   //將新元素連接至佇列尾端
    rear = new_data;           //將rear指向新元素，這是新的佇列尾端
    new_data.next = null;      //新元素之後無其他元素
}

var dequeue=()=>{              // 取出佇列資料
    if (front == null)
       process.stdout.write('佇列已空!\n');
    else  {
       process.stdout.write('姓名：'+front.name+'\t成績：'+front.score+'...取出');  //將佇列前端一致下一個元素
    }
}

JS          list_queue.js

class student {
	constructor () {
		this.name='';
		this.score=0;
		this.next=null;
	}
}
front=new student();
rear=new student();
front=null;
rear=null;

var enqueue=(name, score)=> {  //置入佇列資料
	new_date=new student();    //配置記憶體給新元素
	new_date.name=name;
	new_date.score=score;
	if (rear==null)            //如果rear為null，表示這是第一個元素
		front=new_date;
	else
		rear.next=new_date;    //將新元素連接至佇列尾端
	rear=new_date;             //將rear指向新元素，這是新的佇列尾端
	new_date.next = null;      //新元素之後無其他元素
}

var dequeue=()=>{    //取出佇列資料
	if(front == null)
		process.stdout.write('佇列已空！\n');
	else {
		process.stdout.write('姓名：'+front.name+'\t成績：'+front.score+'....取出\n');
		front = front.next;    //將佇列前端移至下一個元素
	}

}

var show=()=> {    //顯示佇列資料
	ptr = front;
	if (ptr == null)
		process.stdout.write('佇列已空！\n');
	else {
		while (ptr !=null)  {  //由front往rear走訪佇列
			process.stdout.write('姓名：'+ptr.name+'\t成績：'+ptr.score+'\n');
			ptr = ptr.next;
		}

	}
}

select=0;
const prompt = require('prompt-sync')();
while (true) {
	const select = parseInt(prompt('(1)存入 (2)取出 (3)顯示 (4)離開=> '));
	if (select==4)
		break;
	if (select==1) {
		const name = prompt('姓名： ');
		const score = parseInt(prompt('成績： '));
		enqueue(name, score);
	}
	else if (select==2)
		dequeue();
	else
		show();
}

6-7有趣的雙向佇列

所謂雙向佇列Double Ended Queue, Deque 為一有序串列，加入與刪除可在佇列的任一端進行，請看下圖：

具體來說，雙向佇列就是允許兩端中任意一端都具備有刪除或加入功能，而且無論與尾端指標都是朝佇列中央來移動。通常在一般的應用上，雙向佇列可以區分為兩種：第一種是資料只能從一端加入，但是可從兩端取出。另一種則是可由兩端加入，但由一端取出。以下我們將討論第一種輸入限制的雙向佇列的節點宣告、加入與刪除運算法如下：

class Node   {
      constructor()  {
        this.data=0;
        this.next=null;
    }
}
front=new Node();
rear=new Node();
front=null;
rear=null; 

//方法enqueue:佇列資料的存入
var enqueue=(value)=> {
    node = new Node();
    node.data=value;
    node.next=null;     //檢查是否為空佇列
    if (rear==null)
       fornt=node;      //新建立的節點成為第一個節點
    else
       rear.next=node;  //將節點加入到佇列的尾端
    rear=node;
}

//方法dequeue:佇列資料的取出
var dequeue=(action)=>  {
     //從前端取出資料
     if (!(front==null) && action==1)  {
       if (front==rear) rear=null;
        value=front.data;
        front=front.next;
        return value;
     }
     //從尾端取出資料
    else if (!(rear==null) && action=2) {
        startNode=front;  //先記下前端的指標值
        value=rear.data;  //取出目前尾端的資料
        //尋找最尾端節點的前一個節點
        tempNode=front;
        while (front.next!=rear && front.next!=null){
            front=front.next;
            tempNode=front;
        }
        front=startNode;  //記錄從尾端取出資料後的佇列前端指標
        rear=tempNode;    //紀錄從尾端取出資料後的佇列尾端指標
        //下一列程式是指當佇列中僅剩下最後節點時
        //取出資料後便將 front 及 rear 指向 null
        if (front.next==null || rear.next==null)  {
            front=null;
            rear==null;
         }
        return value;
     }
    else return -1;
}

JS         dequeue.js 

class student {
	constructor () {
		this.name='';
		this.score=0;
		this.next=null;
	}
}
front=new student();
rear=new student();
front=null;
rear=null;

var enqueue=(name, score)=> {  //置入佇列資料
	new_date=new student();    //配置記憶體給新元素
	new_date.name=name;
	new_date.score=score;
	if (rear==null)            //如果rear為null，表示這是第一個元素
		front=new_date;
	else
		rear.next=new_date;    //將新元素連接至佇列尾端
	rear=new_date;             //將rear指向新元素，這是新的佇列尾端
	new_date.next = null;      //新元素之後無其他元素
}

var dequeue=()=>{    //取出佇列資料
	if(front == null)
		process.stdout.write('佇列已空！\n');
	else {
		process.stdout.write('姓名：'+front.name+'\t成績：'+front.score+'....取出\n');
		front = front.next;    //將佇列前端移至下一個元素
	}

}

var show=()=> {    //顯示佇列資料
	ptr = front;
	if (ptr == null)
		process.stdout.write('佇列已空！\n');
	else {
		while (ptr !=null)  {  //由front往rear走訪佇列
			process.stdout.write('姓名：'+ptr.name+'\t成績：'+ptr.score+'\n');
			ptr = ptr.next;
		}

	}
}

select=0;
const prompt = require('prompt-sync')();
while (true) {
	const select = parseInt(prompt('(1)存入 (2)取出 (3)顯示 (4)離開=> '));
	if (select==4)
		break;
	if (select==1) {
		const name = prompt('姓名： ');
		const score = parseInt(prompt('成績： '));
		enqueue(name, score);
	}
	else if (select==2)
		dequeue();
	else
		show();
}