Java數據結構專題解析之棧和隊列的實現

Posted on 2021-10-25 by WalkonNet

1. 棧

1.1 概念

棧：是一種特殊的線性表，其隻允許在固定的一端進行插入和刪除元素操作。
特點：棧中的數據元素遵循先進後出的原則，但要註意進的同時也可以出，元素不是要全部進展後才能出棧
棧頂：進行數據插入和刪除操作的一端
棧底：棧頂的另一端
壓棧：棧的插入操作就做進棧/壓棧/入棧，入數據在棧頂
出棧：棧的刪除操作就叫做出棧，出數據在棧頂

1.2 助解圖題

助解圖：

手槍的彈夾其實就類似是一個棧

在這裡插入圖片描述

當我們壓子彈的時候，就是壓棧

在這裡插入圖片描述

當我們上膛後，打槍時，就是出棧

在這裡插入圖片描述

助解題：

題一：一個棧的入棧順序是 a、b、c、d、e，該棧不可能的出棧順序是（） A.edcba B.decba C.dceab D.abcde

結果為：C

題二：中綴表達式為 a + b * c + ( d * e + f ) * g，那麼它的後綴表達式為什麼？

結果為：a b c * + d e * f + g * +

方法步驟（快捷方法）：

在這裡插入圖片描述

該方法中將括號的運算符移到括號前面得到的結果就是前綴表達式

本題背景：我們平常使用的表達式一般為中綴表達式，中綴表達式便於人們的理解與計算。而後綴表達式的運算符更方便計算機的運算（如二叉樹、堆棧的方法計算）

題三：通過棧返回後綴表達式 a b c * + d e * f + g * + 計算的結果

結果為：a + b * c + ( d * e + f ) * g

方法：當參數是數字時就壓棧。當參數為運算符時，出棧第一個數作為運算符後的參數，出棧第二個參數作為運算符前的參數，將結果再壓入棧中。

1.3 棧的數組實現

在 Java 中棧的底層其實是一個數組，並且它擁有壓棧、出棧等等方法，借助這些我們來自己實現一個棧

public class MyStack{
    // 定義一個整型的數組，也可以直接使用泛型
    public int[] elem;
    // 定義數組已經使用的長度，初始時為0
    public int usedSize;
    // 創建 MyStack 的構造方法
    public MyStack(){
        // 用 Mystack 創建對象時初始化數組的長度為10
        this.elem=new int[10];
    }
    // 判斷棧是否已滿
    public boolean isFull(){
        return usedSize==this.elem.length;
    }
    // 壓棧
    public int push(int val){
        if(isFull()){
            // 擴容
            this.elem=Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.usedSize++]=val;
        return val;
    }
    // 出棧
    public int pop(){
        if(empty()){
            throw new RuntimeException("棧為空");
        }
        this.usedSize--;
        return this.elem[this.usedSize];
    }
    // 查看棧頂元素，不刪除
    public int peek(){
        if(empty()){
        	throw new RuntimeException("棧為空");
        }
        return this.elem[this.usedSize-1];
    }
    // 判斷棧是否為空
    public boolean empty(){
        return usedSize==0;
    }
}

1.4 問題

我們上述的棧是用數組實現的，入棧和出棧的時間復雜度都為 O(1)

那麼棧能否用單鏈表實現呢？

使用頭插法：入棧時間復雜度為 O(1)，出棧時間復雜度為 O(1)
使用尾插法：入棧時間復雜度為 O(N)，出棧時間復雜度為 O(N)

綜上分析，棧可以通過單鏈表的頭插頭刪法實現

1.5 棧的單鏈表實現

接下來將使用單鏈表實現棧，註意要使用頭插頭刪法

class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
    }
}
public class MyStack{
    Node head=null;
    // 壓棧
    public int push(int val){
        Node node=new Node(val);
        node.next = head;
        head = node;
        return head.val;
    }
    // 出棧
    public int pop(){
        if(empty()){
            throw new RuntimeException("棧為空");
        }
        int val=head.val;
        head=head.next;
        return val;
    }
    // 查看棧頂元素，不刪除
    public int peek(){
        if(empty()){
            throw new RuntimeException("棧為空");
        }
        return head.val;
    }
    // 判斷棧是否為空
    public boolean empty(){
        return head==null;
    }
}

