Java 棧和隊(duì)列的交互實(shí)現(xiàn)

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

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

隊(duì)列和棧的區(qū)別

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

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

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

一.用隊(duì)列模擬實(shí)現(xiàn)棧

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

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

在這里插入圖片描述

大體流程
1.入棧時(shí)：
如果兩個(gè)都為空，那么想

1.1入棧

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

在這里插入圖片描述

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

1.2出棧

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

在這里插入圖片描述

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

在這里插入圖片描述

 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返回棧頂元素

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

  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)隊(duì)列一和隊(duì)列二都為空時(shí)，此時(shí)棧就為空。

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

二.用棧模擬實(shí)現(xiàn)隊(duì)列

我們也是用兩個(gè)棧來模擬實(shí)現(xiàn)隊(duì)列

2.1 入隊(duì)

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

在這里插入圖片描述

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

2.2出隊(duì)

要出棧時(shí)，如果棧二不為空，就出棧二中的元素，如果棧二為空，將棧一中的所有元素一次性的全部push到棧二中，此時(shí)就將入棧的元素全部倒轉(zhuǎn)過來了,(例如入棧時(shí)在棧中的入棧順序依次排序?yàn)?8 25 35，棧二中此時(shí)的元素入棧順序是35 25 18，出棧時(shí)就先出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只是將出隊(duì)時(shí)的pop換成peek，就可以完成要求。

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

2.4判斷隊(duì)列是否為空

如果棧一和棧二都為空時(shí)，那么隊(duì)列就為空。

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

三.完整代碼

3.1 隊(duì)列模擬實(shí)現(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棧模擬實(shí)現(xiàn)隊(duì)列

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 棧和隊(duì)列的交互實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java 棧和隊(duì)列交互內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: