Java 棧和隊列的交互實現(xiàn)

更新時間：2023年12月21日 11:22:15 作者：愛吃南瓜的北瓜

棧和隊列都是常用的數(shù)據(jù)結(jié)構(gòu),本文就來介紹一下Java 棧和隊列的交互實現(xiàn),主要包括隊列模擬實現(xiàn)棧及棧模擬實現(xiàn)隊列,具有一定的參考價值,感興趣的可以了解一下

隊列和棧的區(qū)別

棧和隊列都是常用的數(shù)據(jù)結(jié)構(gòu)，它們的主要區(qū)別在于數(shù)據(jù)的插入和刪除順序。

棧 (Stack) 是一種后進先出 (Last-In-First-Out, LIFO) 的數(shù)據(jù)結(jié)構(gòu)，只允許在一端進行插入和刪除操作，這一端稱為棧頂。新元素插入后成為新的棧頂，而刪除時也只能刪除棧頂元素。

隊列 (Queue) 是一種先進先出 (First-In-First-Out, FIFO) 的數(shù)據(jù)結(jié)構(gòu)，允許在兩端進行插入和刪除操作，插入在隊尾，刪除在隊頭。新元素插入時成為新的隊尾，而刪除時也只能刪除隊頭元素。

一.用隊列模擬實現(xiàn)棧

1.void push(int x) 將元素 x 壓入棧頂。
2.int pop() 移除并返回棧頂元素。
3.int top() 返回棧頂元素。
4.boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。

如上便是需要用隊列來實現(xiàn)棧的四個基本操作。
我們試想，實現(xiàn)這些棧的操作，一個隊列可以完成嗎？
顯然不可以，我們使用兩個隊列來實現(xiàn)棧的模擬

在這里插入圖片描述

大體流程
1.入棧時：
如果兩個都為空，那么想

1.1入棧

當(dāng)我們要放入18 25 35 48 這一串?dāng)?shù)字入棧時，先放入18 25 35（放入時選擇的隊列是不為空的隊列），模擬入隊以及入棧時的狀況，如下圖

在這里插入圖片描述

 public void push(int x) {
        if(empty()){
            queue1.offer(x);
            return;
        }
        if(!queue1.isEmpty()){
            queue1.offer(x);
        }else {
            queue2.offer(x);
        }
    }

1.2出棧

此時如果我們要將35出棧時，又該如何操作呢？此時我們就需要用到第二個隊列，將隊列一的前size－1個元素（也就是18 25)從隊列一中出隊，放入隊列二中。此時隊列一中的元素為35，隊列二的元素為18 25 如下圖。

在這里插入圖片描述

當(dāng)初棧完成時，我們此時要將48入棧時，又該放入哪個棧中呢？我們考慮棧的特點（先入后出），我們將再入棧的元素放到不為空的隊列中。

在這里插入圖片描述

 public int pop() {
        if(empty()){
            return -1;
        }
        if(!queue1.isEmpty()){
            int size = queue1.size();
            for (int i = 0; i < size-1; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }else {
            int size = queue2.size();
            for (int i = 0; i < size-1; i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }

1.3返回棧頂元素

在實現(xiàn)pop的基礎(chǔ)上，我們將聲明一個變量temp來儲存每次要移除的元素。

  public int top() {
        if(empty()){
            return -1;
        }
        if (!queue1.isEmpty()){
            int temp = -1;
            int size = queue1.size();
            for (int i = 0; i < size; i++) {
                temp = queue1.poll();
                queue2.offer(temp);
            }
            return temp;
        }else {
            int size = queue2.size();
            int temp = -1;
            for (int i = 0; i < size; i++) {
                temp = queue2.poll();
                queue1.offer(temp);
            }
            return temp;
        }
    }

1.4判斷棧是否為空

當(dāng)隊列一和隊列二都為空時，此時棧就為空。

public boolean empty() {
        return queue1.isEmpty()&&queue2.isEmpty();
    }

二.用棧模擬實現(xiàn)隊列

我們也是用兩個棧來模擬實現(xiàn)隊列

2.1 入隊

我們將所有入隊的元素都放入棧一中，如下圖

在這里插入圖片描述

public void push(int x) {
          stack1.push(x);
    }

2.2出隊

要出棧時，如果棧二不為空，就出棧二中的元素，如果棧二為空，將棧一中的所有元素一次性的全部push到棧二中，此時就將入棧的元素全部倒轉(zhuǎn)過來了,(例如入棧時在棧中的入棧順序依次排序為18 25 35，棧二中此時的元素入棧順序是35 25 18，出棧時就先出18,就完成了轉(zhuǎn)換）如下圖

在這里插入圖片描述

 public int pop() {
           if(empty()){
               return -1;
           }
           if (stack2.isEmpty()){
               while (!stack1.isEmpty()){
                   stack2.push(stack1.pop());
               }
           }
           return stack2.pop();
    }

2.3peek

peek只是將出隊時的pop換成peek，就可以完成要求。

public int peek() {
        if(empty()){
            return -1;
        }
        if (stack2.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

2.4判斷隊列是否為空

如果棧一和棧二都為空時，那么隊列就為空。

 public boolean empty() {
          return stack1.isEmpty() && stack2.isEmpty();
    }

三.完整代碼

3.1 隊列模擬實現(xiàn)棧

class MyStack {

    Queue<Integer> queue1 ;
    Queue<Integer> queue2 ;
    public MyStack() {
         queue1 = new LinkedList<>();
         queue2 = new LinkedList<>();
    }
    public void push(int x) {
        if(empty()){
            queue1.offer(x);
            return;
        }
        if(!queue1.isEmpty()){
            queue1.offer(x);
        }else {
            queue2.offer(x);
        }
    }

    public int pop() {
        if(empty()){
            return -1;
        }
        if(!queue1.isEmpty()){
            int size = queue1.size();
            for (int i = 0; i < size-1; i++) {
                queue2.offer(queue1.poll());
            }
            return queue1.poll();
        }else {
            int size = queue2.size();
            for (int i = 0; i < size-1; i++) {
                queue1.offer(queue2.poll());
            }
            return queue2.poll();
        }
    }

    public int top() {
        if(empty()){
            return -1;
        }
        if (!queue1.isEmpty()){
            int temp = -1;
            int size = queue1.size();
            for (int i = 0; i < size; i++) {
                temp = queue1.poll();
                queue2.offer(temp);
            }
            return temp;
        }else {
            int size = queue2.size();
            int temp = -1;
            for (int i = 0; i < size; i++) {
                temp = queue2.poll();
                queue1.offer(temp);
            }
            return temp;
        }
    }

    public boolean empty() {
        return queue1.isEmpty()&&queue2.isEmpty();
    }
}

3.2棧模擬實現(xiàn)隊列

class MyQueue {
    public Stack<Integer> stack1 ;
    public Stack<Integer> stack2;
    public MyQueue() {
     stack1 = new Stack<>();
     stack2 = new Stack<>();
    }

    public void push(int x) {
          stack1.push(x);
    }

    public int pop() {
           if(empty()){
               return -1;
           }
           if (stack2.isEmpty()){
               while (!stack1.isEmpty()){
                   stack2.push(stack1.pop());
               }
           }
           return stack2.pop();
    }

    public int peek() {
        if(empty()){
            return -1;
        }
        if (stack2.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
          return stack1.isEmpty() && stack2.isEmpty();
    }
}

到此這篇關(guān)于Java 棧和隊列的交互實現(xiàn)的文章就介紹到這了,更多相關(guān)Java 棧和隊列交互內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: