如何仅用队列结构实现栈结构?
/*
* 队列结构实现栈
* 两个队列,一个主队列,一个辅助队列
* 从压栈开始操作,主队列压栈,弹出时,需要判断主队列是否为空,如果为空,抛出异常,然后判断主队列长度,
* 如果主队列长度为一,直接弹出,否则将主队列除最后一个元素外的所有元素全部压入辅助队列,主队列和辅助队列交换,
* 然后弹出主队列留的最后一个元素,即为栈所要弹出的元素。查询操作,判断主队列是否为空,
* 如果不为空,判断主队列长度是否等于一,如果不等于一,将主队列除最后一个元素外的所有元素全部压入辅助队列,
* 然后赋值给临时变量,然后再将最后一个元素压入辅助栈,交换主队列和辅助队列,返回临时变量。,
*/
import java.util.LinkedList; import java.util.Queue; public class QueuetoStack { public static class Mystack{ private Queuequeue1; private Queuequeue2; public Mystack(){ queue1 = new LinkedList(); queue2 = new LinkedList(); } public void push(int num) { queue1.add(num); } public int pop() { if(queue1.isEmpty()) { throw new RuntimeException("empty"); } while(queue1.size() > 1) { queue2.add(queue1.poll()); } int res= queue1.poll(); swap(); return res; } public int peek(){ if(queue1.isEmpty()){ throw new RuntimeException("the stack is empty!"); } //队列1的数全部压进队列2 while(queue1.size()!=1){ queue2.add(queue1.poll()); } int res = queue1.poll(); queue2.add(res); swap(); return res; } private void swap() { // TODO Auto-generated method stub Queuequeue = queue1; queue1 = queue2; queue2 = queue; } public boolean isEmpty(){ return queue1.isEmpty(); } } public static void main(String[] args) { Mystack myStack1 = new Mystack(); myStack1.push(3); myStack1.push(6); myStack1.push(9); System.out.println("===="+myStack1.peek()+"===="); while(!myStack1.isEmpty()){ System.out.println("===="+myStack1.peek()+"===="); System.out.println(myStack1.pop()); } } }
如何仅用栈结构实现队列结构?
/*
* 栈结构实现队列
* 两个栈,一个主栈,一个辅助栈
* 压入元素:主栈压入元素;弹出操作:判断主栈是否为空,如果主栈不空,将主栈所有元素全部压入辅助栈,弹出辅助栈的第一个元素,
* 然后判断辅助栈是否为空,若不为空,将辅助栈的所有元素再压回到主栈内;查询操作:判断主栈是否为空,如果主栈不空,
* 将主栈所有元素全部压入辅助栈,执行辅助栈的peek操作,然后判断辅助栈是否为空,若不为空,将辅助栈的所有元素再压回到主栈内;
*/
import java.util.Stack; public class StacktoQueue { public static class Myqueue{ private Stackstack1; private Stackstack2; public Myqueue(){ stack1 = new Stack(); stack2 = new Stack(); } public void push(int num) { stack1.push(num); } public int pull() { if(stack1.isEmpty()) { throw new RuntimeException("empty"); } while(!stack1.isEmpty()) { stack2.push(stack1.pop()); } int res = stack2.pop(); while(!stack2.isEmpty()){ stack1.push(stack2.pop()); } return res; } public int peek(){ if(stack1.isEmpty()){ throw new RuntimeException("the queue is empty!"); } while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } int res = stack2.peek(); while(!stack2.isEmpty()){ stack1.push(stack2.pop()); } return res; } public boolean isEmpty(){ return stack1.isEmpty(); } } public static void main(String[] args) { // TODO Auto-generated method stub Myqueue myQueue = new Myqueue(); myQueue.push(2); myQueue.push(4); myQueue.push(7); System.out.println("===="+myQueue.peek()+"===="); while(!myQueue.isEmpty()){ System.out.println("===="+myQueue.peek()+"===="); System.out.println(myQueue.pull()); } } }