1.仅用队列结构实现栈结构

1.1 分析：

1、所有数先入data队列：

2、将前n-1个数入help队列，弹出最后一个数：

3、将help中的前n-2个数入data队列，弹出最后一个数：

4、重复2~3，即可按先入后出的顺序弹出所有元素。

1.2 代码实现

package Solution;
import java.util.LinkedList;
import java.util.Queue;class queueToStack{Queue data;Queue help;public queueToStack() {this.data=new LinkedList();this.help=new LinkedList();}public void push(int num) {data.add(num);}public Integer peek() {if (data.isEmpty()) {throw new RuntimeException("Stack is empty!");}while(data.size()>1)help.add(data.poll());int result=data.poll();help.add(result);//只返回不删除swap();return result;}public Integer pop() {if (data.isEmpty()) {throw new RuntimeException("Stack is empty!");}while(data.size()>1)help.add(data.poll());int result=data.poll();//返回带删除swap();return result;}public boolean isEmpty() {return data.isEmpty();}public void swap() {//改变引用Queue temp=data;data=help;help=temp;}
}public class Queue_To_Stack {public static void main(String[] args) {queueToStack qts=new queueToStack();qts.push(1);qts.push(2);System.out.println(qts.pop());qts.push(3);System.out.println(qts.pop());System.out.println(qts.pop());qts.push(4);qts.push(5);System.out.println(qts.pop());}
}

运行结果：

注意：队列的先入先出！！！

2.仅用栈结构实现队列结构

2.1 分析

用两个栈：push栈，pop栈

• push栈：用于入队列
• pop栈：用于出队列

两种思想：

一种思想（倒的比较频繁）：

要入队列时，都往push栈加；

出队列时，将push栈中的数据倒入pop栈中，从pop栈顶弹出一个元素；然后将剩余数据倒回到push栈中。

另一种思想：

push往pop倒数据，需满足：

1. 要倒就把push中的数据倒空；
2. 在pop栈中还有数据时，就不能倒

2.2 代码实现

package Solution;import java.util.Stack;class StackToQueue{Stack pushStack;Stack popStack;public StackToQueue(){this.pushStack=new Stack();this.popStack=new Stack();}public void push(int num) {pushStack.push(num);}public Integer peek() {if (pushStack.isEmpty()) {throw new RuntimeException("Queue is empty!");}while(!pushStack.isEmpty())popStack.push(pushStack.pop());int result=popStack.peek();while(!popStack.isEmpty())pushStack.push(popStack.pop());return result;}public Integer poll() {if (pushStack.isEmpty()) {throw new RuntimeException("Queue is empty!");}while(!pushStack.isEmpty())popStack.push(pushStack.pop());int result=popStack.pop();//弹出，少一个while(!popStack.isEmpty())pushStack.push(popStack.pop());return result;}
}
public class Stack_To_Queue {public static void main(String[] args) {StackToQueue stq=new StackToQueue();stq.push(1);stq.push(2);System.out.println(stq.poll());stq.push(3);System.out.println(stq.poll());System.out.println(stq.poll());stq.push(4);stq.push(5);System.out.println(stq.poll());}
}

运行结果：

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！