Java數據結構專題解析之棧和隊列的實現(xiàn)

更新時間：2021年10月25日 10:27:17 作者：謝謝你，泰羅！

從數據結構的定義看，棧和隊列也是一種線性表。其不同之處在于棧和隊列的相關運算具有特殊性，只是線性表相關運算的一個子集。更準確的說，一般線性表的插入、刪除運算不受限制，而棧和隊列上的插入刪除運算均受某種特殊限制。因此，棧和隊列也稱作操作受限的線性表

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 棧的數組實現(xiàn)

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

public class MyStack{
    // 定義一個整型的數組，也可以直接使用泛型
    public int[] elem;
    // 定義數組已經使用的長度，初始時為0
    public int usedSize;
    // 創(chuàng)建 MyStack 的構造方法
    public MyStack(){
        // 用 Mystack 創(chuàng)建對象時初始化數組的長度為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 問題

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

那么棧能否用單鏈表實現(xiàn)呢？

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

綜上分析，?？梢酝ㄟ^單鏈表的頭插頭刪法實現(xiàn)

1.5 棧的單鏈表實現(xiàn)

接下來將使用單鏈表實現(xiàn)棧，注意要使用頭插頭刪法

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 問題

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

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

對于雙向鏈表：我們只要在尾節(jié)點進行入隊操作，在頭節(jié)點進行出隊操作就很容易實現(xiàn)
對于單鏈表：我們只要增加一個尾巴節(jié)點，然后尾巴節(jié)點進行入隊操作，頭節(jié)點進行出隊操作也能實現(xiàn)

至于數組，我們上述通過它實現(xiàn)了棧，而棧的特點其實是先進后出，與隊列的先進先出原則矛盾。使用數組來實現(xiàn)隊列會很麻煩。

2.3 隊列的單鏈表實現(xiàn)

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

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;
    }
}

上述隊列是用單鏈表實現(xiàn)的，也叫鏈式隊列。大家也可以自行嘗試一下雙鏈表實現(xiàn)隊列。

2.4 數組實現(xiàn)隊列

假設現(xiàn)在我們用數組模擬入隊列和出隊列的模型

在這里插入圖片描述

解決方法：

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

2.5 循環(huán)隊列

循環(huán)隊列即數組使用了循環(huán)的方式，讓數組方便隊列的入隊和出隊。那么怎么實現(xiàn)呢？模型如下

在這里插入圖片描述

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

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

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

在這里插入圖片描述

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

(下標+1)%數組長度

接下來讓我們實現(xiàn)循環(huán)隊列

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 雙端隊列

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

雙端隊列較簡單，可以使用雙向鏈表實現(xiàn)，這里就展示一下雙端隊列的模型

在這里插入圖片描述

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 用隊列實現(xiàn)棧

題目（OJ鏈接）：

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

題解：

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

代碼：

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 用棧實現(xiàn)隊列

題目（OJ 鏈接）：

請你僅使用兩個棧實現(xiàn)先入先出隊列。

題解：

我們可以創(chuàng)建兩個棧 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 實現(xiàn)一個最小棧

題目（OJ 鏈接）：

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

題解：

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

代碼：

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 設計循環(huán)隊列

題目（OJ 鏈接）：

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

題解：

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

代碼：

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數據結構專題解析之棧和隊列的實現(xiàn)的文章就介紹到這了,更多相關Java 棧和隊列的實現(xiàn)內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

Java并發(fā)編程：CountDownLatch與CyclicBarrier和Semaphore的實例詳解
這篇文章主要介紹了Java并發(fā)編程：CountDownLatch與CyclicBarrier和Semaphore的實例詳解的相關資料,需要的朋友可以參考下
2017-09-09
Spring boot項目使用thymeleaf模板過程詳解
這篇文章主要介紹了Spring boot項目使用thymeleaf模板過程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2020-07-07
RocketMQ中的消息發(fā)送與消費詳解
這篇文章主要介紹了RocketMQ中的消息發(fā)送與消費詳解,RocketMQ是一款高性能、高可靠性的分布式消息中間件,消費者是RocketMQ中的重要組成部分,消費者負責從消息隊列中獲取消息并進行處理,需要的朋友可以參考下
2023-10-10
Java堆排序算法詳解
這篇文章主要為大家詳細介紹了Java堆排序算法的相關代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2017-09-09
Eclipse插件開發(fā)實現(xiàn)控制臺輸出信息的方法
今天小編就為大家分享一篇關于Eclipse插件開發(fā)實現(xiàn)控制臺輸出信息的方法，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧
2019-01-01
java原碼補碼反碼關系解析
這篇文章主要為大家詳細介紹了java原碼補碼反碼的關系，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2020-02-02
使用Spring方法攔截器MethodInterceptor
這篇文章主要介紹了使用Spring方法攔截器MethodInterceptor，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2021-10-10
詳解Java中的數組與字符串相關知識
這篇文章主要介紹了詳解Java中的數組與字符串相關知識,包括操作字符串的一些基本方法列舉,需要的朋友可以參考下
2015-09-09
Java全面解析IO流相關知識
這篇文章主要介紹了IO流相關知識，包括File，字節(jié)流，字符流，特殊操作流（標準輸入流，標準輸出流，對象序列化與反序列化，properties與IO流結合）相關知識的總結
2021-08-08
用Rational Rose逆向工程(java)生成類圖(教程和錯誤解決)
Rational Rose有個很方便的功能，將項目中的JAVA代碼自動轉換成UML類圖
2013-02-02