网站建设技术论坛,.net做网站实例 贴吧,wordpress 页面 自定义页面,怎么开微商城网店步骤文章目录232. 用栈实现队列补充知识——Deque232. 用栈实现队列
答案思路#xff1a;
在push数据的时候#xff0c;只要数据放进输入栈就好#xff0c;但在pop的时候#xff0c;操作就复杂一些#xff0c;输出栈如果为空#xff0c;就把进栈数据全部导入进来#xff0…
文章目录232. 用栈实现队列补充知识——Deque232. 用栈实现队列
答案思路
在push数据的时候只要数据放进输入栈就好但在pop的时候操作就复杂一些输出栈如果为空就把进栈数据全部导入进来注意是全部导入再从出栈弹出数据如果输出栈不为空则直接从出栈弹出数据就可以了。
如果进栈和出栈都为空的话说明模拟的队列为空了。
class MyQueue {DequeInteger inStack;DequeInteger outStack;public MyQueue() {inStacknew LinkedListInteger();outStacknew LinkedListInteger();}public void push(int x) {inStack.push(x);}public int pop() {if(outStack.isEmpty()){popInStack();}return outStack.pop();}public int peek() {if(outStack.isEmpty()){popInStack();}return outStack.peek();}public boolean empty() {return inStack.isEmpty()outStack.isEmpty();}public void popInStack(){while(!inStack.isEmpty()){outStack.push(inStack.pop());}}
}补充知识——Deque
定义 双向队列支持插入删除元素的线性集合。 java官方文档推荐用deque实现栈stack。
和Queue的区别 Deque是double ended queue将其理解成双端结束的队列双端队列可以在首尾插入或删除元素。 Queue的解释中Queue就是简单的FIFO队列。 所以在概念上来说Queue是FIFO的单端队列Deque是双端队列。
特点 1.插入、删除、获取操作支持两种形式快速失败和返回null或true/false 2.既具有FIFO特点又具有LIFO特点即是队列又是栈 3.不推荐插入null元素null作为特定返回值表示队列为空 4.未定义基于元素相等的equals和hashCode
方法
addFirst(): 向队头插入元素如果元素为空则发生NPE(空指针异常)addLast(): 向队尾插入元素如果为空则发生NPEofferFirst(): 向队头插入元素如果插入成功返回true否则返回falseofferLast(): 向队尾插入元素如果插入成功返回true否则返回falseremoveFirst(): 返回并移除队头元素如果该元素是null则发生NoSuchElementExceptionremoveLast(): 返回并移除队尾元素如果该元素是null则发生NoSuchElementExceptionpollFirst(): 返回并移除队头元素如果队列无元素则返回nullpollLast(): 返回并移除队尾元素如果队列无元素则返回nullgetFirst(): 获取队头元素但不移除如果队列无元素则发生NoSuchElementExceptiongetLast(): 获取队尾元素但不移除如果队列无元素则发生NoSuchElementExceptionpeekFirst(): 获取队头元素但不移除如果队列无元素则返回nullpeekLast(): 获取队尾元素但不移除如果队列无元素则返回nullpop(): 弹出栈中元素也就是返回并移除队头元素等价于removeFirst()如果队列无元素则发生NoSuchElementExceptionpush(): 向栈中压入元素也就是向队头增加元素等价于addFirst()如果元素为null则发生NPE如果栈空间受到限制则发生IllegalStateException
实现 ArrayDeque: 基于数组实现的线性双向队列通常作为栈或队列使用但是栈的效率不如LinkedList高。 LinkedList: 基于链表实现的链式双向队列通常作为栈或队列使用但是队列的效率不如ArrayQueue高。
private static void usingAsQueue() {DequeInteger queuenew ArrayDeque();System.out.println(队列为空:queue.isEmpty()); //判断队列是否为空queue.addLast(12); //添加元素System.out.println(队列为空:queue.isEmpty()); //判断队列是否为空System.out.println(queue.peekFirst()); //获取队列首部元素System.out.println(queue.pollFirst()); //获取并移除栈顶元素System.out.println(队列为空:queue.isEmpty()); //判断队列是否为空}private static void usingAsStack() {//作为栈使用DequeInteger stacknew LinkedList();System.out.println(栈为空:stack.isEmpty()); //判断栈是否为空stack.addFirst(12);System.out.println(栈为空:stack.isEmpty()); //判断栈是否为空System.out.println(stack.peekFirst()); //获取栈顶元素System.out.println(stack.pollFirst()); //获取并移除栈顶元素System.out.println(栈为空:stack.isEmpty()); //判断栈是否为空System.out.println();
