一、定义
- 栈：先进后出
- 队列：先进先出
二、题目
1.用数组结构实现大小固定的栈和队列
2.返回栈中最小元素
题意
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
要求
(1)pop、push、getMin操作的时间复杂度都是O(1)。
(2)设计的栈类型可以使用现成的栈结构。
解题思路
- 利用一个help栈，每次data栈有数字入栈，在help中压入最小值；每次data栈栈顶出栈，help栈顶同步出栈。
- 利用一个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");
}
}
- 实现一种狗猫队列的结构，要求如下：
- 用户可以调用add方法将cat类或dog类的实例放入队列中；
- 用户可以调用pollAll方法，将队列中所有的实例按照进队列的先后顺序依次弹出；
- 用户可以调用pollDog方法，将队列中dog类的实例按照进队列的先后顺序依次弹出；
- 用户可以调用pollCat方法，将队列中cat类的实例按照进队列的先后顺序依次弹出；
- 用户可以调用isEmpty方法，检查队列中是否还有dog或cat的实例；
- 用户可以调用isDogEmpty方法，检查队列中是否有dog类的实例；
- 用户可以调用isCatEmpty方法，检查队列中是否有cat类的实例。
