一文帶你認識Java棧和佇列

本篇文章為大家帶來了關於java的相關知識，其中主要整理了堆疊和佇列的相關問題，包括了堆疊和佇列的定義、應用、實作和操作等等內容，下面一起來看一下，希望對大家有幫助。

推薦學習：《java影片教學》

在學習堆疊和佇列之前，先了解什麼是線性表：一次保存單一同類型的元素，多個元素之間邏輯上連續，例如數組，鍊錶，字串，棧和隊列
棧和隊列其實操作受限的線性表，數組也罷，鍊錶也罷，既可以在頭部插入和刪除，也能在尾部插入和刪除，但是棧和隊列只能在一端插入，在一端刪除

一、棧

#1.定義

只能在一端插入元素，也只能在這一端刪除元素（棧頂），可以把棧看作一個“水杯”，只能從一端添加元素，也只能從一段刪除元素，而且，先進入水杯的水在杯底，後進入水杯的水在杯頂，往出倒水的時候，也是倒出的杯頂的水，棧也是一樣，先入棧的元素在棧底，後入棧的元素在棧頂，所以先入棧的元素後出，後入棧的元素先出，這也是棧的特性「先進後出，後進先出」Last In First Out(LIFO),取出元素和添加元素只能在棧頂。
將1 2 3 4 5，一次放入堆疊中

#2.堆疊的應用

1.無所不在的undo(撤銷)操作

在任何一個編輯器中輸錯一個內容後，使用Ctrl z就返回到了輸入的內容；
在任何一個瀏覽器中點擊後退操作

都是棧的這個結構的應用
1.使用編輯器使用撤銷操作，一次輸入就把內容壓入棧中，再輸入就就再壓入棧中，發現一次輸入錯誤，就使用撤銷操作，把當前棧頂的錯誤內容彈出，那麼目前棧頂的內容就是上次輸入的內容。
2.瀏覽網頁其實也是相同原理的，就像打開百度-> 打開csdn -> 打開創作中心，也是使用棧這個結構，先把百度網頁壓入棧中，然後csdn網頁壓入棧中，然後創作中心網頁壓入堆疊中，想要返回csdn主頁，按下後頭箭頭，就把當前棧頂的創作中心網頁彈出，取出csdn主頁。

2.作業系統堆疊

程式再執行的過程中，從A函數呼叫B函數，從B函數呼叫C函數，呼叫結束，返回執行時，如何得知從哪繼續開始執行呢，背後也是棧這個結構

3.棧的實現

基於鍊錶實現的棧– 鍊式棧
基於數組實現的棧– 順序棧（使用較多）
定義一個基於動態陣列實作的堆疊

//基于动态数组实现的顺序栈public class MyStack<e> {
    //记录当前栈的元素个数
    private int size;
    //实际存储数据的动态数组，此时在栈中只能在数组的尾部添加和删除元素
    private List<e> data = new ArrayList();
    }</e></e>

4.堆疊的操作

1.向堆疊中新增一個元素
只能在堆疊頂部新增

 /**
     * 向当前栈中添加元素 -- >压栈操作
     * @param val
     */
    public void push(E val){
        data.add(val);
        size++;
    }

2.目前從堆疊頂端彈出一個元素

/**
     * 弹出当前栈顶元素,返回栈顶元素的值
     * @return
     */
    public E pop(){
        if (isEmpty()){
            //栈为空无法弹出
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        //在数组末尾删除元素
        E val = data.get(size - 1);
        data.remove(size - 1);
        size --;
        return val;
    }

3.查看目前棧頂元素，但不彈出

/**
     * 查看当前栈顶元素值，不弹出该元素
     * @return
     */
    public E peek(){
        if (isEmpty()){
            throw new NoSuchElementException("stack is empty!cannot peek!");
        }
        return data.get(size - 1);
    }

二、佇列

1.定義

佇列：先進先出（FIFO）的資料結構i，元素只能從隊尾加入到佇列中，也只能從隊首出佇列，元素的出隊順序與入隊順序保持一致
將1 2 3 4 5依序入隊

#2.隊列的應用

現實生活中，各種各樣的「排隊」操作

3.佇列的實作

基於陣列實作的佇列– 順序佇列
基於鍊錶實作的佇列– 鍊式佇列
出隊運算只能在佇列的頭部進行，若採用數組實現的隊列，每次出隊一個元素就得搬移剩下的所有元素向前移動一個單位，此時採用鍊錶實現的隊列更適合隊列的結構，刪除元素只需要刪除頭結點，添加元素在鍊錶的尾部添加

public interface Queue<e> {
    //入队操作
    void offer(E val);
    //出队操作
    E poll();
    //查看队首元素
    E peek();
    boolean isEmpty();}</e>

對於棧來說隊列的實現子類是比較多的，例如
FIFO隊列
雙端隊列
循環隊列
優先權佇列
不管哪個佇列都要實作

4.FIFO佇列

1.定義一個FIFO佇列

// An highlighted blockvar foo = 'bar';

2.在佇列中加入一個元素

public void offer(E val) {
        Node<e> node = new Node(val);
        if (head == null){
            head = tail = node;
        }else{
            //链表的尾插
            tail.next = node;
            tail = node;
        }
        size++;
    }</e>

3.從目前隊首出隊一個元素

 public E poll() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty! cannot poll!");
        }
        //头删
        E val = head.val;
        Node<e> node = head;
        head = head.next;
        node.next = node = null;
        size--;
        return val;
    }</e>

