栈和队列栈和队列都是数据结构，作用是存储。每种数据结构都有其相应的特点。队列的特性是先进先出，栈的特性是先进后出：只有满足了以上特性，一个数据结构才能称为栈或队列。下面我们来看一下这两个经典的数据结构设计题：实现一个带栈的队列要实现一个带栈的队列，必须实现队列的如下API：voidpush(intx)//addelementsto队尾intpop()//删除队头元素并返回intpeek()//返回队首元素booleanempty()//判断队列是否为空我们需要使设计队列满足上述API的使用。一个队列有一个队列头和一个队列尾。所以我们可以使用两个栈，通过栈的特性让它们相互配合，实现一个队列：StackstackPush;//一个栈用于压入元素StackstackPop;//一个栈用来压栈元素Elementpopoff//InitializepublicMyQueue(){stackPush=newStack();stackPop=newStack();}push():push()所做的是在最后向队列中添加一个元素。所以这里我们可以直接调用栈的push()，然后将元素放入stackPush栈中：publicvoidpush(intx){stackPush.push(x);}此时元素1在stackPush栈底：pop():pop()是删除队列的头部元素并返回。有了刚才push()的经验，pop()依然可以沿用刚才push()的经验，即当stackPop为空时，pop()将stack中的元素按顺序一个一个Push，返回stackPop:thenReturntheelementsinstackPop()topop():publicintpop(){if(stackPop.isEmpty()&&stackPush.isEmpty()){thrownewRuntimeException("队列为空。");}else{if(stackPop.isEmpty()){while(!stackPush.isEmpty()){stackPop.push(stackPush.pop());}}}返回stackPop.pop();}peek()：peek是返回队列的头部元素：pop()和peek()有什么区别？即pop()返回队列的第一个元素，需要删除，但是peek()返回而不删除它。所以，就像pop()的思路一样，只需要在最后return的时候把stackPop.pop()换成stackPop.peek()，就大功告成了。publicintpeek(){if(stackPush.isEmpty()&&stackPop.isEmpty()){thrownewRuntimeException("队列为空。");}else{if(stackPop.isEmpty()){while(!stackPush.isEmpty()){stackPop.push(stackPush.pop());}}}返回stackPop.peek();}empty()：判断队列是否为空，为空则返回true，不为空则返回false。所以我们也可以直接判断两个栈是否同时为空。只要同时为空就返回true，同时不为空就返回false：publicbooleanempty(){returnstackPop.isEmpty()&&stackPush.isEmpty();主要用途是两个栈的相互协作。核心思想是将一段数据从一个栈的尾部移动到另一个栈，也就是队列的头部。那么我们来谈谈时间复杂度。当队列为空时，pop()和peek()都会通过while循环将元素从stackPush移动到stackPop，所以复杂度为O(n)。用队列实现栈，首先看一下栈的API：voidpush(intx)//将元素压入栈顶intpop()//取出并返回栈顶元素inttop()//返回栈顶元素booleanempty()//如果栈为空，则返回true；否则，返回假。与队列相同的API。只是这次我们是模拟一个队列实现一个栈。如果说用栈实现队列是一种相互协作的方式，那么用队列来实现栈就不一定了。我们可以使用ArrayDeque()来实现队列。队列<整数>队列；//使用ArrayDeque作为队列publicMyStack(){queue=newArrayDeque<>();}push(intx)：根据栈的特点，第一个入栈的元素会在栈底。所以在用队列模拟栈的时候，可以先把元素放入队列，然后一个一个的取出来，最后再入队，这样原本在队头的元素就去队尾，相当于栈头：//enter入栈时，新元素x入队后，新元素x之前的所有元素重新入队。此时元素x在队头publicvoidpush(intx){queue.offer(x);int大小=队列。尺寸（）;for(inti=0;i
