Java 栈和队列
Word码鸭 人气:0栈和队列的本质是相同的，都只能在线性表的一端进行插入和删除。因此，栈和队列可以相互转换。
用栈实现队列—力扣232题
题目要求：仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作
使用双栈来实现队列，我们就可以让一个栈储存具体元素，另一个栈做辅助
上图可以看到，新元素进栈时，要确保该栈为空。进入栈的元素按顺序存到辅助栈中，等新元素进入栈之后，再将辅助栈中的元素按顺序出到该栈中。这样操作之后，栈中元素存放的顺序就和队列的一样啦
代码实现：
//双栈模拟队列
public class MyQueue{
//实际存储元素的栈
private Stack<Integer> s1 = new Stack<>();
//辅助栈
private Stack<Integer> s2 = new Stack<>();
public MyQueue() {
}
//将元素 x 推到队列的末尾
public void push(int x) {
if (s1.empty()){//栈为空，直接放入x
s1.push(x);
}else {
//此时不为空
//先把s1所有元素弹出放入s2
while (!s1.empty()){
s2.push(s1.pop());//s2放入的值就是s2弹出的值
//以下两句和上一句相同
// int val = s1.pop();
// s2.push(val);
}
//将新元素直接放入s1，此时新元素就处在s1的栈顶
s1.push(x);
//再次将s2的所有值依次弹出放入s1
while (!s2.empty()){
s1.push(s2.pop());
}
}
}
//从队列的开头移除并返回元素
public int pop() {
return s1.pop();
}
//返回队列开头的元素
public int peek() {
return s1.peek();
}
//判断队列是否为空
public boolean empty() {
return s1.empty();
}
}
用队列实现栈—力扣225题
题目要求：仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作
1. 双队列实现栈
使用双队列实现栈， q1是存储元素的队列，保证q2添加元素之后永远为空队列（新元素直接入q2），保证新元素处在队首。这样的话，新元素入队之后，另外一个队列的元素依次出队然后入队，这样就实现了一个栈。
代码实现：
public class MyStack {
//q1是存储元素的队列
private Queue<Integer> q1 = new LinkedList<>();
//q2是辅助队列
//添加元素后保证q2永远为空
private Queue<Integer> q2 = new LinkedList<>();
public MyStack () {
}
//将元素 x 压入栈顶
public void push(int x) {
//新入队元素直接入q2，成为q2队首
q2.offer(x);
//将q1中的所有元素依次出队，入q2
while (!q1.isEmpty()){
q2.offer(q1.poll());
}
//q1为空，q2为存储元素的队列，互换引用指向
//互换之后，q1任然是存储元素的队列，q2为空
Queue<Integer> temp = q1;
q1 = q2;
q2 = temp;
}
// 移除并返回栈顶元素
public int pop() {
return q1.poll();
}
//返回栈顶元素
public int top() {
return q1.peek();
}
//判断栈是否为空
public boolean empty() {
return q1.isEmpty();
}
}
2.一个队列实现栈
先将元素入队，再将之前的元素依次出队再入队即可！也就是说，保证新元素在队首
代码实现：
public class MyStack {
private Queue<Integer> queue = new LinkedList<>();
public MyStack() {
}
public void push(int x) {
//记录之前元素的个数
int size = queue.size();
//将新元素入队
queue.offer(x);
//将之前的元素依次出队再入队,新元素就在队首位置
for (int i = 0; i < size; i++) {
queue.offer(queue.poll());
}
}
public int pop() {
return queue.poll();
}
public int top() {
return queue.peek();
}
public boolean empty() {
return queue.isEmpty();
}
}
这几个例题实践目的是更加熟悉的掌握和了解栈和队列，实际应用中是不推荐的哦。
加载全部内容