上海营销型网站制作,湖北专业网站制作公司,最贵网站建设报价,廉江网站建设目录
1.概念
2.队列的使用
3.队列模拟实现
4.循环队列
5.双端队列
6.OJ题
6.1 用队列实现栈
6.2 用栈实现队列 1.概念
#xff08;1#xff09;队列是只允许在一端进行插入数据操作#xff0c;在另一端进行删除数据操作的特殊线性表#xff1b;
#xff08;21队列是只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表
2队列具有先进先出后进后出的特点
3入队列进行插入操作的一端称为队尾 出队列进行删除操作的一端称为队头
2.队列的使用
在java中Queue是个接口底层是通过链表实现的其常用方法如下
方法功能boolean offer(E e)入队列E poll()出队列peek()获取队头元素int size()获取队列中有效元素的个数boolean isEmpty()检测队列是否为空
3.队列模拟实现
1包类关系 2TestMyQueue
package TestMyQueue;import TestMyStack.EmptyException;public class MyQueue {// 使用单链表实现队列static class Node{public int val;public Node next;public Node(int val){this.val val;}}public Node head;public Node last;public int usedSize;public void offer(int val){Node newNode new Node(val);if(head null){head newNode;last newNode;}else{last.next newNode;last newNode;usedSize;}}public int poll(){if(isEmpty()){throw new EmptyException();}int ret head.val;head head.next;return ret;}public boolean isEmpty(){return usedSize 0;}public int peek(){if(isEmpty()){throw new EmptyException();}int ret head.val;return ret;}public int getUseSize(){return usedSize;}
} 3EmptyException
package TestMyQueue;public class EmptyException extends RuntimeException{public EmptyException(){}
}
4.循环队列
题目链接622. 设计循环队列 - 力扣LeetCode 代码
class MyCircularQueue {private int[] elem;private int front; // 表示队列的头private int rear; // 表示队列的尾public MyCircularQueue(int k) {this.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 (rear0)?elem.length-1:rear-1;return elem[index];}public boolean isEmpty() {return front rear;}public boolean isFull() {// 写法1
// if( (rear1) % elem.length front){
// return true;
// }
// return false;// 写法2return (rear1)% elem.length front;}
}
5.双端队列
双端队列是指允许两端都可以进行入队和出队操作的队列
Deque是一个接口使用时必须创建其实现类类的对象 常用的实现类为ArrayDeque由数组实现的双端队列和LinkedList由双向链表实现的双端队列故而实例化Deque的方式有以下两种 // 链式双端队列DequeInteger deque new LinkedList();// 数组双端队列DequeInteger deque2 new ArrayDeque();
注也可以使用Deque实现顺序栈
实际上以下写法
StackInteger stack new Stack();
即直接使用Stack类实例化栈对象是很少用的可以使用ArrayDeque创建顺序栈对象
DequeInteger stack2 new ArrayDeque();
6.OJ题
6.1 用队列实现栈
题目链接225. 用队列实现栈 - 力扣LeetCode
解题思路使用两个队列实现栈元素入栈至不为空的队列元素出栈在不为空的队列出栈size-1个元素最后余下的元素就是要出栈的元素如果两个队列均为空则入第一个队列
代码
public class MyStack {private QueueInteger queue1;private QueueInteger queue2;public MyStack() {queue1 new LinkedList();queue2 new LinkedList();}public void push(int x) {if(!queue1.isEmpty()){queue1.offer(x);}else if(!queue2.isEmpty()){queue2.offer(x);}else{queue1.offer(x);}}public int pop() {if(empty()){// 当前栈为空return -1;}if(!queue1.isEmpty()){int size queue1.size();for(int i0;isize-1;i){//for(int i0;iqueue1.size()-1;i){ //写法错误,poll会导致size变化int ret queue1.poll();queue2.offer(ret);}return queue1.poll();}else{int size queue2.size();for(int i0;isize-1;i){int ret queue2.poll();queue1.offer(ret);}return queue2.poll();}}public int top() {if(empty()){return -1;}if(!queue1.isEmpty()){int size queue1.size();int ret -1;for(int i0;isize;i){ret queue1.poll();queue2.offer(ret);}return ret;}else{int size queue2.size();int ret -1;for(int i0;isize;i){ret queue2.poll();queue1.offer(ret);}return ret;}}public boolean empty() {return queue1.isEmpty() queue2.isEmpty();}
}
6.2 用栈实现队列
题目链接232. 用栈实现队列 - 力扣LeetCode
解题思路使用两个栈实现队列stack1用于入栈元素当需要出栈元素时若stack2不为空直接出栈stack2栈顶元素如果stack2为空就将stack1的所有元素入栈到stack2中再出栈stack2顶元素即可
代码
class MyQueue {private StackInteger stack1;private StackInteger stack2;public MyQueue() {stack1 new Stack();stack2 new Stack();}public void push(int x) {stack1.push(x);}public int pop() {if(empty()){return -1;}if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(empty()){return -1;}if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.empty() stack2.empty();}
}
