栈变队列，队列变栈，猫狗队列

队列，队列变栈，猫狗队列"/>

栈变队列，队列变栈，猫狗队列

栈：先进后出； 队列：先进先出；
栈变队列：用两个栈结构实现队列结构。
思想：定义一个stackPush栈用来存放添加进来的元素，定义一个stackPop栈用来返回队列的poll方法。一开始将添加的元素放入到Push栈里面，然后如果要调用队列的poll方法时，使用while循环将Push栈里面的元素全部放入到Pop栈里面，再返回Pop栈的pop方法。
代码：

public static class TwoStacksQueue {private Stack<Integer> stackPush;private Stack<Integer> stackPop;public TwoStacksQueue() {stackPush = new Stack<Integer>();//定义一个压入栈stackPop = new Stack<Integer>();//定义一个弹出栈}public void push(int pushInt) {  //队列的push方法，和下面stackPush.push不一样，这个是这个类的方法而不是栈里面的pushstackPush.push(pushInt);}public int poll() {if (stackPop.empty() && stackPush.empty()) {throw new RuntimeException("Queue is empty!");} else if (stackPop.empty()) {while (!stackPush.empty()) { //while循环，将stackPush栈中的元素压入到stackPop中，元素顺序刚好相反。stackPop.push(stackPush.pop());//这个push是压入到stackPop栈中而不是调用什么的push方法}}return stackPop.pop();//从弹出栈中取得应该弹出的元素}public int peek() {if (stackPop.empty() && stackPush.empty()) {throw new RuntimeException("Queue is empty!");} else if (stackPop.empty()) {while (!stackPush.empty()) {stackPop.push(stackPush.pop());}}return stackPop.peek();}

队列变栈:用两个队列实现栈结构
思想：跟栈变队列相似，定义两个队列来分别存放和取出元素，满足栈的push和pop方法,注意代码的swap过程，将两个队列交换。
代码:

public static class TwoQueuesStack {private Queue<Integer> queue;  //定义一个队列private Queue<Integer> help;   //定义一个帮助队列public TwoQueuesStack() {queue = new LinkedList<Integer>();help = new LinkedList<Integer>();}public void push(int pushInt) { queue.add(pushInt);}public int peek() {if (queue.isEmpty()) {throw new RuntimeException("Stack is empty!");}while (queue.size() != 1) {help.add(queue.poll());}int res = queue.poll();help.add(res);swap();return res;}public int pop() {if (queue.isEmpty()) {throw new RuntimeException("Stack is empty!");}while (queue.size() > 1) {help.add(queue.poll());}int res = queue.poll();swap();return res;}private void swap() {  //交换两个队列，因为添加进来的元素要先出去，放在queue队列上以保持原来的数据在新的下面Queue<Integer> tmp = help;help = queue;queue = tmp;}}

3：猫狗队列 【题目】 宠物、狗和猫的类如下： 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类的实例。
思想： 定义一个猫队列和一个狗队列用来存放猫和狗，再定义一个count变量，用来记录猫和狗进来的顺序，不管猫还是狗进入了队列，count都+1，所以先进队列的count值更小，把宠物的信息封装成了一个类放在队列里，具体看代码。
代码：

import java.util.LinkedList;
import java.util.Queue;public class Code_04_DogCatQueue {public static class Pet {private String type;public Pet(String type) {this.type = type;}public String getPetType() {return this.type;}}public static class Dog extends Pet {public Dog() {super("dog"); //super继承父类的构造方法}}public static class Cat extends Pet {public Cat() {super("cat");}}public static class PetEnterQueue {private Pet pet;private long count; //定义count来记录猫狗进来的顺序public PetEnterQueue(Pet pet, long count) {this.pet = pet;this.count = count;}public Pet getPet() {return this.pet;}public long getCount() {return this.count;}public String getEnterPetType() {return this.pet.getPetType();}}public static class DogCatQueue {private Queue<PetEnterQueue> dogQ; //泛型，队列里的元素是PetEnterQueue的这种类型private Queue<PetEnterQueue> catQ;private long count;public DogCatQueue() {this.dogQ = new LinkedList<PetEnterQueue>();this.catQ = new LinkedList<PetEnterQueue>();this.count = 0;}public void add(Pet pet) {if (pet.getPetType().equals("dog")) {this.dogQ.add(new PetEnterQueue(pet, this.count++)); //判断，如果是dog就进入dog队列，count+1表示位置} else if (pet.getPetType().equals("cat")) {this.catQ.add(new PetEnterQueue(pet, this.count++));} else {throw new RuntimeException("err, not dog or cat");}}public Pet pollAll() {  //3种情况，猫狗都不为空；猫为空，狗不为空；猫不为空，狗为空。if (!this.dogQ.isEmpty() && !this.catQ.isEmpty()) {if (this.dogQ.peek().getCount() < this.catQ.peek().getCount()) {  //如果dog的count值小于猫的count值，就表示dog比cat更早进来。return this.dogQ.poll().getPet();} else {return this.catQ.poll().getPet();}} else if (!this.dogQ.isEmpty()) {return this.dogQ.poll().getPet(); } else if (!this.catQ.isEmpty()) {return this.catQ.poll().getPet();} else {throw new RuntimeException("err, queue is empty!");}}public Dog pollDog() {  //弹出狗if (!this.isDogQueueEmpty()) {  //判断狗队列是否为空return (Dog) this.dogQ.poll().getPet();} else {throw new RuntimeException("Dog queue is empty!");}}public Cat pollCat() {if (!this.isCatQueueEmpty()) {return (Cat) this.catQ.poll().getPet();} elsethrow new RuntimeException("Cat queue is empty!");}public boolean isEmpty() {return this.dogQ.isEmpty() && this.catQ.isEmpty();}public boolean isDogQueueEmpty() {  //定义的判断方法return this.dogQ.isEmpty();}public boolean isCatQueueEmpty() {return this.catQ.isEmpty();}}public static void main(String[] args) {DogCatQueue test = new DogCatQueue();Pet dog1 = new Dog();Pet cat1 = new Cat();Pet dog2 = new Dog();Pet cat2 = new Cat();Pet dog3 = new Dog();Pet cat3 = new Cat();test.add(dog1);test.add(cat1);test.add(dog2);test.add(cat2);test.add(dog3);test.add(cat3);test.add(dog1);test.add(cat1);test.add(dog2);test.add(cat2);test.add(dog3);test.add(cat3);test.add(dog1);test.add(cat1);test.add(dog2);test.add(cat2);test.add(dog3);test.add(cat3);while (!test.isDogQueueEmpty()) {System.out.println(test.pollDog().getPetType());}while (!test.isEmpty()) {System.out.println(test.pollAll().getPetType());}}}