队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头。
自己实现队列:
链表实现:实现一个双向链表,增加元素,采用尾插法,删去元素采用头删法,具体步骤链表处详细讲过,此处不再赘述
public class MyQueue1 { class ListNode{ public int val; public ListNode next; public ListNode prev; public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last; public void offer(int val){ ListNode node=new ListNode(val); if (head==null){ head=last=node; return; } last.next=node; node.prev=last; last=node; } public boolean isEmpty(){ return head==null; } public int poll(){ if (head==null){ throw new NullPointerException(); } if (head==last){ int tpm=head.val; head=last=null; return tpm; } int tmp=head.val; head=head.next; head.prev=null; return tmp; } public int peek(){ if (head==null){ throw new NullPointerException(); } int tmp=head.val; return tmp; } }
数组实现循环队列:
1,enQueue:
public boolean enQueue(int val){ if (isFull()){ return false; } elem[last]=val; last=(last+1)%elem.length; return true; }
2,deQueue:删除元素时,将first加一,将数组的起始位置改变
public boolean deQueue(){ if (isFull()){ return false; } first=(first+1)%elem.length; return true; }
3,front:得到队列的首元素
public int front(){ if (isEmpty()){ return -1; } return elem[first]; }
4,rear:得到队列的尾元素,注意:last可能等于0(删除一次时).这时last-1=-1,出现越界。所以这种情况应该单独判断
public int rear(){ if (isEmpty()){ return -1; } int index=(last==0)?elem.length-1:last-1; return elem[index]; }
5,isFull/isEmpty:
public boolean isFull(){ return (last+1)%elem.length==first; } public boolean isEmpty(){ return last==first; }
6,因为对数组初始化的时候,初始化数组的容量,但上述解法会浪费一块空间,所以真实的数组容量比初始化的少一个,所以构造方法应该写成如下这种方式:
public MyQueue2(int k) { this.elem = new int[k+1]; }
两个队列实现一个栈
public class Queue3 { public Queue<Integer> queue1; public Queue<Integer> queue2; public Queue3() { this.queue1 = new LinkedList<>(); this.queue2 = new LinkedList<>(); } }
1,poll:如图,在栈中,4会最先从栈顶取出,而队列1中最先取出的是1,所以想要取出4,就要将1,2,3弹出放到队列2中。这时,取出的就是4了。同理可得:想要取出元素,先判断的、那个队列中含有元素,将有元素的队列中的元素放到另一个队列中。
public int poll(){ if (isEmpty()){ 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(); } }
2,top:得到栈顶元素,与上述处理方法基本一致
public int top(){ if (isEmpty()){ return -1; } if (!queue1.isEmpty()){ int size=queue1.size(); for (int i = 0; i < size-1; i++) { queue2.offer(queue1.poll()); } int tmp=queue1.peek(); queue2.offer(queue1.poll()); return tmp; }else { int size=queue2.size(); for (int i = 0; i < size-1; i++) { queue1.offer(queue2.poll()); } int tmp=queue2.peek(); queue1.offer(queue2.poll()); return tmp; } }
3,offer:增加元素,先判断那个队列中有元素,将添加的元素放到有元素的队列中
public void offer(int val){ if (isEmpty()){ queue1.offer(val); return; } if (!queue1.isEmpty()){ queue1.offer(val); }else { queue2.offer(val); } }
4,isEmpty:当两个队列中的均为空时,这说明他们等价的栈中也没元素
public boolean isEmpty(){ return queue1.isEmpty()&&queue2.isEmpty(); }
两个栈实现一个队列
public class Queue4 { public Stack<Integer> stack1; public Stack<Integer> stack2; public Queue4() { this.stack1 = new Stack<>(); this.stack2 = new Stack<>(); } }
1,poll:如图,队列中最先取出的是1,而栈1中最先取出的是4,所以要将栈1中的元素全部放到栈2中,然后取出栈2 的栈顶元素就是队列最先取出的元素。
public int poll(){ if (isEmpty()){ return -1; } if (stack2.empty()){ while (!stack1.empty()){ stack2.push(stack1.pop()); } } return stack2.pop(); }
2,top:取出队头元素,与上述的方法大致相同
public int top(){ if (isEmpty()){ return -1; } if (stack2.empty()){ while (!stack1.empty()){ stack2.push(stack1.pop()); } } return stack2.peek(); }
3,offer:直接将元素添加到栈1中
public void offer(int val){ stack1.push(val); }
4,isEmpty:当两个栈中的均为空时,这说明他们等价的队列中也没元素
public boolean isEmpty(){ return stack1.isEmpty()&&stack2.isEmpty(); }