2. 隊列

2.1 概念

隊列：隻允許在一端進行插入數據操作，在另一端進行刪除操作的特殊線性表。
特點：隊列具有先進先出的特點
對頭：進行刪除操作的一端
隊尾：進行插入操作的一段

在這裡插入圖片描述

2.2 問題

在我們實現隊列前，要思考隊列是靠數組實現呢還是拿鏈表實現呢？

在 Java 當中，隊列是由 LinkedList 實現的，它的底層是一個雙向鏈表。

對於雙向鏈表：我們隻要在尾節點進行入隊操作，在頭節點進行出隊操作就很容易實現
對於單鏈表：我們隻要增加一個尾巴節點，然後尾巴節點進行入隊操作，頭節點進行出隊操作也能實現

至於數組，我們上述通過它實現瞭棧，而棧的特點其實是先進後出，與隊列的先進先出原則矛盾。使用數組來實現隊列會很麻煩。

2.3 隊列的單鏈表實現

根據 Java 中隊列的一些方法，接下來我們來實現自己的隊列

class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
    }
}
public class MyQueueLinked {
    private Node front;
    private Node rear;
    private int usedSize;
    // 入隊列
    public void offer(int val){
        Node node=new Node(val);
        if(this.front==null){
            this.front=node;
            this.rear=node;
        }else{
            this.rear.next=node;
            this.rear=node;
        }
        this.usedSize++;
    }
    // 出隊列
    public int poll(){
       if(isEmpty()){
           throw new RuntimeException("隊列為空");
       }
       int val=this.front.val;
       if(this.front.next==null){
           this.front=null;
           this.rear=null;
       }else{
           this.front=this.front.next;
       }
        this.usedSize--;
        return val;
    }
    // 得到隊頭元素不刪除
    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("隊列為空");
        }else{
            return this.front.val;
        }
    }
    // 判斷隊列是否為空
    public boolean isEmpty(){
        return this.usedSize==0;
    }
    // 得到隊列長度
    public int size(){
        return this.usedSize;
    }
}

上述隊列是用單鏈表實現的，也叫鏈式隊列。大傢也可以自行嘗試一下雙鏈表實現隊列。

2.4 數組實現隊列

假設現在我們用數組模擬入隊列和出隊列的模型

在這裡插入圖片描述

解決方法：

方法一：出隊時，移動數組將後面的元素往前覆蓋（時間復雜度為 O(N)）
方法二：使用循環的方法，實現循環隊列（時間復雜度為 O(1)）

2.5 循環隊列

循環隊列即數組使用瞭循環的方式，讓數組方便隊列的入隊和出隊。那麼怎麼實現呢？模型如下

在這裡插入圖片描述

front：指向的位置就是隊列的頭，既已經存放數據的第一個下標（刪除數據一端）
rear：指向的位置就是隊列的尾巴，即可以存放數據的第一個下標（插入數據一端）

問題1：如何判斷 front = rear 時是空還是滿？

為瞭能夠區別是空還是滿，我們常假定當 front = rear 時為空。而對於滿的話，我們則會將這個數組保留一個空的位置，那麼當 rear+1 = front 時，則隊列滿瞭

在這裡插入圖片描述

問題2：當 front 在數組最後一個位置時，如何再移它到數組的第一個位置呢？

(下標+1)%數組長度

接下來讓我們實現循環隊列

