Java中棧和隊列有什么區(qū)別

這期內容當中小編將會給大家?guī)碛嘘PJava中棧和隊列有什么區(qū)別，文章內容豐富且以專業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

Java的特點有哪些

Java的特點有哪些 1.Java語言作為靜態(tài)面向對象編程語言的代表，實現(xiàn)了面向對象理論，允許程序員以優(yōu)雅的思維方式進行復雜的編程。 2.Java具有簡單性、面向對象、分布式、安全性、平臺獨立與可移植性、動態(tài)性等特點。 3.使用Java可以編寫桌面應用程序、Web應用程序、分布式系統(tǒng)和嵌入式系統(tǒng)應用程序等。

一、棧

1.1 概述

Java為什么要有集合類: 臨時存儲數(shù)據(jù)。
鏈表的本質: 對象間通過持有和引用關系互相關聯(lián)起來。

線性表: 普通線性表, 操作受限線性表(某些操作受到限制 --> 某一個線性表它的增刪改操作受到限制) --> 棧 & 隊列

1.1.1 線性表的概念

（1）線性表：n個數(shù)據(jù)元素的有序序列。

①首先，線性表中元素的個數(shù)是有限的。
②其次，線性表中元素是有序的。

（2）那這個”序”指的是什么呢？

①除表頭和表尾元素外，其它元素都有唯一前驅和唯一后繼，其唯一前驅或唯一后繼確定了該元素在線性表中的位置。
②因此，線性表中，每個數(shù)據(jù)元素都有一個確定的位序，這個確定的位序我們稱之為索引。 表頭元素有唯一后繼，無前驅，表尾元素有唯一前驅，無后繼。

1.1.2 棧的概念

棧是一種”操作受限”的線性表，體現(xiàn)在只能在一端插入和刪除數(shù)據(jù)，符合FILO的特性。

FILO: 先進后出,
LIFO: 后進先出

1.1.3 棧的應用

線性表和哈希表在以后工作中會最常用。
棧在實際工作中不常用

應用場景：

1.函數(shù)調用棧
2.反序字符串: 實現(xiàn)reNumber(str)方法,反轉字符串(附代碼) 。

public class DemoStack1 {
    public static void main(String[] args) {

        String str = "123456789";
        String reStr = reStr(str);
        System.out.println(reStr);

    }

    // 棧先進后出
    public static String reStr(String str){
        MyArrayStack<Character> stack = new MyArrayStack<>();

        for (int i = 0; i < str.length(); i++) {
            stack.push(str.charAt(i));
        }

        StringBuffer buffer = new StringBuffer();

        // 1 2 3 4 5 6 7 8 9
        while (!stack.isEmpty()){
            Character pop = stack.pop();
            buffer.append(pop);
        }

        return buffer.toString();
    }
}

3.括號匹配問題: 實現(xiàn)judgeBracket(str)方法來判斷括號匹配 （附代碼）。

public class DemoStack2 {
    public static void main(String[] args) {

        String str = "public class) DemoStack2 {public static void main(String[] args) {}}";

        boolean bool = judgeBracket(str);
        System.out.println(bool);

    }

