栈和队列

一、定义

• 栈：先进后出
• 队列：先进先出

二、题目

1.用数组结构实现大小固定的栈和队列

2.返回栈中最小元素

题意

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

要求

(1)pop、push、getMin操作的时间复杂度都是O(1)。
(2)设计的栈类型可以使用现成的栈结构。

解题思路

1. 利用一个help栈，每次data栈有数字入栈，在help中压入最小值；每次data栈栈顶出栈，help栈顶同步出栈。
2. 利用一个help栈，只有当data栈入栈的数≤help栈顶时，help才压数进栈；每次data栈出栈，只有出栈的数=help栈顶时，help才将栈顶弹出。

3.栈和队列的相互实现

题1 两个队列实现栈

解题思路

每次出队列的时候，将前面的数都保存到help队列中，留一个在data队列中，然后再pop，就是最后一个数了。最后交换data和help。

题2 两个栈实现队列

解题思路

利用一个help栈
有两个原则：

• help栈为空，data栈才能向help栈中倒数据。
• data栈要向help栈倒数据，一定要将data内的所有数据一次倒完。

4.猫狗队列

题意

• 宠物、狗和猫的类如下：

public class Pet {
  private String type;
  public Pet(String type) {
    this.type = type;
  }
  public String getPetType() {
    return this.type;
  }
}

public class Dog extends Pet {
  public Dog() {
    super("dog");
  }
}

public class Cat extends Pet {
  public Cat() {
    super("cat");
  }
}

• 实现一种狗猫队列的结构，要求如下：

1. 用户可以调用add方法将cat类或dog类的实例放入队列中；
2. 用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
3. 用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；
4. 用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；
5. 用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例；
6. 用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例；
7. 用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。