剑指offer面试题7 用俩个栈实现队列

发布时间:2024年01月21日

考察点

栈,队列

知识点

栈是先进后出的数据结构,队列是先进先出的结构。这俩个数据结构其实可以看作是特殊的
数组,数组可以在任何一个位置存取元素,而栈相当于只能通过要么左边一端要么右边一端存取
元素的数组,队列相当于只能通过左边一端存元素右边一端取元素,或者左边一端取元素右边一端存元素的数组。有了这层物理限制,就可以很好的理解"先进后出"以及"先进先出"的含义了
java语言中队列接口Queue定义了4个方法:
int size()//取大小
boolean add(T)boolean offer(T)//添加元素到队尾
T remove()/T pool()//获取对首元素并且删除
T element()/T peek()//获取对首元素不删除
其中前面的添加/删除/获取元素失败会抛出异常,后面的则是返回falsenull
java语言中实现Queue接口的类有很多,常见的比如LinkedList:
Queue<int> q = new LinkedList<>();
java语言中栈是通过Deque接口来实现的,Deque接口本身实现的是一个双端队列(就是俩边
可以同时存取元素的队列),由于历史原因java语言本身没有提供Stack的接口。Deque接口
关于栈定义了3个方法:
boolean push(T)//添加元素
T pop()//获取栈顶元素并弹出
T peek()//获取栈顶元素

题目

分析
这种题目只能是通过举例子的方式摸索出可能的解法,然后总结出步骤,用语言实现即可。回归到数据结构的特性,考的无非就是队列先进先出,栈先进后出的特点,我们举例子假设元素以a,b,c顺序入栈1,按照栈的逻辑出的元素顺序应该是c,b,a,要想以a,b,c的顺序出栈,只能先把最先出去的元素存起来,题目中刚好给了2个栈,也就是说我们以c,b,a的元素顺序存到了栈2,这个时候栈2出的元素顺序就刚好满足我们的诉求了。假设这个时候又新增了d,e2个元素,它们肯定是在a,b,c的后面,所以直接入栈1就可以了。总结出来的步骤就是如果入栈直接入栈1,如果出栈直接出栈2,要是栈2是空的则把栈1的元素弹出压进去

import java.util.Deque;
import java.util.LinkedList;

public class MockQueue {
	private Deque stack1;
	private Deque stack2;

	public MockQueue() {
		stack1 = new LinkedList<>();
		stack2 = new LinkedList<>();
	}
	public void appendTail(int val) {
		stack1.push(val);
	}
	public int deleteHead() {
		if (stack2.size() <= 0 && stack1.size() <= 0) {
			throw new Error("queue empty");
		}
		if (stack2.size() > 0) {
			int ret = (int) stack2.peek();
			stack2.pop();
			return ret;
		}
		while (stack1.size() > 0) {
			stack2.push(stack1.peek());
			stack1.pop();
		}
		int ret = (int) stack2.peek();
		stack2.pop();
		return ret;
	}

}
public class Seven {
	public static void main(String[] args) {
		MockQueue queue = new MockQueue();
		try {
			queue.deleteHead();
		} catch (Throwable e) {
			System.out.println(e);
		}
		queue.appendTail(1);
		queue.appendTail(2);
		queue.appendTail(3);
		queue.appendTail(4);
		System.out.println(queue.deleteHead());
		System.out.println(queue.deleteHead());
		queue.appendTail(5);
		queue.appendTail(6);
		System.out.println(queue.deleteHead());
		System.out.println(queue.deleteHead());
	}
}
文章来源:https://blog.csdn.net/wellwang1993/article/details/135734446
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。