用两个栈实现一个队列java实现

栈(Stack)和队列(Queue)是常用的数据结构，在日常开发中使用频率很高。但是，有时候我们需要用栈来实现队列，或用队列实现栈。今天我们来探讨一下如何使用两个栈来实现一个队列。这里我们使用Java来实现，先讲原理再说具体实现。

1、栈和队列的概念

- 栈(Stack)是一种线性数据结构，具有先进后出（Last In First Out）的特点，添加和删除元素只能在栈顶进行。

- 队列(Queue)是一种线性数据结构，具有先进先出（First In First Out）的特点，添加和删除元素在队列的两端进行。

2、用两个栈实现队列的原理

在队列中，元素的入队和出队是有顺序的。如果我们直接使用一个栈去实现队列，那么出队时将会存在一个问题，因为栈的特性是先进后出，所以出队时无法保证出队的元素是最先入队的元素。而使用两个栈时，我们可以借助第二个栈先“倒序”存储元素，再逐个出栈，就能实现队列的先入先出的特点了。

具体来说，实现方法如下：

两个栈分别为stackPush和stackPop，stackPush用于入队操作，stackPop用于出队操作。

- 当需要执行入队操作时，只需要将元素压入stackPush栈即可。

- 当需要执行出队操作时，如果stackPop不为空，那么直接从stackPop中弹出栈顶元素；如果stackPop为空，那么将stackPush中的元素逐个压入stackPop中，然后再弹出栈顶元素。

3、Java实现代码

以下是使用两个栈实现队列的Java代码。

```java

import java.util.Stack;

public class queueWithStack {

private Stack stackPush;

private Stack stackPop;

public queueWithStack(){

stackPush = new Stack<>();

stackPop = new Stack<>();

}

public void push(int num){

stackPush.push(num);

}

public int pop(){

if(stackPop.empty() && stackPush.empty()){

throw new RuntimeException("Queue is empty");

} else if(stackPop.empty()){

while(!stackPush.empty()){

stackPop.push(stackPush.pop());

}

}

return stackPop.pop();

}

public int peek(){

if(stackPop.empty() && stackPush.empty()){

throw new RuntimeException("Queue is empty");

} else if(stackPop.empty()){

while(!stackPush.empty()){

stackPop.push(stackPush.pop());

}

}

return stackPop.peek();

}

public boolean empty(){

return stackPop.empty() && stackPush.empty();

}

}

```

4、测试代码

我们可以使用JUnit来测试我们的代码是否实现了队列的先入先出的特性。

```java

import org.junit.Before;

import org.junit.Test;

import static org.junit.Assert.*;

public class queueWithStackTest {

private queueWithStack queue;

@Before

public void setUp(){

queue = new queueWithStack();

}

@Test

public void testPush(){

queue.push(1);

queue.push(2);

queue.push(3);

assertEquals(queue.peek(), 1);

}

@Test

public void testPop(){

queue.push(1);

queue.push(2);

queue.push(3);

assertEquals(queue.pop(), 1);

assertEquals(queue.pop(), 2);

assertEquals(queue.pop(), 3);

}

@Test(expected = RuntimeException.class)

public void testEmpty(){

queue.peek();

}

}

```

5、总结

使用两个栈实现队列的思路非常巧妙，基本思路是通过两个栈分别实现队列的不同功能（入队和出队），然后把这两个栈结合起来。这种实现方式的时间复杂度与空间复杂度均为O(n)，因此效率较低。但是实际应用中，这种方法的优点是使用的数据结构简单，不需要使用Java集合框架。这样有利于提升代码的可读性和可维护性。

在实际开发中，若遇到需要使用队列来保存一些数据信息时，可以考虑使用该数据结构，对于一些数据的流向要求相对明确的情况下，可采用此方法，不仅可以解决问题，同时也可以拓展自己的思维模式。