栈和队列（Java）

一.栈（Stack）

1.定义

栈是限定仅在表尾进行插入或删除操作的线性表

一般的表尾称为栈顶      表头称为栈底

栈具有“后进先出”的特点

2.对栈的模拟

栈主要具有以下功能：

• push(Object item)：将元素item压入栈顶。

• pop()：弹出栈顶元素，并将其从栈中删除。

• peek()：返回栈顶元素，但不删除它。

• isEmpty()：判断栈是否为空，返回布尔值。具体模拟代码我们可以用一个顺序表来实现如下

而在Java 编程应用idea中我们在使用时无需再进行模拟实现，可直接通过栈的实例化  然后直接进行调用栈的不同方法

实例化一个存储字符串类型的栈

则可直接stack.pop（）....进行调用方法

3.括号匹配问题

链接如下： 

20. 有效的括号 - 力扣（LeetCode）

该题目就需要我们对于栈的功能的熟练掌握

需我们考虑三种括号不匹配情况从而考虑入栈和出栈的适配问题

以下是代码：

二.队列（Queue）

1.定义

与栈相反，队列是一种先进先出的线性表

插入一端成为队尾，删除一端称为队头

2.对队列的模拟

队列具有以下功能：

• 1. offer(E e)：添加元素到队列
  2.poll()：移除并返回队列头部的元素
• 3. peek()：获取队列头部的元素，但不移除
  4.isEmpty()：检查队列是否为空

以下队列的模拟我是借助链表来进行模拟实现

Java中idea也具有Queue队列 但队列是作为一个抽象类 所以

在实例化对象时需要向上转型

则可进行调用队列的方法：queue.offer();....

3.循环队列

循环队列是队列的一大重点

与队列不同的就是需要考虑队尾与对头的衔接

1.注意队空与队满的判断条件

队空的条件：q.front==q.rear;

队满的条件：(q.rear+1)%MaxSize==q.front;

2.代码详解

三.栈对队列的模拟以及队列对栈的模拟

1.队列对栈的模拟

225. 用队列实现栈 - 力扣（LeetCode）

class MyStack {

Queue<Integer>queue1 ;//申请第一个队列

Queue<Integer>queue2 ;//申请第二个队列

    public MyStack() {

        queue1=new LinkedList<>();

        queue2=new LinkedList<>();

    }

   

    public void push(int x) {//在模拟栈入队时 找两个队列中非空的队列

        if(!queue1.isEmpty()){

            queue1.offer(x);

        }

        else if(!queue2.isEmpty()){

            queue2.offer(x);

        }

        else{

            queue1.offer(x);

        }

    }

   

    public int pop() {//出队列时将非空队列中size-1个元素入另一个队列中，留下的即为模拟栈该出栈的元素

        if(empty()){

            return -1;

        }

if(!queue1.isEmpty()){

    int size=queue1.size();

    for(int i=0;i<size-1;i++){

        queue2.offer(queue1.poll());

    }

    return queue1.poll();

}

else{

    int size=queue2.size();

     for(int i=0;i<size-1;i++){

        queue1.offer(queue2.poll());

    }

    return queue2.poll();

}

       

    }

   

    public int top() {

        if(empty()){

            return -1;

        }

        if(!queue1.isEmpty()){

            int val=0;

            int size=queue1.size();

          for(int i=0;i<size;i++){

            val=queue1.poll();

            queue2.offer(val);

          }

          return val;

        }

        else{

            int val=0;

            int size=queue2.size();

          for(int i=0;i<size;i++){

            val=queue2.poll();

            queue1.offer(val);

          }

          return val;

        }

    }

    public boolean empty() {

        return queue1.isEmpty()&&queue2.isEmpty();

    }

}

2.栈对队列的模拟

232. 用栈实现队列 - 力扣（LeetCode）

注意结合栈的特性以两个栈来结合使队列的先进后出成功进行

class MyQueue {

public Stack <Integer>  stack1;

public Stack <Integer> stack2;

    public MyQueue() {

        stack1=new Stack<>();

        stack2=new Stack<>();

    }

   

    public void push(int x) {

        if(empty()){

            stack1.push(x);

        }

        if(stack1.isEmpty()){

            stack2.push(x);

        }

        else{

            stack1.push(x);

        }

    }

    public int pop() {

        if(empty()){

            return -1;

        }

        if(!stack2.isEmpty()){

            return stack2.pop();

        }

        else{

         while(!stack1.isEmpty()){

              stack2.push(stack1.pop());

            }

            return stack2.pop();

        }

    }

   

    public int peek() {

        if(empty()){

            return -1;

        }

        if(stack1.isEmpty()){

             int sz=stack2.size();

            int num=0;

            for(int i=0;i<sz;i++){

                num=stack2.pop();

              stack1.push(num);

            }

            return stack1.peek();

        }

        else{

            int sz=stack1.size();

            int num=0;

            for(int i=0;i<sz;i++){

                num=stack1.pop();

              stack2.push(num);

            }

            return stack2.peek();

        }

    }

   

    public boolean empty() {

        return stack1.isEmpty()&&stack2.isEmpty();

    }

}