    public static  boolean judgeBracket(String str){
        MyArrayStack<Character> stack = new MyArrayStack<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            // 判斷c 是left括號, 然后入棧

            if (c == '{'){
                stack.push('}');
            } else if (c == '['){
                stack.push(']');
            }else if (c == '('){
                stack.push(')');
            } else if (c == '}' || c == ')' || c == ']'){
                Character pop = stack.pop();
                if (c != pop){// 不匹配
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

4.編譯器利用棧實現(xiàn)表達式求值

5.瀏覽器的前進后退功能

6.利用棧實現(xiàn) DFS: depth-first-search 深度優(yōu)先遍歷(樹 圖)

編譯器利用棧實現(xiàn)表達式求值

中綴表達式: 2 + 3 * 2 給人看的 , 運算符放到中間
前綴表達式: + 2 * 3 2 運算符放到之前
后綴表達式: 2 3 2 * + 運算符放到后面

// 中綴表達式轉化為后綴:
// 遍歷中綴表達式
// 遇到操作數(shù)輸出
// 遇到操作符, 出棧, 直到遇到更低優(yōu)先級的操作符, 操作符入棧
// 遍歷完成, 全部彈棧

// 中綴表達式轉化為前綴:
// 遍歷中綴表達式: 逆序遍歷
// 遇到操作數(shù)輸出: 頭插法
// 遇到操作符, 出棧, 只彈出更高優(yōu)先級的操作符, 操作符入棧
// 遍歷完成, 全部彈棧

二、隊列

2.1 隊列的概念

隊列也是一種”操作受限”的線性表，體現(xiàn)在一端插入數(shù)據(jù)在另一端刪除數(shù)據(jù)，特性是FIFO。

2.2 隊列的實現(xiàn)

實現(xiàn)一個集合類
集合類: 數(shù)據(jù)容器
底層: 數(shù)組 or 鏈表
數(shù)據(jù)結構表現(xiàn): 隊列

(1)用數(shù)組實現(xiàn)一個隊列。

/**
 * 用數(shù)組實現(xiàn)一個隊列
 * 集合類角度: 數(shù)據(jù)容器
 * 底層: 數(shù)組
 * 表示: 隊列
 */
public class MyArrayQueue <T> {

    private final int MAX_CAPACITY = Integer.MAX_VALUE - 8;
    private final int INIT_CAPACITY = 16;

    private Object[] objs;
    private int size;
    private int head;// 頭的下標
    private int end;// 尾的下標


    public MyArrayQueue(){
        objs = new Object[INIT_CAPACITY];
    }
    public MyArrayQueue(int initCapcity){
        if (initCapcity <= 0 || initCapcity > MAX_CAPACITY) throw new IllegalArgumentException("" + initCapcity);

        objs = new Object[initCapcity];
    }

    public boolean offer(T t){
        // 如果數(shù)組滿了
        if (size == objs.length){
            int newLen = getLen();
            grow(newLen);
        }

        // 可以添加
        if (isEmpty()){
            // 沒有任何元素存儲: 新添加的元素就是唯一的元素
            objs[head] = t;
            end = head;
            size++;
            return true;
        } else {
            // 原本存儲就有內容

            // 尾后移一位
            end = (end + 1) % objs.length;
            objs[end] = t;
            size++;
            return true;
        }
    }

    private void grow(int newLen) {
        Object[] newArr = new Object[newLen];
        for (int i = 0; i < objs.length; i++) {
            int index = (head + i) % objs.length;

            newArr[i] = objs[index];
        }
        objs = newArr;
        head = 0;
        end = size - 1;
    }

    private int getLen() {
        int oldLen = objs.length;
        int newLen = oldLen << 1;
        // 判斷新長度是否溢出
        if (newLen <= 0 || newLen > MAX_CAPACITY){
            newLen = MAX_CAPACITY;
        }
        // 如果新長度和舊長度一樣
        if (newLen == oldLen)throw  new RuntimeException("stack can not add");

        return newLen;
    }


    public T poll(){
        if (isEmpty()) throw new RuntimeException("queue is empty");

        if (size == 1){
            // 原隊列中只剩一個元素
            T oldValue = (T)objs[head];
            head = 0;
            end = 0;
            size--;
            return oldValue;
        } else {
            // 隊列中超過一個元素
            T oldValue = (T)objs[head];
            head = (head + 1) % objs.length;
            size--;
            return oldValue;
        }
    }

    public T peek(){
        if (isEmpty()) throw new RuntimeException("queue is empty");
        return (T)objs[head];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }
}

（2）用鏈表實現(xiàn)一個鏈表。

public class MyLinkedQueue <T> {

    private Node head;// 隊頭
    private Node end; // 隊尾
    private int size;

    // 添加 offer
    // 刪除 poll
    // 查看隊頭元素 peek

    public  boolean offer(T t){

        // 如果原隊列為空
        if (isEmpty()){// 原隊列空
            // 讓頭尾都指向這個新加的結點
            head = new Node(t, null);
            end = head;
            size++;
            return true;
        }

        // 原隊列不空
        // 把這個元素添加到隊尾
        end.next = new Node(t, null);
        end = end.next;// end后移
        size++;
        return true;
    }

    public T poll(){
        if (isEmpty()) throw  new RuntimeException("queue is empty");

        if (size == 1){
            // 代表著, 鏈表中只有一個元素
            T oldVlaue = head.value;
            head = null;
            end = null;
            size--;
            return  oldVlaue;
        }else {
            T oldVlaue = head.value;
            head = head.next;
            size--;
            return oldVlaue;
        }
    }

    public T peek(){
        if (isEmpty()) throw  new RuntimeException("queue is empty");
        return head.value;
    }


    public boolean isEmpty(){
        return size == 0;
    }
    public int size(){
        return size;
    }




    class Node{
        T value;
        Node next;

        public Node(T value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}

2.3 隊列的應用

（1）隊列更不常用(自己寫代碼使用不常用):

（2）常見, 很多jdk源碼, 中間件的源碼上 很多地方使用了隊列

Eg:

①生產者消費者問題

生產者 – 消費者
生產者: 廚師
消費者: 吃面包的人
桌子: 放面包的地方

②線程池

線程池: 任務
生產者: 產生任務
消費者: 線程
桌子: 隊列

③生態(tài)環(huán)境:

第三方輪子: 要看懂
Maven

④消息隊列和緩存。

（3）普通隊列的應用場景是很有限的，一般在工程中用到的是阻塞隊列。

①阻塞隊列(有一個隊列, 大小一定)：常用于生產者-消費者模型中。
當隊列滿的時候，入隊列就阻塞。
當隊列空的時候，出隊列就阻塞。

②利用隊列實現(xiàn) BFS:breadth first search 廣度優(yōu)先搜索/ 遍歷 ()

上述就是小編為大家分享的Java中棧和隊列有什么區(qū)別了，如果剛好有類似的疑惑，不妨參照上述分析進行理解。如果想知道更多相關知識，歡迎關注億速云行業(yè)資訊頻道。