串列之應用—以串列表示堆疊與佇列 - 筆記長也

串列之應用—以串列表示堆疊與佇列

2018-03-03 16:50:56   資料結構

堆疊與佇列

先前我們在介紹堆疊與佇列,是以陣列實作。本篇文章將以串列的方式來實作堆疊與佇列,關於堆疊與佇列之相關介紹請看「堆疊與佇列圖解概念」一文。

以串列表示堆疊

堆疊之加入

堆疊為一個出入口,因此我們可以看做將資料加入串列的前端。

1.ptr.next=top

2.top=ptr;

    public static void push(){
        
        ptr=new Nodes();
        ptr.data=input.next();
        ptr.next=top;
        top=ptr;
        System.out.println("Push-->OK!");
        
    }

堆疊之刪除

堆疊的刪除我們可以看作刪除串列前端的資料

1.追蹤要刪除的前端節點(clear=top)

2.top=top.next

3.clear=null

    public static void pop(){
        
        if(top==null){
            
            System.out.println("Stack is null!");
            
        }
        else{
            
            Nodes clear;
            clear=top;
            top=top.next;
            clear=null;
            System.out.println("POP -> OK!");
            
        }
        
        
    }

如果把堆疊顛倒,將加入與刪除都作用於末端,也是可以的。

以串列表示佇列

佇列之加入

佇列的加入可以看成將資料加入串列末端。

先判斷rear是否為空,若為空則代表串列為空,需要將front也指向新加入的節點,否則僅需將rear指向加入的節點

if(rear!=null):

1.rear.next=ptr

2.rear=ptr

if(rear==null):

1.rear=ptr

2.front=ptr

    public static void insert(){
        
        System.out.println("Key Your Data:");
        ptr=new Nodeq();
        ptr.data=input.next();
        ptr.next=null;
        if(rear==null)
            front=ptr;
        else
            rear.next=ptr;
        rear=ptr;
        System.out.println("Insesrt -> OK!");
        
    }

佇列之刪除

佇列刪除我們可以視為刪除串列前端之節點,當front==null代表串列為空

1.以clear=front來追蹤要刪除的節點

2.front=front.next

3.clear=null

    public static void del(){
        
        if(front==null)
            System.out.println("Queue is Null!");
        else{
            
            Nodeq clear; 
            clear=front;
            front=front.next;      
            clear=null;
            
        }

完整程式碼(堆疊)

import java.util.Scanner;

class Nodes{
    
    public String data;
    public Nodes next;

}

public class Stack_UseingLinkList {
    
    static Nodes top,ptr,current;
    static Scanner input = new Scanner(System.in);
    
    Stack_UseingLinkList(){
        
    }
    
    public static void push(){
        
        ptr=new Nodes();
        ptr.data=input.next();
        ptr.next=top;
        top=ptr;
        System.out.println("Push-->OK!");
        
    }
    
    public static void pop(){
        
        if(top==null){
            
            System.out.println("Stack is null!");
            
        }
        else{
            
            Nodes clear;
            clear=top;
            top=top.next;
            clear=null;
            System.out.println("POP -> OK!");
            
        }
        
        
    }
    
    public static void printStack(){
        
        current=top;
        while(current!=null){
            
            System.out.println(current.data);
            current=current.next;
            
        }
        
    }


    public static void main(String[] args) {
        Stack_UseingLinkList obj=new Stack_UseingLinkList();
        System.out.println("1.PUSH/2.POP/3.PRINT");
        Scanner doing = new Scanner(System.in);
        while (true){
            
            int don=doing.nextInt();
            switch(don){
                
                case 1:
                    obj.push();
                    break;
                case 2:
                    obj.pop();
                    break;
                case 3:
                   obj.printStack();
                   break;
                
            }
        }
    }
    
}

完整程式碼(佇列)

import java.util.Scanner;

class Nodeq{
    
    public String data;
    public Nodeq next;

}
public class Queue_UseingLinkList {
    
    static Nodeq rear,front,ptr,current;
    static Scanner input = new Scanner(System.in);
    
    public static void insert(){
        
        System.out.println("Key Your Data:");
        ptr=new Nodeq();
        ptr.data=input.next();
        ptr.next=null;
        if(rear==null)
            front=ptr;
        else
            rear.next=ptr;
        rear=ptr;
        System.out.println("Insesrt -> OK!");
        
    }
    
    public static void del(){
        
        if(front==null)
            System.out.println("Queue is Null!");
        else{
            
            Nodeq clear; 
            clear=front;
            front=front.next;      
            clear=null;
            
        }
        
    }
        public static void printStack(){
        
        current=front;
        while(current!=null){
            
            System.out.print(current.data +" ");
            current=current.next;
            
        }
        
    }
    
    
    public static void main(String[] args) {
       Queue_UseingLinkList obj = new Queue_UseingLinkList();
        System.out.println("1.插入/2.刪除/3.PRINT");
        Scanner doing = new Scanner(System.in);
        while (true){
            
            int don=doing.nextInt();
            switch(don){
                
                case 1:
                    obj.insert();
                    break;
                case 2:
                    obj.del();
                    break;
                case 3:
                   obj.printStack();
                   break;
                
            }
        }
    }
    
}

關於作者


長也

資管菸酒生,嘗試成為網頁全端工程師(laravel / React),技能樹成長中,閒暇之餘就寫一些筆記。 喔對了,也愛追一些劇,例如火神跟遺物整理師,推推。最愛的樂團應該是告五人吧(?)