Java 栈与队列实战真题训练

Java 栈与队列实战真题训练

目录1、实现循环队列（1）数组下标实现循环（2）区分队列的满与空2、队列实现栈3、栈实现队列4、实现最小栈

1、实现循环队列

【OJ链接】

循环队列一般通过数组实现。我们需要解决几个问题。

（1）数组下标实现循环

a、下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length。通俗一点，就是如果我们的数组大小为8，下标走到了7，再往后如何回到0，我们可以（index+1）%8来实现。

b、下标最前再往前的时候，我们特殊判断一下，将其置为数组大小减一即可。

（2）区分队列的满与空

我们可以给数组预留一个位置，如果rear+1=front，则表示队列已满；如果rear=front，表示队列为空。这个情况下，我们需要考虑队列大小的问题，在定义数组大小时，需要比原有的大一。

【代码如下】

class MyCircularQueue {

public int front;

public int rear;

public int[] array;

//构造方法

public MyCircularQueue(int k) {

//因为预留位置的缘故，数组的大小要定义为k+1

this.array=new int[k+1];

}

//入队

public boolean enQueue(int value) {

if(isFull()){

return false;

}

this.array[this.rear]=value;

this.rear=(this.rear+1)%this.array.length;

return true;

}

//出队

public boolean deQueue() {

if(isEmpty()){

return false;

}

this.front=(this.front+1)%this.array.length;

return true;

}

//获取队头

public int Front() {

if(isEmpty()){

return -1;

}

return this.arhttp://ray[front];

}

//获取队尾

public int Rear() {

if(isEmpty()){

return -1;

}

int index=-1;

if(this.rear==0){

index=this.array.length-1;

}else{

index=this.rear-1;

}

return this.array[index];

}

//判断是否为空

public boolean isEmpty() {

if(this.front==this.rear){

return true;

}

return false;

}

//判断队列是否满

public boolean isFull() {

if((this.rear+1)%this.array.length==this.front){

return true;

}

return false;

}

}

2、队列实现栈

【OJ链接】

因为栈的先进后出、队列的先进先出原则。我们需要两个队列来实现栈。当两个队列都为空时，栈为空。

入栈（push）：第一次入栈无所谓，两个队列都为空，随便选择一个队列入队即可；后面入栈时，肯定会有一个队列不为空，找到不为空的队列，进行入队操作。出栈（pop）：首先栈为空时，不能进行出栈操作；栈不为空时，肯定有一个队列为空（queue1），一个队列不为空（queue2），将queue1中的size-1个元素出栈到queue2中（特别注意不能将求queue1大小的函数放进循环里，queue进行出队操作时，其大小是改变的），最后将queue1中最后一个元素进行出队最为返回值。获取栈顶元素（top）：和出栈差不多，就不细说了

【代码如下】

class MyStack {

private Queue queue1;

private Queue queue2;

//构造方法

public MyStack() {

queue1=new LinkedList<>();

queue2=new LinkedList<>();

}

//入栈

public void push(int x) {

if(!queue2.isEmpty()){

queue2.offer(x);

}else{

queue1.offer(x);

}

}

//出栈

public int pop() {

if(empty()){

return -1;

}

if(queue1.isEmpty()){

int size=queue2.size();

for(int i=0;i

int x=queue2.poll();

queue1.offer(x);

}

return queue2.poll();

}else{

int size=queue1.size();

for(int i=0;i

int x=queue1.poll();

queue2.offer(x);

}

return queue1.poll();

}

}

//获取栈顶元素

public int top() {

if(empty()){

return -1;

}

if(queue1.isEmpty()){

int x=-1;

int size=queue2.size();

for(int i=0;i

x=queue2.poll();

queue1.offer(x);

}

return x;

}else{

int size=queue1.size();

int x=-1;

for(int i=0;i

x=queue1.poll();

queue2.offer(x);

}

return x;

}

}

//判断栈是否为空

public boolean empty() {

if(queue1.isEmpty()&&queue2.isEmpty()){

return true;

}

return false;

}

}

3、栈实现队列

【OJ链接】

还是和上面一样，需要用到两个栈（stack1、stack2）。和实现栈列不同的是，入队只能对同一个栈进行操作。如果两个栈都为空，则队列为空。

