资源网站怎样做,做班级网站的详细计划书,百度怎么建网站,培训网站大全1.概念队列 : 只允许在一段进行插入数据操操作 , 在另一端进行删除数据操作的特殊线性表 ; 队列是先进先出入队列 : 进行插入操作的一端称为队尾出队列 : 进行删除操作的一端称为对头2.队列的使用在Java中 , Queue 是一个接口 , 底层通过链表实现的方法行为说明add(E e)添加元素…1.概念队列 : 只允许在一段进行插入数据操操作 , 在另一端进行删除数据操作的特殊线性表 ; 队列是先进先出入队列 : 进行插入操作的一端称为队尾出队列 : 进行删除操作的一端称为对头2.队列的使用在Java中 , Queue 是一个接口 , 底层通过链表实现的方法行为说明add(E e)添加元素到队尾若队列已满抛出 IllegalStateException推荐使用 offer()offer(E e)添加元素到队尾队列满时返回 false更安全的插入方式remove()移除并返回队头元素队列空时抛出NoSuchElementException推荐使用 poll()poll()移除并返回队头元素队列空时返回 null安全的移除方式element()查看队头元素不删除队列空时抛出异常推荐使用 peek()peek()查看队头元素不删除队列空时返回 null安全的查看方式
public static void main(String[] args) {QueueInteger queue new LinkedList();queue.offer(11);//添加元素到队尾queue.offer(12);queue.offer(13);queue.offer(14);queue.offer(15);System.out.println(queue);//打印队列 [11, 12, 13, 14, 15]int a1 queue.poll();//移除头元素,并返回System.out.println(a1);//11System.out.println(queue);//[12, 13, 14, 15]int a2 queue.peek();//获取队头元素System.out.println(a2);//12
}3.队列的模拟实现①实现队列
public class MyQueue {public static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(int val){this.val val;}}public int usedSize 0;public ListNode head null;public ListNode last null;public boolean isEmpty(){//检查是否为空return usedSize 0;//如果是空的 , usedSize为0 返回true}public void offer(int val){//入队列,采用的是尾插法ListNode node new ListNode(val);if(isEmpty()){head last node;//把node节点赋值给head和lastusedSize;}else {last.next node;node.prev last;last node;usedSize;}}public int poll(){//相应的出队列应该采用,头删法if(isEmpty()) {return -1;}int vall head.val;head head.next;if(head ! null){head.prev null;}usedSize--;return vall;}public int size(){//返回大小return usedSize;}}②测试
public static void main(String[] args) {MyQueue myQueue new MyQueue();myQueue.offer(11);//添加元素到队尾myQueue.offer(12);myQueue.offer(13);myQueue.offer(14);myQueue.offer(15);System.out.println(myQueue.poll());
}4.循环队列循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间但是使用循环队列我们能使用这些空间去存储新的值方法名描述参数返回值特殊说明MyCircularQueue(k)构造器初始化队列设置队列容量为 kint k队列容量无内部实际使用 k1 的空间来区分空满状态Front()获取队首元素无int队首元素值队列为空时返回 - 1Rear()获取队尾元素无int队尾元素值队列为空时返回 - 1enQueue(value)向队列插入元素int value待插入元素boolean插入成功返回 true队列满则返回 false插入后队尾指针循环后移deQueue()从队列删除队首元素无boolean删除成功返回 true队列为空则返回 false删除后队首指针循环后移isEmpty()检查队列是否为空无boolean为空返回 true否则返回 false当 front rear 时队列空isFull()检查队列是否已满无boolean已满返回 true否则返回 false当 (rear1) % 容量 front 时队列满
class MyCircularQueue {public int front;public int rear;public int[] elem;public MyCircularQueue(int k) {elem new int[k1];}//入队列 public boolean enQueue(int value) {if(isFull()) {return false;}elem[rear] value;rear (rear1)%elem.length;return true;}//出队列 public boolean deQueue() {if(isEmpty()) {return false;}front (front1)%elem.length;return true;}//得到队头元素 public int Front() {if(isEmpty()) {return -1;}return elem[front];}public int Rear() {if(isEmpty()) {return -1;}int index (rear 0) ? elem.length-1 : rear-1;return elem[index];}public boolean isEmpty() {return rear front;}public boolean isFull() {return (rear1)%elem.length front;}}5.双端队列(Deque)双端队列 是 指允许两端都可以进行入队和出队操作的队列Deque是一个接口, 使用时 必须创建LinkedList对象Deque的接口比较多 , 栈和队列均可以实现该接口
public static void main(String[] args) {DequeInteger stack new LinkedList();//双端队列的链式实现DequeInteger queue new ArrayDeque();//双端队列的线性实现
}6.用队列实现栈模拟的入栈操作 : 将元素放到不为空的队列中模拟的出栈操作 : 把不为空的队列中的size-1个元素放到另一个队列中 ; 最后剩下的就是模拟栈中的顶层元素
import java.util.LinkedList;
import java.util.Queue;class MyStackUseQueue {public QueueInteger qu1;public QueueInteger qu2;public MyStackUseQueue() {qu1 new LinkedList();qu2 new LinkedList();}public void push(int x) {if(!qu1.isEmpty()) {qu1.offer(x);}else if(!qu2.isEmpty()) {qu2.offer(x);}else {qu1.offer(x);}}public int pop() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size qu1.size();for(int i 0;i size-1;i) {qu2.offer( qu1.poll());}return qu1.poll();}else {int size qu2.size();for(int i 0;i size-1;i) {qu1.offer( qu2.poll());}return qu2.poll();}}public int top() {if(empty()) {return -1;}if(!qu1.isEmpty()) {int size qu1.size();int val 0;for(int i 0;i size;i) {val qu1.poll();qu2.offer(val);}return val;}else {int size qu2.size();int val 0;for(int i 0;i size;i) {val qu2.poll();qu1.offer(val);}return val;}}public boolean empty() {return qu1.isEmpty() qu2.isEmpty();}
}7.用栈实现队列模拟入队操作 : 放到第一个栈中模拟出队操作 : 判断第二个栈是否为空 ?如果为空 : 需要把第一个栈中的所有元素都放到第二个栈里 , 取出第二个栈中的顶层元素如果不为空 : 直接取出第二个栈中的顶层元素
import java.util.ArrayDeque;class MyQueueUseStack {public ArrayDequeInteger stack1;public ArrayDequeInteger stack2;public MyQueueUseStack() {stack1 new ArrayDeque();stack2 new ArrayDeque();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()) {return -1;}if(stack2.isEmpty()) {//第一个栈里面所有的元素 放到第二个栈当中 while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()) {return -1;}if(stack2.isEmpty()) {//第一个栈里面所有的元素 放到第二个栈当中 while(!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() stack2.isEmpty();}
}
