資料結構--堆疊和佇列的使用

目錄

一、堆疊的理解和使用

1.1什么是堆疊

1.2堆疊的簡單實作

1.3堆疊中方法的介紹

1.4 關于堆疊的練習

二、佇列的理解和使用

2.1什么是佇列

2.2對于簡單佇列的實作

2.3佇列中方法的介紹

三、回圈佇列

一、堆疊的理解和使用

1.1什么是堆疊

堆疊是一種特殊的線性表只能允許在一段進行插入和洗掉操作，進行插入和洗掉操作的一端叫堆疊頂，另一端稱為堆疊底，

出堆疊和入堆疊就是將元素從堆疊頂拿出或者拿入，

1.2堆疊的簡單實作

public class MyStack01 {
    int[] elem;
    int usedSize;
    public MyStack01(){
        this.elem=new int[10];
        this.usedSize=0;
    }

    public boolean isFull(){
        if(this.elem.length==usedSize){
            return true;
        }
        return false;
    }
    //添加
    public void push(int val){
        if(isFull()){
            this.elem=Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[this.usedSize]=val;
        this.usedSize++;
    }

    public boolean isEmpty(){
        return this.usedSize==0;
    }
    //出堆疊
    public int pop(){
        if(isEmpty()){
            System.out.println("堆疊中沒有元素");
            return -1;
        }
        int val=this.elem[usedSize-1];
        usedSize--;
        return val;
    }
    //查找堆疊頂元素
    public int peek(){
        if(isEmpty()){
            System.out.println("堆疊中沒有元素");
            return -1;
        }
        return this.elem[usedSize-1];
    }
}

1.3堆疊中方法的介紹

1.4 關于堆疊的練習

括號匹配問題：題目，

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字串 s ，判斷字串是否有效，

    public boolean isValid(String s) {
        if(s.length()==0||s==null) return false;
        Stack<Character> stack=new Stack<>();
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(ch=='('||ch=='{'||ch=='['){
                stack.push(ch);
            }else{
                if(stack.empty()){
                    return false;
                }
                char ch01=stack.peek();
                if((ch==')'&&ch01=='(')||(ch=='}'&&ch01=='{')||(ch==']'&&ch01=='[')){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }

        return stack.empty();
    }

二、佇列的理解和使用

2.1什么是佇列

佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出 ，入佇列：進行插入操作的一端稱為隊尾，出佇列：進行洗掉操作的一端稱為隊頭，

2.2對于簡單佇列的實作

public class MyQueue {
    Node head;
    Node last;
    int usedSize;
    //入佇列
    public void offer(int val) {
        Node node=new Node(val);
        if(head==null){
            this.head=node;
            this.last=node;
        }else{
            this.last.next=node;
            this.last=node;
        }
    }

    //出對頭元素
    public int poll() {
        if(isEmpty()){
            throw new RuntimeException("佇列為空");
        }
        int val=this.head.data;
        if(this.head.next==null){
            this.head=null;
            this.last=null;
        }else{
            this.head=this.head.next;
        }
        return val;
    }

    //得到對頭元素
    public int peek() {
        if(isEmpty()){
            throw new RuntimeException("佇列為空");
        }
        return this.head.data;
    }

    public boolean isEmpty() {
        return this.usedSize==0;
    }

    public int size() {
        return this.usedSize;
    }
}

2.3佇列中方法的介紹

三、回圈佇列

回圈佇列是指用陣列來實作佇列（一般佇列是用鏈表來實作的），

我們通過head指向第一個和last指向最后一個的后面，兩個指向來撰寫，

public class MyQueue01 {
    int[] elem;
    int usedSize;
    int head;
    int last;

    public MyQueue01(int k) {
        this.elem=new int[k+1];
    }

    //向回圈佇列插入一個元素，如果成功插入則回傳真
    public boolean enQueue(int value) {
        if(isFull()) return false;
        this.elem[this.last]=value;
        this.last=(this.last+1)%this.elem.length;
        return true;
    }

    //從回圈佇列中洗掉一個元素，如果成功洗掉則回傳真，
    public boolean deQueue() {
        if(isEmpty()) return false;
        this.head=(this.head+1)%this.elem.length;
        return true;
    }

    //從隊首獲取元素，如果佇列為空，回傳 -1 ，
    public int Front() {
        if(isEmpty()) return -1;
        int val=this.elem[this.head];
        return val;
    }

    //獲取隊尾元素，如果佇列為空，回傳 -1 ，
    public int Rear() {
        if(isEmpty()) return -1;
        if(this.last==0){
            return this.elem[this.elem.length-1];
        }
        return this.elem[this.last-1];
    }

    //檢查回圈佇列是否為空，
    public boolean isEmpty() {
        if(this.head==this.last){
            return true;
        }
        return false;
    }

    //檢查回圈佇列是否已滿，
    public boolean isFull() {
        if((this.last+1)%elem.length==this.head){
            return true;
        }
        return false;
    }

}