入队（push）：规定stack1用来入队。每次入队时，对stack1进行入栈操作即可。出队（pop）：规定stack2进行出队操作。如果队列为空时，不能进行出队操作。当stack2为空时，我们需要将stack1中所有元素出栈，放入stack2中，然后对stack2进行出栈操作。如果stack2不为空，则直接对stack2进行出栈操作即可。获取队列开头元素（peek）：和出栈操作相同，最后只需要获取stack2的栈顶元素即可。

【代码如下】

class MyQueue {

private Stack stack1;

private Stack stack2;

//构造方法

public MyQueue() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入队操作

public void push(int x) {

stack1.push(x);

}

//出队操作

public int pop() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.pop();

}

//获取队列开头的元素

public int peek() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.peek();

}

//判断队列是否为空

public boolean empty() {

if(stack1.empty()&&stack2.empty()){

return true;

}

return false;

}

}

4、实现最小栈

【OJ链接】

其实就是要在O(1)的时间复杂度内找到栈的最小元素。需要两个栈来实现，一个栈来进行出栈、入栈操作。只需要保证不管如何操作，另一个栈的栈顶元素都是当前栈的最小元素即可。

两个栈stack1、stack2，站的操作都在stack1中：

入栈：如果第一次入栈，我们需要将其也放入stack2中，之后的入栈，将入栈元素与stack2的栈顶元素进行比较，如果其小于stack2的栈顶元素，则将其放入stack2中。出栈：对stack1出栈时，将其与stack2的栈顶元素进行比较，如果其等于stack2的栈顶元素，则对stack2进行出栈操作。

这样就能保证stack2的栈顶元素总是stack1的最小元素。注意：如果stack1中入栈两个相同的最小元素，都需要对stack2进行入栈。

【代码如下】

class MinStack {

private Stack stack1;

private Stack stack2;

//构造方法

public MinStack() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入栈

public void push(int val) {

stack1.push(val);

if(stack2.empty()){

stack2.push(val);

}else{

if(val<=stack2.peek()){

stack2.push(val);

}

}

}

//出栈

public void pop() {

int x=stack1.pop();

if(x==stack2.peek()){

stack2.pop();

}

}

//获取栈顶元素

public int top() {

return stack1.peek();

}

//获取栈的最小元素

public int getMin() {

return stack2.peek();

}

}

int x=queue2.poll();

queue1.offer(x);

}

return queue2.poll();

}else{

int size=queue1.size();

for(int i=0;i

int x=queue1.poll();

queue2.offer(x);

}

return queue1.poll();

}

}

//获取栈顶元素

public int top() {

if(empty()){

return -1;

}

if(queue1.isEmpty()){

int x=-1;

int size=queue2.size();

for(int i=0;i

x=queue2.poll();

queue1.offer(x);

}

return x;

}else{

int size=queue1.size();

int x=-1;

for(int i=0;i

x=queue1.poll();

queue2.offer(x);

}

return x;

}

}

//判断栈是否为空

public boolean empty() {

if(queue1.isEmpty()&&queue2.isEmpty()){

return true;

}

return false;

}

}

3、栈实现队列

【OJ链接】

还是和上面一样，需要用到两个栈（stack1、stack2）。和实现栈列不同的是，入队只能对同一个栈进行操作。如果两个栈都为空，则队列为空。

入队（push）：规定stack1用来入队。每次入队时，对stack1进行入栈操作即可。出队（pop）：规定stack2进行出队操作。如果队列为空时，不能进行出队操作。当stack2为空时，我们需要将stack1中所有元素出栈，放入stack2中，然后对stack2进行出栈操作。如果stack2不为空，则直接对stack2进行出栈操作即可。获取队列开头元素（peek）：和出栈操作相同，最后只需要获取stack2的栈顶元素即可。

【代码如下】

class MyQueue {

private Stack stack1;

private Stack stack2;

//构造方法

public MyQueue() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入队操作

public void push(int x) {

stack1.push(x);

}

//出队操作

public int pop() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.pop();

}

//获取队列开头的元素

public int peek() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.peek();

}

//判断队列是否为空

public boolean empty() {

if(stack1.empty()&&stack2.empty()){

return true;

}

return false;

}

}

4、实现最小栈

【OJ链接】

其实就是要在O(1)的时间复杂度内找到栈的最小元素。需要两个栈来实现，一个栈来进行出栈、入栈操作。只需要保证不管如何操作，另一个栈的栈顶元素都是当前栈的最小元素即可。

两个栈stack1、stack2，站的操作都在stack1中：

