Java 栈和队列的相互转换详解

网友投稿 254 2022-08-28


Java 栈和队列的相互转换详解

目录用栈实现队列—力扣232题用队列实现栈—力扣225题1. 双队列实现栈2.一个队列实现栈

栈和队列的本质是相同的,都只能在线性表的一端进行插入和删除。因此,栈和队列可以相互转换。

用栈实现队列—力扣232题

题目要求:仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作

使用双栈来实现队列,我们就可以让一个栈储存具体元素,另一个栈做辅助

上图可以看到,新元素进栈时,要确保该栈为空。进入栈的元素按顺序存到辅助栈中,等新元素进入栈之后,再将辅助栈中的元素按顺序出到该栈中。这样操作之后,栈中元素存放的顺序就和队列的一样啦

代码实现:

//双栈模拟队列

public class MyQueue{

//实际存储元素的栈

private Stack s1 = new Stack<>();

//辅助栈

private Stack s2 = new Stack<>();

public MyQueue() {

}

//将元素 x 推到队列的末尾

public void push(int x) {

if (s1.empty()){//栈为空,直接放入x

s1.push(x);

}else {

//此时不为空

//先把s1所有元素弹出放入s2

while (!s1.empty()){

http:// s2.push(s1.pop());//s2放入的值就是s2弹出的值

//以下两句和上一句相同

// int val = s1.pop();

// s2.push(val);

}

//将新元素直接放入s1,此时新元素就处在s1的栈顶

s1.push(x);

//再次将s2的所有值依次弹出放入http://s1

while (!s2.empty()){

s1.push(s2.pop());

}

}

}

//从队列的开头移除并返回元素

public int pop() {

return s1.pop();

}

//返回队列开头的元素

public int peek() {

returvdrXPDNknn s1.peek();

}

//判断队列是否为空

public boolean empty() {

return s1.empty();

}

}

用队列实现栈—力扣225题

题目要求:仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作

1. 双队列实现栈

使用双队列实现栈, q1是存储元素的队列,保证q2添加元素之后永远为空队列(新元素直接入q2),保证新元素处在队首。这样的话,新元素入队之后,另外一个队列的元素依次出队然后入队,这样就实现了一个栈。

代码实现:

public class MyStack {

//q1是存储元素的队列

private Queue q1 = new LinkedList<>();

//q2是辅助队列

//添加元素后保证q2永远为空

private Queue q2 = new LinkedList<>();

public MyStack () {

}

//将元素 x 压入栈顶

public void push(int x) {

//新入队元素直接入q2,成为q2队首

q2.offer(x);

//将q1中的所有元素依次出队,入q2

while (!q1.isEmpty()){

q2.offer(q1.poll());

}

//q1为空,q2为存储元素的队列,互换引用指向

//互换之后,q1任然是存储元素的队列,q2为空

Queue temp = q1;

q1 = q2;

q2 = temp;

}

// 移除并返回栈顶元素

public int pop() {

return q1.poll();

}

//返回栈顶元素

public int top() {

return q1.peek();

}

//判断栈是否为空

public boolean empty() {

return q1.isEmpty();

}

}

2.一个队列实现栈

先将元素入队,再将之前的元素依次出队再入队即可!也就是说,保证新元素在队首

代码实现:

public class MyStack {

private Queue queue = new LinkedList<>();

public MyStack() {

}

public void push(int x) {

//记录之前元素的个数

int size = quvdrXPDNkneue.size();

//将新元素入队

queue.offer(x);

//将之前的元素依次出队再入队,新元素就在队首位置

for (int i = 0; i < size; i++) {

queue.offer(queue.poll());

}

}

public int pop() {

return queue.poll();

}

public int top() {

return queue.peek();

}

public boolean empty() {

return queue.isEmpty();

}

}

这几个例题实践目的是更加熟悉的掌握和了解栈和队列,实际应用中是不推荐的哦。


版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:python之第三方HTTP库requests之文件上传
下一篇:python之处理selenium中的获取元素属性问题 || 处理selenium中的获取文本问题 || 处理selenium中的窗口切换问题 || 处理selenium中的鼠标悬停问题(python selenium循环判断元素是否存在)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~