算法与数据结构——用栈实现队列的功能，用队列实现栈的功能

1、用栈实现队列的功能

思路 ：

队列的特点 FIFO栈的特点 FILO

用两个栈，一个做为入队栈，一个作为出队栈，每次出队，都从出队栈出，如果出队栈无数据，从入队栈出栈，再入出队栈

package com.lxd.leetcode.demo.stack; import java.util.Arrays; import java.util.Stack; /** * @ClassName StackImplQueue * @Description: 用栈实现队列功能 * @Author xiaod * @Date 2020/7/3 * @Version V1.0 **/ public class StackImplQueue { /*** * - 队列的特点 FIFO * - 栈的特点 FILO * * 用两个栈，一个做为入队栈，一个作为出队栈，每次出队，都从出队栈出，如果出队栈无数据，从入队栈出栈，再入出队栈 */ private static class QueueByStack<T>{ private Stack<T> inStack; private Stack<T> outStack; public QueueByStack(Stack inStack, Stack outStack){ this.inStack = inStack; this.outStack = outStack; } /** * 入队 * @param t */ public void push(T t){ inStack.push(t); } /*** * 获取队首元素并移除 * @return */ public T pop(){ if(!outStack.isEmpty()){ //出队栈有数据 return outStack.pop(); }else { //出队栈无数据，将入队栈数据出栈压入出队栈 while (!inStack.isEmpty()){ outStack.push(inStack.pop()); } return outStack.pop(); } } /*** * 获取队首元素 * @return */ public T peek(){ if(!outStack.isEmpty()){ //出队栈有数据 return outStack.peek(); }else { //出队栈无数据，将入队栈数据出栈压入出队栈 while (!inStack.isEmpty()){ outStack.push(inStack.pop()); } return outStack.peek(); } } } public static void main(String[] args) { Stack instack =new Stack(); Stack outstack =new Stack(); QueueByStack<Integer> queueByStack= new QueueByStack(instack,outstack); queueByStack.push(44); queueByStack.push(55); queueByStack.push(66); queueByStack.push(77); queueByStack.push(88); queueByStack.push(99); System.out.println( "queueByStack.peek()1 = " + queueByStack.peek()); System.out.println( "queueByStack.pop() = " + queueByStack.pop()); System.out.println( "queueByStack.peek()2 = " + queueByStack.peek()); } }

2、用队列实现栈的功能

思路：

准备两个队列，一个用作入栈出栈、一个用来在数据出栈时，临时存储出栈数据队列前面的数据，该数据出栈之后，再将队列数据依次入队。

/** * @ClassName QueueImplStack * @Description: 一用队列实现栈的功能 * @Author xiaod * @Date 2020/7/3 * @Version V1.0 **/ public class QueueImplStack { /*** * 准备两个队列，一个用作入栈出栈、一个用来在数据出栈时，临时存储出栈数据队列前面的数据，该数据出栈之后，再将队列数据依次入队。 */ private static class StackByQueue<T>{ /** * 操作出栈入栈的队列 */ private Queue<T> operationQueue; /** * 临时存储数据的队列 */ private Queue<T> tempQueue; public StackByQueue(Queue operationQueue, Queue tempQueue) { this.operationQueue = operationQueue; this.tempQueue = tempQueue; } /** * 入栈操作 * @param t */ public void push(T t){ operationQueue.add(t); } /** * 去除栈顶元素并移除 * @return */ public T pop(){ while (operationQueue.size()>1){ tempQueue.add(operationQueue.poll()); } T result = operationQueue.poll(); while (!tempQueue.isEmpty()){ operationQueue.add(tempQueue.poll()); } return result; } /** * 查看栈顶元素 * @return */ public T peek(){ while (operationQueue.size()>1){ tempQueue.add(operationQueue.poll()); } T result = operationQueue.poll(); while (!tempQueue.isEmpty()){ operationQueue.add(tempQueue.poll()); } operationQueue.add(result); return result; } } public static void main(String[] args) { Queue operationQueue =new LinkedList(); Queue tempQueue =new LinkedList(); StackByQueue<Integer> stackByQueue =new StackByQueue<>(operationQueue,tempQueue); stackByQueue.push(44); stackByQueue.push(55); stackByQueue.push(66); stackByQueue.push(77); stackByQueue.push(88); System.out.println( "stackByQueue.peek()1 = " + stackByQueue.peek()); System.out.println( "stackByQueue.pop() = " + stackByQueue.pop()); System.out.println( "stackByQueue.peek()2 = " + stackByQueue.peek()); } }