入栈：如果第一次入栈，我们需要将其也放入stack2中，之后的入栈，将入栈元素与stack2的栈顶元素进行比较，如果其小于stack2的栈顶元素，则将其放入stack2中。出栈：对stack1出栈时，将其与stack2的栈顶元素进行比较，如果其等于stack2的栈顶元素，则对stack2进行出栈操作。

这样就能保证stack2的栈顶元素总是stack1的最小元素。注意：如果stack1中入栈两个相同的最小元素，都需要对stack2进行入栈。

【代码如下】

class MinStack {

private Stack stack1;

private Stack stack2;

//构造方法

public MinStack() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入栈

public void push(int val) {

stack1.push(val);

if(stack2.empty()){

stack2.push(val);

}else{

if(val<=stack2.peek()){

stack2.push(val);

}

}

}

//出栈

public void pop() {

int x=stack1.pop();

if(x==stack2.peek()){

stack2.pop();

}

}

//获取栈顶元素

public int top() {

return stack1.peek();

}

//获取栈的最小元素

public int getMin() {

return stack2.peek();

}

}

int x=queue1.poll();

queue2.offer(x);

}

return queue1.poll();

}

}

//获取栈顶元素

public int top() {

if(empty()){

return -1;

}

if(queue1.isEmpty()){

int x=-1;

int size=queue2.size();

for(int i=0;i

x=queue2.poll();

queue1.offer(x);

}

return x;

}else{

int size=queue1.size();

int x=-1;

for(int i=0;i

x=queue1.poll();

queue2.offer(x);

}

return x;

}

}

//判断栈是否为空

public boolean empty() {

if(queue1.isEmpty()&&queue2.isEmpty()){

return true;

}

return false;

}

}

3、栈实现队列

【OJ链接】

还是和上面一样，需要用到两个栈（stack1、stack2）。和实现栈列不同的是，入队只能对同一个栈进行操作。如果两个栈都为空，则队列为空。

入队（push）：规定stack1用来入队。每次入队时，对stack1进行入栈操作即可。出队（pop）：规定stack2进行出队操作。如果队列为空时，不能进行出队操作。当stack2为空时，我们需要将stack1中所有元素出栈，放入stack2中，然后对stack2进行出栈操作。如果stack2不为空，则直接对stack2进行出栈操作即可。获取队列开头元素（peek）：和出栈操作相同，最后只需要获取stack2的栈顶元素即可。

【代码如下】

class MyQueue {

private Stack stack1;

private Stack stack2;

//构造方法

public MyQueue() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入队操作

public void push(int x) {

stack1.push(x);

}

//出队操作

public int pop() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.pop();

}

//获取队列开头的元素

public int peek() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.peek();

}

//判断队列是否为空

public boolean empty() {

if(stack1.empty()&&stack2.empty()){

return true;

}

return false;

}

}

4、实现最小栈

【OJ链接】

其实就是要在O(1)的时间复杂度内找到栈的最小元素。需要两个栈来实现，一个栈来进行出栈、入栈操作。只需要保证不管如何操作，另一个栈的栈顶元素都是当前栈的最小元素即可。

两个栈stack1、stack2，站的操作都在stack1中：

入栈：如果第一次入栈，我们需要将其也放入stack2中，之后的入栈，将入栈元素与stack2的栈顶元素进行比较，如果其小于stack2的栈顶元素，则将其放入stack2中。出栈：对stack1出栈时，将其与stack2的栈顶元素进行比较，如果其等于stack2的栈顶元素，则对stack2进行出栈操作。

这样就能保证stack2的栈顶元素总是stack1的最小元素。注意：如果stack1中入栈两个相同的最小元素，都需要对stack2进行入栈。

【代码如下】

class MinStack {

private Stack stack1;

private Stack stack2;

//构造方法

public MinStack() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入栈

public void push(int val) {

stack1.push(val);

if(stack2.empty()){

stack2.push(val);

}else{

if(val<=stack2.peek()){

stack2.push(val);

}

}

}

//出栈

public void pop() {

int x=stack1.pop();

if(x==stack2.peek()){

stack2.pop();

}

}

//获取栈顶元素

public int top() {

return stack1.peek();

}

//获取栈的最小元素

public int getMin() {

return stack2.peek();

}

}

x=queue2.poll();

queue1.offer(x);

}

return x;

}else{

int size=queue1.size();

int x=-1;

for(int i=0;i

x=queue1.poll();

queue2.offer(x);

}

return x;

}

}

//判断栈是否为空