public class MyCircularQueue {
    private int[] elem;
    private int front;
    private int rear;
    public MyCircularQueue(int k){
        this.elem=new int[k+1];
    }
    // 判斷隊列是否滿瞭
    public boolean isFull(){
        return (this.rear+1)%this.elem.length==this.front;
    }
    // 判斷隊列是否為空
    public boolean isEmpty(){
        return this.front==this.rear;
    }
    // 入隊
    public void enQueue(int val){
        if(isFull()){
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[this.rear]=val;
        this.rear=(this.rear+1)%this.elem.length;
    }
    // 出隊
    public int deQueue(){
        if(isEmpty()){
            throw new RuntimeException("隊列為空");
        }
        int val=this.elem[this.front];
        this.front=(this.front+1)%this.elem.length;
        return val;
    }
    // 得到隊頭元素
    public int getFront(){
        if(isEmpty()){
            throw new RuntimeException("隊列為空");
        }
        return this.elem[this.front];
    }
    // 得到隊尾元素
    public int getRear(){
        if(isEmpty()){
            throw new RuntimeException("隊列為空");
        }
        if(this.rear==0){
            return this.elem[this.elem.length-1];
        }
        return this.elem[this.rear - 1];
    }
}

註意：

假設一個數組長度為3，做題時可能人傢用例入隊瞭3次，但是按照上述隊列為滿的方式，我們其實是保留瞭一個位置是不能存放數據的。因此對於這種題目我們可以將我們的數組開大一位

2.6 雙端隊列

雙端隊列：是指允許兩端都可以進行入隊和出隊操作的隊列
特點：元素可以從隊頭出隊和入隊，也可以從隊尾出隊和入隊

雙端隊列較簡單，可以使用雙向鏈表實現，這裡就展示一下雙端隊列的模型

在這裡插入圖片描述

3. 棧和隊列練習題

3.1 有效的括號

題目（OJ 鏈接）：

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

有效字符串需滿足：左括號必須用相同類型的右括號閉合，左括號必須以正確的順序閉合。

題解：使用棧，遍歷字符串，是左括號就進行入棧，是右括號就與棧頂元素比較。

public boolean isValid(String s) {
    Stack<Character> stack=new Stack<>();
    for(int i=0;i<s.length();i++){
        char ch=s.charAt(i);
        switch(ch){
            case ')':
                if(stack.empty()||stack.pop()!='('){
                    return false;
                }
                break;
            case '}':
                if(stack.empty()||stack.pop()!='{'){
                    return false;
                }
                break;
            case ']':
                if(stack.empty()||stack.pop()!='['){
                    return false;
                }
                break;
            default:
                stack.push(ch);
                break;
        }
    }
    if(stack.empty()){
        return true;
    }
    return false;
}

3.2 用隊列實現棧

題目（OJ鏈接）：

請你僅使用兩個隊列實現一個後入先出（LIFO）的棧，並支持普通棧的全部四種操作（push、top、pop 和 empty）。

題解：

由於隊列是先進先出，棧是先進後出，故一個隊列無法滿足實現棧的能力。而使用兩個隊列，對於入棧，我們我隻要找到棧不為空的隊列進行入隊就行；對於出棧，我們隻要將不為空的隊列的除最後一個入隊的元素全部轉移到另一個空隊列中，再將留下的元素出隊

代碼：

class MyStack {
    private Queue<Integer> q1;
    private Queue<Integer> q2;
    public MyStack() {
        q1=new LinkedList<>();
        q2=new LinkedList<>();
    }
    // 入棧
    public void push(int x) {
        if(!q1.isEmpty()){
            q1.offer(x);
        }else if(!q2.isEmpty()){
            q2.offer(x);
        }else{
            q1.offer(x);
        }
    }
    // 出棧
    public int pop() {
        if(empty()){
            throw new RuntimeException("棧為空");
        }
        if(!q1.isEmpty()){
            int val1=0;
            while(!q1.isEmpty()){
                val1=q1.poll();
                if(!q1.isEmpty()){
                    q2.offer(val1);
                }
            }
            return val1;
        }else{
            int val2=0;
            while(!q2.isEmpty()){
                val2=q2.poll();
                if(!q2.isEmpty()){
                    q1.offer(val2);
                }
            }
            return val2;
        }
    }
    // 得到棧頂元素不刪除
    public int top() {
        if(empty()){
            throw new RuntimeException("棧為空");
        }
        if(!q1.isEmpty()){
            int val1=0;
            while(!q1.isEmpty()){
                val1=q1.poll();
                q2.offer(val1);
            }
            return val1;
        }else{
            int val2=0;
            while(!q2.isEmpty()){
                val2=q2.poll();
                q1.offer(val2);
            }
            return val2;
        }
    }
    // 判斷棧是否為空
    public boolean empty() {
        return q1.isEmpty()&&q2.isEmpty();
    }
}

3.3 用棧實現隊列

題目（OJ 鏈接）：

請你僅使用兩個棧實現先入先出隊列。

題解：

我們可以創建兩個棧 s1、s2，s1 用來入隊，s2 用來出隊

代碼：

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    public MyQueue() {
        s1=new Stack<>();
        s2=new Stack<>();
    }
    // 入隊
    public void push(int x) {
        s1.push(x);
    }
    // 出隊
    public int pop() {
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.pop();
    }
    // 返回隊首元素，不刪除
    public int peek() {
        if(empty()){
            return -1;
        }
        if(s2.empty()){
            while(!s1.empty()){
                s2.push(s1.pop());
            }
        }
        return s2.peek();
    }
    // 判斷隊列是否為空
    public boolean empty() {
        return s1.empty()&&s2.empty();
    }
}

