订阅号怎么做免费的视频网站,免费下载的app,朔州网站建设费用,wordpress 选单设定一、什么是队列
普通队列#xff1a;只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff0c;队列具有先进先出FIFO(FirstIn First Out) 入队列#xff1a;进行插入操作的一端称为队尾#xff08;Tail/Rear#xff09; 出队列#xf…一、什么是队列
普通队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(FirstIn First Out) 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一端称为队头Head/Front 双端队列可以在对头或者队尾进行插入或者删除操作。 普通队列和双端队列 从上面知道双向列表可以当普通队列使用也可以当双端队列使用也可以当栈使用。
二、队列常用的方法
2.1、Queue 注意add函数和offer函数
public static void main(String[] args) {QueueInteger queue new LinkedList();queue.add(1);//添加元素queue.add(2);//添加元素queue.add(3);//添加元素queue.offer(4);//添加元素queue.offer(5);//添加元素queue.offer(6);//添加元素System.out.println(queue.peek());//获取对头元素但是不删除System.out.println(queue.element());//获取对头元素但是不删除System.out.println(queue.poll());//获取对头元素并且删除对头元素System.out.println(queue.remove());//获取对头元素并且删除对头元素}2.2、Deque public static void main(String[] args) {DequeInteger deque new LinkedList();deque.add(1);//默认在队尾添加元素deque.addFirst(2);//在对头添加元素deque.addLast(3);//在队尾添加元素deque.offer(4);//在队尾添加元素deque.offerLast(5);//在队尾添加元素deque.offerFirst(6);//在队头添加元素System.out.println(deque);System.out.println(deque.peek());//获取元素但是不删除System.out.println(deque.peekFirst());//获取队头元素但是不删除System.out.println(deque.peekLast());//获取队尾元素但是不删除System.out.println(deque.poll());//获取队头元素并且删除System.out.println(deque.pollFirst());//获取队头元素并且删除System.out.println(deque);}三、单链表模拟实现队列 单链表可以实现队列那双向链表也可以实现队列 使用单链表第三种方式实现队列 offer- 在队列里面添加元素
/*** 在队列里面添加元素实际上就是尾插法* param val*/public void offer(int val){//要插入节点那就要先创造一个节点Node node new Node(val);//这时候就要分两种情况1、如果是第一次插入 2、不是第一次插入if(head null){//head null说明是第一次插入head node;last node;}else {last.next node;last last.next;}}poll - 出队列
/*** 出队列并且删除元素* return*/public int poll(){//出队列就是删除头结点但是如果链表里面没有节点那就不能删除if(isEmpty()){throw new RuntimeException(队列为空);}int oldVal head.val;head head.next;return oldVal;}/*** 判断队列是否为空如果队列为空那就返回true否则返回FALSE* return*/public boolean isEmpty(){return this.head null;}使用的单链表实现简单的队列
//使用单链表实现队列首先就要定义节点
class Node{//值域public int val;//指针域public Node next;public Node(int val){this.val val ;}
}
public class MyQueue {//单链表实现队列那就要加上一个尾指针public Node head;//头结点public Node last;//尾巴节点/*** 在队列里面添加元素实际上就是尾插法* param val*/public void offer(int val){//要插入节点那就要先创造一个节点Node node new Node(val);//这时候就要分两种情况1、如果是第一次插入 2、不是第一次插入if(head null){//head null说明是第一次插入head node;last node;}else {last.next node;last last.next;}}/*** 出队列并且删除元素* return*/public int poll(){//出队列就是删除头结点但是如果链表里面没有节点那就不能删除if(isEmpty()){throw new RuntimeException(队列为空);}int oldVal head.val;head head.next;return oldVal;}/*** 判断队列是否为空如果队列为空那就返回true否则返回FALSE* return*/public boolean isEmpty(){return this.head null;}/*** 获取对头的元素* return*/public int peek(){//出队列就是删除头结点但是如果链表里面没有节点那就不能删除if(isEmpty()){throw new RuntimeException(队列为空);}return head.val;}
}四、循环队列
我们说了可以利用链表实现队列那能不能利用数组实现队列 上图转载于https://blog.csdn.net/DarkAndGrey/article/details/122511544
队列面试题
设计循环队列 上图转载于https://blog.csdn.net/DarkAndGrey/article/details/122511544
代码如下
public class MyCircularQueue {//我们知道循环队列是有数组实现的所以要创建一个数组并且还有表示对头和队尾的下标public int[] elem;public int front;//对头的下标public int rear;//队尾的下标/*** 构造方法初始化数组的大小* param k*/public MyCircularQueue(int k) {this.elem new int[k1];}/*** 入队列* param value* return*/public boolean enQueue(int value) {//在入队列的时候先判断队列是否满满了不能入if(isFull()){return false;}elem[rear] value;rear (rear1) % elem.length;return true;}/*** 出队列* return*/public boolean deQueue() {if(isEmpty()){return false;}front (front1) % elem.length;return true;}/*** 返回对头下标的元素* return*/public int Front() {if(isEmpty()){return -1;}return elem[front];}/*** 获取队尾元素* return*/public int Rear() {if(isEmpty()){return -1;}int index 0;if(rear 0){index elem.length - 1;}else{index rear - 1;}return elem[index];}public boolean isEmpty() {//front的下一个是rear那就说明空了return front rear;}/*** 判断队列是否满* return*/public boolean isFull() {//rear的下一个如果是front那这个队列就满了if((rear1) % elem.length front){return true;}return false;}
}
用队列实现栈 代码如下
class MyStack {private QueueInteger qu1;private QueueInteger qu2;public MyStack() {qu1 new LinkedList();qu2 new LinkedList();}/*** 添加元素将要添加的元素放入不为空的栈里面* param x*/public void push(int x) {if(!qu1.isEmpty()){//如果qu1不为空那就插入元素qu1.offer(x);}else if(!qu2.isEmpty()){//如果qu2不为空那就插入元素qu2.offer(x);}else{//第一次插入的时候两个都为空的时候那就指定队列插入元素qu1.offer(x);}}/*** 弹出元素* return*/public int pop() {if (empty()){return -1;}if(!qu1.isEmpty()){int size qu1.size();for (int i 0; i size - 1; i) {int val qu1.poll();qu2.offer(val);}return qu1.poll();}if(!qu2.isEmpty()){int size qu2.size();for (int i 0; i size - 1; i) {int val qu2.poll();qu1.offer(val);}return qu2.poll();}return -1;}public int top() {if (empty()){return -1;}if(!qu1.isEmpty()){int val 0;//要记录这个size 不然当出一个元素的时候这个函数都会变化得到的值也会变化int size qu1.size();for (int i 0; i size; i) {val qu1.poll();qu2.offer(val);}return val;}if(!qu2.isEmpty()){int val 0;int size qu2.size();for (int i 0; i size; i) {val qu2.poll();qu1.offer(val);}return val;}return -1;}public boolean empty() {return qu1.isEmpty() qu2.isEmpty();}
}用栈实现队列 栈 的特性是先进后出。也就是说第一个入栈的数据将是最后一个出栈我们利用两个栈来实现这题。 代码如下
class MyQueue {StackInteger stack1;StackInteger stack2;public MyQueue() {stack1 new Stack();stack2 new Stack();}public void push(int x) {stack1.push(x);}public int pop() {if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {// 防止 别人一开始 就调用 peek所以 peek 也需要 写 stack1 导入 stack2 的程序if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {// 如果模拟的队列 将全部数据出队那么 stack1 和 stack2 都为空return stack1.isEmpty() stack2.isEmpty();}
}