public boolean empty() {

if(queue1.isEmpty()&&queue2.isEmpty()){

return true;

}

return false;

}

}

3、栈实现队列

【OJ链接】

还是和上面一样，需要用到两个栈（stack1、stack2）。和实现栈列不同的是，入队只能对同一个栈进行操作。如果两个栈都为空，则队列为空。

入队（push）：规定stack1用来入队。每次入队时，对stack1进行入栈操作即可。出队（pop）：规定stack2进行出队操作。如果队列为空时，不能进行出队操作。当stack2为空时，我们需要将stack1中所有元素出栈，放入stack2中，然后对stack2进行出栈操作。如果stack2不为空，则直接对stack2进行出栈操作即可。获取队列开头元素（peek）：和出栈操作相同，最后只需要获取stack2的栈顶元素即可。

【代码如下】

class MyQueue {

private Stack stack1;

private Stack stack2;

//构造方法

public MyQueue() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入队操作

public void push(int x) {

stack1.push(x);

}

//出队操作

public int pop() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.pop();

}

//获取队列开头的元素

public int peek() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.peek();

}

//判断队列是否为空

public boolean empty() {

if(stack1.empty()&&stack2.empty()){

return true;

}

return false;

}

}

4、实现最小栈

【OJ链接】

其实就是要在O(1)的时间复杂度内找到栈的最小元素。需要两个栈来实现，一个栈来进行出栈、入栈操作。只需要保证不管如何操作，另一个栈的栈顶元素都是当前栈的最小元素即可。

两个栈stack1、stack2，站的操作都在stack1中：

入栈：如果第一次入栈，我们需要将其也放入stack2中，之后的入栈，将入栈元素与stack2的栈顶元素进行比较，如果其小于stack2的栈顶元素，则将其放入stack2中。出栈：对stack1出栈时，将其与stack2的栈顶元素进行比较，如果其等于stack2的栈顶元素，则对stack2进行出栈操作。

这样就能保证stack2的栈顶元素总是stack1的最小元素。注意：如果stack1中入栈两个相同的最小元素，都需要对stack2进行入栈。

【代码如下】

class MinStack {

private Stack stack1;

private Stack stack2;

//构造方法

public MinStack() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入栈

public void push(int val) {

stack1.push(val);

if(stack2.empty()){

stack2.push(val);

}else{

if(val<=stack2.peek()){

stack2.push(val);

}

}

}

//出栈

public void pop() {

int x=stack1.pop();

if(x==stack2.peek()){

stack2.pop();

}

}

//获取栈顶元素

public int top() {

return stack1.peek();

}

//获取栈的最小元素

public int getMin() {

return stack2.peek();

}

}

x=queue1.poll();

queue2.offer(x);

}

return x;

}

}

//判断栈是否为空

public boolean empty() {

if(queue1.isEmpty()&&queue2.isEmpty()){

return true;

}

return false;

}

}

3、栈实现队列

【OJ链接】

还是和上面一样，需要用到两个栈（stack1、stack2）。和实现栈列不同的是，入队只能对同一个栈进行操作。如果两个栈都为空，则队列为空。

入队（push）：规定stack1用来入队。每次入队时，对stack1进行入栈操作即可。出队（pop）：规定stack2进行出队操作。如果队列为空时，不能进行出队操作。当stack2为空时，我们需要将stack1中所有元素出栈，放入stack2中，然后对stack2进行出栈操作。如果stack2不为空，则直接对stack2进行出栈操作即可。获取队列开头元素（peek）：和出栈操作相同，最后只需要获取stack2的栈顶元素即可。

【代码如下】

class MyQueue {

private Stack stack1;

private Stack stack2;

//构造方法

public MyQueue() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入队操作

public void push(int x) {

stack1.push(x);

}

//出队操作

public int pop() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.pop();

}

//获取队列开头的元素

public int peek() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.peek();

}

//判断队列是否为空

public boolean empty() {

if(stack1.empty()&&stack2.empty()){

return true;

}

return false;

}

}

4、实现最小栈

【OJ链接】

其实就是要在O(1)的时间复杂度内找到栈的最小元素。需要两个栈来实现，一个栈来进行出栈、入栈操作。只需要保证不管如何操作，另一个栈的栈顶元素都是当前栈的最小元素即可。

两个栈stack1、stack2，站的操作都在stack1中：