4.查看目前隊列的隊首元素

public E peek() {
        if (isEmpty()){
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }

5.循环队列

1.定义：基本上都是使用固定长度的数组来实现，数组在实现队时，若从数组头部删除元素需要频繁的移动后面的元素，效率比较低；出队和入队操作，使用两个引用，一个head，一个tail,添加元素在数组的尾部添加，删除元素只需要移动head引用指向的地址即可（逻辑删除）
2.应用：操作系统的生产消费者模型，MySQL数据库的InnoDB存储引擎的redo日志
3.循环队列就是使用长度固定的数组来实现，数组头部就是队首（head），数组的尾部就是队尾（tail），数组[head…tail)时循环队列的有效元素
head永远指向循环队列的第一个元素
tai永远指向循环队列有效元素的后一个位置

此时循环队列的有效元素就为7 9 1两个元素
循环队列出队一个元素，就只用让head引用向后移动一个位置

此时循环队列的有效元素就只有9 和 1 两个元素了
再出队一个元素，但此时head引用已经走到末尾了，所谓循环队列就是当head或者tail引用走到数组末尾时，再向后移动就是返回数组头部的操作，循环队列最大好处就是进行元素的删除的时候不需要进行数据的搬移操作，当有新的元素添加到队列中就会覆盖掉原来的元素，就只需要将tail索引位置覆盖上新的元素，再让tail再向后移动

当队列为空时,head == tail

当队列已“满”时，head == tail

循环队列需要注意的关键点
1.因此当head 和 tail相等时，没法区分此时循环队列已满，还是为空，因此在循环队列中，若(tail + 1) % n == head就认为循环队列已满

此时循环队列就已经满了，在循环队列中就会浪费一个空间，判断队列是否已满
2.head和tail的移动不能简单的 + 1，使用取模操作，取数组长度
tail = (tail + 1) % n
head = (head + 1) % n
对数组长度取模的本质：
当head和tai走到数组最后一个索引位置时，下一次要返回数组头部，就必须用 + 1对数组长度取模
3.head == tail时，认为队列为空

6.循环队列的操作

1.定义一个循环队列

//基于整形的循环队列public class LoopQueue implements Queue<integer> {
    //定长数组
    private Integer[] data;
    //指向队首元素
    int head;
    //指向队尾元素的下一个元素
    int tail;
    public LoopQueue(int size){
        data = new Integer[size + 1];
    }}</integer>

2.向循环队列中添加一个元素

@Override    public void offer(Integer val) {
       if (isFull()){
           throw new ArrayIndexOutOfBoundsException("loopQueue is full!cannot offer");
       }
       data[tail] = val;
       tail = (tail + 1) % data.length;
    }

3.从循环队列中出队一个元素

 @Override    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot poll!");
        }
        Integer val = data[head];
        head = (head + 1) % data.length;
        return val;
    }

4.查看当前循环队列队首元素

 @Override    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("loopQueue is empty!cannot peek!");
        }
        return data[head];
    }

5.判断当前循环队列是否为空

 @Override    public boolean isEmpty() {
        return head == tail;
    }

6.判断当前循环队列是否已满

 public boolean isFull(){
        return (tail + 1) % data.length == head;
    }

7.toString方法

public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        //最后一个有效元素的索引
        int lsatIndex = tail == 0 ? data.length - 1 : tail - 1;
        for (int i = head; i != tail;) {
            sb.append(data[i]);
            if (i != lsatIndex){
                sb.append(", ");
            }
            i = (i + 1) % data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }

---

7.双端队列

双端队列：Deque是Queue的子接口，这个队列既可以尾插，头出；也可以头插，尾出

双端队列的一个常用子类就是LinkedList，不管使用栈还是队列，都可以统一使用双端队列接口
1.现在需要一个栈

2.现在需要一个队列

推荐学习：《java视频教程》

以上是一文帶你認識Java棧和佇列的詳細內容。更多資訊請關注PHP中文網其他相關文章！