使用队列实现堆栈

可以使用两个队列来实现Java堆栈。让要实现的堆栈为“s”，用于实现的队列为“q1”和“q2”。Stack 's' 可以通过两种方式实现：

方法1：通过使 push 操作代价高昂

该方法确保新进入的元素始终位于 'q1' 的前面，因此 pop 操作只是从 'q1' 出列。'q2' 用于将每个新元素放在 'q1' 的前面。

1.push(s, x)操作的步骤描述如下：

将 x 排入队列 q2

从 q1 逐一出列并入队到 q2。

交换 q1 和 q2 的名称

2.pop(s)操作的功能描述如下：

从 q1 中取出一个项目并返回它。

下面是上述方法的实现：

/* Java Program to implement a stack using
two queue */
import java.util.*;
class GfG {
	static class Stack {
		// Two inbuilt queues
		static Queue<Integer> q1 = new LinkedList<Integer>();
		static Queue<Integer> q2 = new LinkedList<Integer>();
		// To maintain current number of
		// elements
		static int curr_size;
		Stack()
		{
			curr_size = 0;
		}
		static void push(int x)
		{
			curr_size++;
			// Push x first in empty q2
			q2.add(x);
			// Push all the remaining
			// elements in q1 to q2.
			while (!q1.isEmpty()) {
				q2.add(q1.peek());
				q1.remove();
			}
			// swap the names of two queues
			Queue<Integer> q = q1;
			q1 = q2;
			q2 = q;
		}
		static void pop()
		{
			// if no elements are there in q1
			if (q1.isEmpty())
				return;
			q1.remove();
			curr_size--;
		}
		static int top()
		{
			if (q1.isEmpty())
				return -1;
			return q1.peek();
		}
		static int size()
		{
			return curr_size;
		}
	}
	// driver code
	public static void main(String[] args)
	{
		Stack s = new Stack();
		s.push(1);
		s.push(2);
		s.push(3);
		System.out.println("current size: " + s.size());
		System.out.println(s.top());
		s.pop();
		System.out.println(s.top());
		s.pop();
		System.out.println(s.top());
		System.out.println("current size: " + s.size());
	}
}
// This code is contributed by Prerna

输出

当前尺寸：3
3
2
1
当前尺寸：1

方法2：通过使pop操作成本高

在push操作中，新元素总是排队到q1。在 pop() 操作中，如果 q2 为空，则除了最后一个元素之外的所有元素都被移动到 q2。最后最后一个元素从 q1 出列并返回。

1.push(s, x)操作：

将 x 排入队列 q1(假设 q1 的大小是无限的)。

2.弹出操作：

除了从 q1 到 q2 的最后一个元素，一个接一个地从队列中取出所有元素。

将q1的最后一项出队，出队的项就是result，存储起来。

交换 q1 和 q2 的名称

返回步骤 2 中存储的项目。

/* Java Program to implement a stack
using two queue */
import java.util.*;
class Stack {
	Queue<Integer> q1 = new LinkedList<>(), q2 = new LinkedList<>();
	int curr_size;
	public Stack()
	{
		curr_size = 0;
	}
	void remove()
	{
		if (q1.isEmpty())
			return;
		// Leave one element in q1 and
		// push others in q2.
		while (q1.size() != 1) {
			q2.add(q1.peek());
			q1.remove();
		}
		// Pop the only left element
		// from q1
		q1.remove();
		curr_size--;
		// swap the names of two queues
		Queue<Integer> q = q1;
		q1 = q2;
		q2 = q;
	}
	void add(int x)
	{
		q1.add(x);
		curr_size++;
	}
	int top()
	{
		if (q1.isEmpty())
			return -1;
		while (q1.size() != 1) {
			q2.add(q1.peek());
			q1.remove();
		}
		// last pushed element
		int temp = q1.peek();
		// to empty the auxiliary queue after
		// last operation
		q1.remove();
		// push last element to q2
		q2.add(temp);
		// swap the two queues names
		Queue<Integer> q = q1;
		q1 = q2;
		q2 = q;
		return temp;
	}
	int size()
	{
		return curr_size;
	}
	// Driver code
	public static void main(String[] args)
	{
		Stack s = new Stack();
		s.add(1);
		s.add(2);
		s.add(3);
		s.add(4);
		System.out.println("current size: " + s.size());
		System.out.println(s.top());
		s.remove();
		System.out.println(s.top());
		s.remove();
		System.out.println(s.top());
		System.out.println("current size: " + s.size());
	}
}
// This code is contributed by Princi Singh

输出

当前尺寸：4
4
3
2
当前尺寸：2

以上就是关于“使用队列实现堆栈”的介绍，大家如果想了解更多相关知识，不妨来关注一下赢咖4的Java队列教程，里面有更丰富的知识等着大家去学习，相信对大家会有很大帮助的。