入栈：如果第一次入栈，我们需要将其也放入stack2中，之后的入栈，将入栈元素与stack2的栈顶元素进行比较，如果其小于stack2的栈顶元素，则将其放入stack2中。出栈：对stack1出栈时，将其与stack2的栈顶元素进行比较，如果其等于stack2的栈顶元素，则对stack2进行出栈操作。

这样就能保证stack2的栈顶元素总是stack1的最小元素。注意：如果stack1中入栈两个相同的最小元素，都需要对stack2进行入栈。

【代码如下】

class MinStack {

private Stack stack1;

private Stack stack2;

//构造方法

public MinStack() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入栈

public void push(int val) {

stack1.push(val);

if(stack2.empty()){

stack2.push(val);

}else{

if(val<=stack2.peek()){

stack2.push(val);

}

}

}

//出栈

public void pop() {

int x=stack1.pop();

if(x==stack2.peek()){

stack2.pop();

}

}

//获取栈顶元素

public int top() {

return stack1.peek();

}

//获取栈的最小元素

public int getMin() {

return stack2.peek();

}

}

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.pop();

}

//获取队列开头的元素

public int peek() {

if(stack2.empty()){

int size=stack1.size();

for(int i=0;i

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.peek();

}

//判断队列是否为空

public boolean empty() {

if(stack1.empty()&&stack2.empty()){

return true;

}

return false;

}

}

4、实现最小栈

【OJ链接】

其实就是要在O(1)的时间复杂度内找到栈的最小元素。需要两个栈来实现，一个栈来进行出栈、入栈操作。只需要保证不管如何操作，另一个栈的栈顶元素都是当前栈的最小元素即可。

两个栈stack1、stack2，站的操作都在stack1中：

入栈：如果第一次入栈，我们需要将其也放入stack2中，之后的入栈，将入栈元素与stack2的栈顶元素进行比较，如果其小于stack2的栈顶元素，则将其放入stack2中。出栈：对stack1出栈时，将其与stack2的栈顶元素进行比较，如果其等于stack2的栈顶元素，则对stack2进行出栈操作。

这样就能保证stack2的栈顶元素总是stack1的最小元素。注意：如果stack1中入栈两个相同的最小元素，都需要对stack2进行入栈。

【代码如下】

class MinStack {

private Stack stack1;

private Stack stack2;

//构造方法

public MinStack() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入栈

public void push(int val) {

stack1.push(val);

if(stack2.empty()){

stack2.push(val);

}else{

if(val<=stack2.peek()){

stack2.push(val);

}

}

}

//出栈

public void pop() {

int x=stack1.pop();

if(x==stack2.peek()){

stack2.pop();

}

}

//获取栈顶元素

public int top() {

return stack1.peek();

}

//获取栈的最小元素

public int getMin() {

return stack2.peek();

}

}

int x=stack1.pop();

stack2.push(x);

}

}

return stack2.peek();

}

//判断队列是否为空

public boolean empty() {

if(stack1.empty()&&stack2.empty()){

return true;

}

return false;

}

}

4、实现最小栈

【OJ链接】

其实就是要在O(1)的时间复杂度内找到栈的最小元素。需要两个栈来实现，一个栈来进行出栈、入栈操作。只需要保证不管如何操作，另一个栈的栈顶元素都是当前栈的最小元素即可。

两个栈stack1、stack2，站的操作都在stack1中：

入栈：如果第一次入栈，我们需要将其也放入stack2中，之后的入栈，将入栈元素与stack2的栈顶元素进行比较，如果其小于stack2的栈顶元素，则将其放入stack2中。出栈：对stack1出栈时，将其与stack2的栈顶元素进行比较，如果其等于stack2的栈顶元素，则对stack2进行出栈操作。

这样就能保证stack2的栈顶元素总是stack1的最小元素。注意：如果stack1中入栈两个相同的最小元素，都需要对stack2进行入栈。

【代码如下】

class MinStack {

private Stack stack1;

private Stack stack2;

//构造方法

public MinStack() {

stack1=new Stack<>();

stack2=new Stack<>();

}

//入栈

public void push(int val) {

stack1.push(val);

if(stack2.empty()){

stack2.push(val);

}else{

if(val<=stack2.peek()){

stack2.push(val);

}

}

}

//出栈

public void pop() {

int x=stack1.pop();

if(x==stack2.peek()){

stack2.pop();

}

}

//获取栈顶元素

public int top() {

return stack1.peek();

}

//获取栈的最小元素

public int getMin() {

return stack2.peek();

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。