7 月12日学习打卡--栈和队列的相互转换
hello大家好呀，本博客目的在于记录暑假学习打卡，后续会整理成一个专栏，主要打算在暑假学习完数据结构，因此会发一些相关的数据结构实现的博客和一些刷的题，个人学习使用，也希望大家多多支持，有不足之处也请指出，谢谢大家。
前言
为了更深入理解栈和队列，本篇博客我将介绍力扣上两道栈和队列的转化问题。
一，力扣225，用队列实现栈
我们知道栈的特点是先进后出，队列是先进先出，因此，我们需要两个队列才能实现一个栈，通过队列中元素的转移来获取我们想要删除的元素，下面逐一介绍各个方法
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，用栈实现队列
思路：和上面类似，不过这里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();
*/好了，今天练车耽误了一下，今天就到这里吧，谢谢大家
原文地址：https://blog.csdn.net/2302_81982408/article/details/140389412
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！