1. 栈(Stack)
现实生活也有很多像栈一样的结构，如枪里的子弹最先打出去的是最后装的子弹，羽毛球桶最先拿出来的羽毛球是最后放进去的，都符合栈的后进先出LIFO（Last In First Out）的原则。
1.2栈的常用方法
2. 队列(Queue)
2.2 队列的实现
如图我们可以知道队列是一个接口，接口不能实例化，但可以通过实现了该接口的类来实例化，所以 Queue可以通过ArrayList，LinkedList，PriorityQueue等来实例化该接口；
public static void main ( String [] args ) {Queue < Integer > q = new LinkedList <> ();Queue < Integer > q1 = new ArrayList <> ();Queue < Integer > q2 = new PriorityQueue <> ();}
3 循环队列
class MyCircularQueue {int[] elem;int front;int rear;int size;public MyCircularQueue(int k) {elem=new int[k];front=rear=0;}public boolean enQueue(int value) {if(isFull()){return false;}else{elem[rear]=value;rear=(rear+1)% elem.length;size++;return true;}}public boolean deQueue() {if(isEmpty()){return false;}else{front=(front+1)%elem.length;size--;return true;}}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int rear1=(rear==0)?elem.length-1:rear-1;//rear==0的时候比较特殊return elem[rear1];}public boolean isEmpty() {return size==0;}public boolean isFull() {return size==elem.length;}
}class MyCircularQueue {int[] elem;int front;int rear;public MyCircularQueue(int k) {elem=new int[k+1];//浪费一个空间来判断循环队列的队满；front=rear=0;}public boolean enQueue(int value) {if(isFull()){return false;}else{elem[rear]=value;rear=(rear+1)% elem.length;return true;}}public boolean deQueue() {if(isEmpty()){return false;}else{front=(front+1)%elem.length;return true;}}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int rear1=(rear==0)?elem.length-1:rear-1;//rear==0的时候比较特殊return elem[rear1];}public boolean isEmpty() {return front==rear;}public boolean isFull() {return (rear+1)% elem.length==front;}
}4.栈和队列的相互转化
4.1用队列实现栈
栈：先进后出
队列：先进先出
进栈的实现：两队列都空就放数据到队列1里，否则就哪个队列为空就放哪里
出栈的实现：将有不为空的队列里的size-1个元素方到另一个队列里，然后就将只剩下一个元素的队列出队列就实现的出栈；
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.add(x);
}else if(!queue2.isEmpty()){
queue2.add(x );
}else{
queue1.add(x);
}
}
public int pop() {
if(empty()){
return -1;
}
if (queue1.isEmpty()){
int size= queue2.size();
for (int i = 0; i < size-1; i++) {
int val=queue2.poll();
queue1.add(val);
}
return queue2.poll();
}
else {
int size= queue1.size();
for (int i = 0; i < size-1; i++) {
int val = queue1.poll();
queue2.add(val);
}
return queue1.poll();
}
}
public int top() {
if(empty()){
return -1;
}
if (queue1.isEmpty()){
int size= queue2.size();
for (int i = 0; i < size-1; i++) {
int val=queue2.poll();
queue1.add(val);
}
int val2= queue2.peek();
queue1.add(queue2.poll());
return val2;
}
else {
int size= queue1.size();
for (int i = 0; i < size-1; i++) {
int val = queue1.poll();
queue2.add(val);
}
int val2= queue1.peek();
queue2.add(queue1.poll());
return val2;
}
}
public boolean empty() {
return (queue2.isEmpty()&&queue1.isEmpty());
}
}
注意：
问题：观察上图发现只是实例化queue接口的类不一样，其余代码一样，那为什么结果会不一样呢？
解答：
优先级队列 是会自动按照升序排序的 也就是每次push进来一个元素 都会自动排成升序 所以stack中从栈底到栈顶分别是 1 2 2 3 4，因此结果是4 4 3
而双向链表是没有排序这个性质 从栈底到栈顶分别是 1 2 3 4 2 ，因此结果是 2 2 4
4.1用栈实现栈队列
栈：先进后出
队列：先进先出
进队的模拟实现：
stack1专门用来放元素，都为空的时候就将元素加入stack1中，stack1不为空就直接push，为空就将stack2中的元素全部放入stack1中
出队的模拟实现：
stack2专门用来出元素，进行出对操作时将元素放入stack2中出元素即可
class MyQueue {
Stack<Integer> stack1;
Stack<Integer> stack2;
public MyQueue() {
stack1=new Stack<>();
stack2=new Stack<>();
}
public void push(int x) {
if(!stack1.isEmpty()) {
stack1.push(x);
}else if(!stack2.isEmpty()){
int size=stack2.size();
for (int i = 0; i < size; i++) {
int val=stack2.pop();
stack1.push(val);
}
stack1.push(x);
}else{
stack1.push(x);
}
}
public int pop() {
if(empty()){
return -1;
}
if(stack2.isEmpty()){
int size=stack1.size();
for (int i = 0; i < size; i++) {
stack2.push(stack1.pop());
}
return stack2.pop();
}else{
return stack2.pop();
}
}
public int peek() {
if(empty()){
return -1;
}
if(stack2.isEmpty()){
int size=stack1.size();
for (int i = 0; i < size; i++) {
stack2.push(stack1.pop());
}
return stack2.peek();
}else{
return stack2.peek();
}
}
public boolean empty() {
return stack1.isEmpty()&&stack2.isEmpty();
}
}
