hello大家好呀，本博客目的在于記錄暑假學習打卡，后續會整理成一個專欄，主要打算在暑假學習完數據結構，因此會發一些相關的數據結構實現的博客和一些刷的題，個人學習使用，也希望大家多多支持，有不足之處也請指出，謝謝大家。

前言

為了更深入理解棧和隊列，本篇博客我將介紹力扣上兩道棧和隊列的轉化問題。

一，力扣225，用隊列實現棧

. - 力扣（LeetCode）

我們知道棧的特點是先進后出，隊列是先進先出，因此，我們需要兩個隊列才能實現一個棧，通過隊列中元素的轉移來獲取我們想要刪除的元素，下面逐一介紹各個方法

1：push

根據后面的pop（）方法和我們需要實現棧的特性可知，我們每次需要在兩個隊列中非空的隊列中插入元素（插入元素肯定是插在一個隊列中），如果都為空，則指定一個隊列插入

public void push(int x) {if (!q2.isEmpty()) {q2.offer(x);} else if (!q1.isEmpty()) {q1.offer(x);} else {q1.offer(x);}

2.empty

我們先看empty，因為后面方法需要用到，顯然，兩個隊列均為空則模擬棧空

 public boolean empty() {return q1.isEmpty()&&q2.isEmpty();}

3.pop

pop方法我們的思路是如果哪個隊列不空，則把隊列中的size-1個元素移動到另一個隊列，剩下的便是不需要的數（雖然看起來代碼多但是else里的只需要把if里的改下就行）

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

4.empty

與pop類似，只是我們不需要刪除元素，而且需要一個整形紀錄棧頂元素

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

完整代碼

class MyStack {Queue<Integer> q1;Queue<Integer> q2;public MyStack() {q1=new LinkedList();q2=new LinkedList();}public void push(int x) {if (!q2.isEmpty()) {q2.offer(x);} else if (!q1.isEmpty()) {q1.offer(x);} else {q1.offer(x);}}public int pop() {if (empty()){return -1;}if(!q2.isEmpty()){int size=q2.size();for (int i = 0; i < size-1; i++) {q1.offer(q2.poll());}return q2.poll();}else {int size=q1.size();for (int i = 0; i < size-1; i++){q2.offer(q1.poll());}return q1.poll();}}public int top() {if (empty()){return -1;}if(!q2.isEmpty()){int size=q2.size();int val=0;for (int i = 0; i < size; i++) {val=q2.poll();q1.offer(val);}return val;}else {int size=q1.size();int val=0;for (int i = 0; i < size; i++) {val=q1.poll();q2.offer(val);}return val;}}public boolean empty() {return q1.isEmpty()&&q2.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

二,力扣232，用棧實現隊列

. - 力扣（LeetCode）

思路：和上面類似，不過這里push方法都是放到第一個棧，出隊操作分兩步：

1.判斷第二個棧是不是空的？如果是，則把第一個棧中所有元素都放到第二個棧里，取出第二個棧當中的棧頂元素。

2.如果不是空的，直接取出第二個棧中的棧頂元素

代碼：

class MyQueue {Stack<Integer> s1;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.isEmpty()) {int size = s1.size();for (int i = 0; i < size; i++) {s2.push(s1.pop());}return s2.pop();} else {return s2.pop();}}public int peek() {if (empty())return -1;if (s2.isEmpty()) {int size = s1.size();for (int i = 0; i < size; i++) {s2.push(s1.pop());}return s2.peek();} else {return s2.peek();}}public boolean empty() {return s1.isEmpty() && s2.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

好了，今天練車耽誤了一下，今天就到這里吧，謝謝大家