基础数据结构--栈和队列的练习算法-数据结构栈队列

1、如何用栈结构实现队列结构首先，用一个栈肯定是实现不了的。所以，考虑两个栈来实现。一个是push栈、一个是pop栈。
放数据的时候往push栈放，当取数据的时候，将数据全部倒到pop栈，再从pop栈取数据。
注意：

（1）倒数据的时候要一次性倒完
（2）如果pop栈没有拿完，不能倒数据

详细代码：

package basic.stackqueue; import java.util.Stack; /** * 使用栈结构实现队列结构的功能 * * @author 周一 */ public class TwoStacksImplementQueue {/** * 使用两个栈来实现队列结构 */ public static class TwoStackQueue { // 用于存放添加数据的栈 public Stack stackPush; // 用于存放获取数据的栈 public Stack stackPop; public TwoStackQueue() { stackPush = new Stack<>(); stackPop = new Stack<>(); }/** * 倒数据 */ private void pushToPop() { // pop为空才倒数据 if (stackPop.empty()) { // push有数据可倒，并且一次性倒完 while (!stackPush.empty()) { stackPop.push(stackPush.pop()); } } }/** * 添加数据都往stackPush栈放 */ public void add(T data) { stackPush.push(data); }public T poll() { if (stackPush.empty() && stackPop.empty()) { throw new RuntimeException("Queue is empty"); } // 拿数据前先执行倒数据方法 pushToPop(); // 拿数据都从stackPop栈拿 return stackPop.pop(); }public T peek() { if (stackPush.empty() && stackPop.empty()) { throw new RuntimeException("Queue is empty"); } pushToPop(); return stackPop.peek(); }}public static void main(String[] args) { TwoStackQueue test = new TwoStackQueue<>(); test.add(1); test.add(4); test.add(3); test.add(2); System.out.println(test.peek()); System.out.println(test.poll()); System.out.println(test.peek()); System.out.println(test.poll()); System.out.println(test.peek()); System.out.println(test.poll()); System.out.println(test.peek()); System.out.println(test.poll()); }}

2、如何用队列结构实现栈结构同理，想用一个队列来实现，是不行的。所以，考虑两个队列来实现。
注意：

（1）加数据的时候，往当前存在数据的队列加；
（2）拿数据的时候，将所有数据移到空队列中，留下一个数返回即可。

【基础数据结构--栈和队列的练习】详细代码：

package basic.stackqueue; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /** * 使用队列结构实现栈结构 * * @author 周一 */ public class TwoQueuesImplementStack {/** * 两个队列实现栈结构 */ public static class TwoQueueStack { public Queue queue; public Queue help; public TwoQueueStack() { queue = new LinkedList<>(); help = new LinkedList<>(); }public void push(T data) { queue.offer(data); }public T poll() { while (queue.size() > 1) { // 将queue中数据倒入help中，留下一个 help.offer(queue.poll()); } // 将queue中剩下的一个数据取出后返回 T res = queue.poll(); // 交换queue和help的引用 // 这样就不用判断当前哪个队列存在数据，每次都是从queue倒到help，取数据、交换引用，取后又是queue队列存放数据 // 下次拿就直接从queue中拿，大大减少代码复杂程度 Queue tmp = queue; queue = help; help = tmp; return res; }public T peek() { while (queue.size() > 1) { // 将queue中数据倒入help中，留下一个 help.offer(queue.poll()); } // 将queue中剩下的一个数据取出后返回 T res = queue.poll(); // 由于是peek，所以将最后这一个数放到help队列中 help.offer(res); // 交换queue和help的引用 Queue tmp = queue; queue = help; help = tmp; return res; }public boolean isEmpty() { return queue.isEmpty(); }}public static void main(String[] args) { System.out.println("test begin"); TwoQueueStack myStack = new TwoQueueStack<>(); Stack stack = new Stack<>(); int testTime = 100000; int maxValue = https://www.it610.com/article/100000; for (int i = 0; i < testTime; i++) { if (myStack.isEmpty()) { if (!stack.isEmpty()) { System.out.println("error"); } int value = https://www.it610.com/article/(int) ((maxValue + 1) * Math.random()); myStack.push(value); stack.push(value); } else { if (Math.random() < 0.25) { int value = (int) ((maxValue + 1) * Math.random()); myStack.push(value); stack.push(value); } else if (Math.random() < 0.5) { if (!myStack.peek().equals(stack.peek())) { System.out.println("error"); } } else if (Math.random() < 0.75) { if (!myStack.poll().equals(stack.pop())) { System.out.println("error"); } } else { if (myStack.isEmpty() != stack.isEmpty()) { System.out.println("error"); } } } } System.out.println("test end"); }}