3.4 實現一個最小棧

題目（OJ 鏈接）：

設計一個支持 push ，pop ，top 操作，並能在常數時間內檢索到最小元素的棧。

題解：

我們可以創建兩個棧，一個棧就是用來存儲刪除元素，另一個就是專門用來存儲最小值的棧。註意這個最小值是存儲該元素時該棧的最小值

代碼：

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;
    public MinStack() {
        stack=new Stack<>();
        minStack=new Stack<>();
    }
    // 入棧
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            if(val<=minStack.peek()){
                minStack.push(val);
            }
        }
    }
    // 出棧
    public void pop() {
        int val=stack.pop();
        if(minStack.peek()==val){
            minStack.pop();
        }
    }
    // 得到棧頂元素，不刪除
    public int top() {
        return stack.peek();
    }
    // 得到此時棧的最小值
    public int getMin() {
        return minStack.peek();
    }
}

3.5 設計循環隊列

題目（OJ 鏈接）：

設計你的循環隊列實現。循環隊列是一種線性數據結構，其操作表現基於 FIFO（先進先出）原則並且隊尾被連接在隊首之後以形成一個循環。它也被稱為“環形緩沖器”。

題解：

通過 (下標+1)%數組長度 的方式將數組形成一個循環，先設定好數組為空和為滿的條件。註意防止題目將數組存滿，開數組時的大小要註意。

代碼：

class MyCircularQueue {
    private int[] elem;
    private int front;
    private int rear;
    public MyCircularQueue(int k) {
        this.elem=new int[k+1];
    }
    // 入隊列
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        this.elem[rear]=value;
        this.rear=(this.rear+1)%this.elem.length;
        return true;
    }
    // 出隊列
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front=(this.front+1)%this.elem.length;
        return true;
    }
    // 得到隊首元素，不刪除
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.elem[front];
    }
    // 得到隊尾元素，不刪除
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        if(this.rear==0){
            return this.elem[this.elem.length-1];
        }
        return this.elem[this.rear-1];
    }
    // 判斷隊列是否為空
    public boolean isEmpty() {
        return this.rear==this.front;
    }
    // 判斷隊列是否滿瞭
    public boolean isFull() {
        return (this.rear+1)%this.elem.length==this.front;
    }
}

到此這篇關於Java數據結構專題解析之棧和隊列的實現的文章就介紹到這瞭,更多相關Java 棧和隊列的實現內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

Java數據結構專題解析之棧和隊列的實現

目錄

1. 棧

1.1 概念

1.2 助解圖題

1.3 棧的數組實現

1.4 問題

1.5 棧的單鏈表實現

2. 隊列

2.1 概念

2.2 問題

2.3 隊列的單鏈表實現

2.4 數組實現隊列

2.5 循環隊列

2.6 雙端隊列

3. 棧和隊列練習題

3.1 有效的括號

3.2 用隊列實現棧

3.3 用棧實現隊列

3.4 實現一個最小棧

3.5 設計循環隊列

推薦閱讀：

發佈留言取消回覆

近期文章

目錄

1. 棧

1.1 概念

1.2 助解圖題

1.3 棧的數組實現

1.4 問題

1.5 棧的單鏈表實現

2. 隊列

2.1 概念

2.2 問題

2.3 隊列的單鏈表實現

2.4 數組實現隊列

2.5 循環隊列

2.6 雙端隊列

3. 棧和隊列練習題

3.1 有效的括號

3.2 用隊列實現棧

3.3 用棧實現隊列

3.4 實現一個最小棧

3.5 設計循環隊列

推薦閱讀：

發佈留言 取消回覆

近期文章

標籤

發佈留言取消回覆