网站改版建设的目的,做名片去哪个网站,网站建设与管理题,互联网软件目录 1. 队列概念2. 模拟实现队列2.1 链式队列2.2 循环队列 3. 双端队列4. 队列的应用4.1 用队列实现栈4.2 用栈实现队列 1. 队列概念
队列是一种只能在一端进行插入数据操作#xff0c;另一端进行删除数据操作的数据结构#xff0c;插入数据的叫队尾#xff0c;删除数据的… 目录 1. 队列概念2. 模拟实现队列2.1 链式队列2.2 循环队列 3. 双端队列4. 队列的应用4.1 用队列实现栈4.2 用栈实现队列 1. 队列概念
队列是一种只能在一端进行插入数据操作另一端进行删除数据操作的数据结构插入数据的叫队尾删除数据的叫队头。类似于生活中的排队打饭进入队列中只能从队伍的后面进入出队只能在队头出。队列是一种先进先出的数据结构。
2. 模拟实现队列
队列有链式结构和顺序结构两种Java中的Queue接口底层是链式结构包含方法如下 add和offer表示入队remove和poll表示出队element和peek表示获取队头的元素不删除。
2.1 链式队列
Java的Queue底层是用双向链表实现的所以我们也用双向链表模拟实现
public class MyQueueE {//使用双向链表static class ListNode {public ListNode next;//前驱public ListNode prev;//后继public Object val;//值//构造方法用于初始化public ListNode(Object val) {this.val val;}}public ListNode head;//头public ListNode tail;//尾//入队-只能从尾部入队(尾插)public void offer(E val) {ListNode newNode new ListNode(val);//第一次入队if (tail null) {head tail newNode;return;}tail.next newNode;newNode.prev tail;tail newNode;}//出队-只能从头部出队(头删)public E poll() {if (empty()) {return null;}Object ret head.val;head head.next;head.prev null;return (E) ret;}//获取队头元素public E peek() {if (empty()) {return null;}return (E)head.val;}//判断队列是否为空public boolean empty() {return head null;}}2.2 循环队列
循环队列是使用数组实现的循环队列的结果如图 循环队列的原理 循环队列看似乎结果成环其实底层是连续的数组实现循环的是队头(front)和队尾(rear)两个变量front下标表示队列的第一个元素rear下标则是队尾的下一个位置。队列为空的条件frontrear队列满了的条件rear1%数组长度 front
代码实现
public class round_robinQueueE {public Object[] elem;//数组public int front;//队头public int rear;//队尾//k表示容量public round_robinQueue(int k) {this.elem new Object[k 1];//浪费一个空间,所以申请了k1个空间}//入队一个元素public boolean offer(int value) {//满了不能插if (isFull()) {return false;}elem[rear] value;rear (rear 1) % elem.length;return true;}//出队一个元素public boolean poll() {if (isEmpty()) {return false;}front (front 1) % elem.length;return true;}//获取队头元素public E getFront() {if (isEmpty()) {return null;}return (E) elem[front];}//获取队尾元素public E Rear() {if (isEmpty()) {return null;}//rear指向的是下一个位置,不是最后一个元素,如果rear0,会越界if (rear 0) {return (E) elem[elem.length - 1];}return (E) elem[rear - 1];}public boolean isEmpty() {return front rear;}public boolean isFull() {return (rear 1) % elem.length front;}
}3. 双端队列
双端队列指允许两端都可以进行入队、出队操作的队列Java中可以使用Deque这个接口有顺序实现ArrayDeque和链式实现LinkedList
4. 队列的应用
4.1 用队列实现栈 题目链接用队列实现栈 解题思路 首先只使用一个队列是不行的需要两队列。 实现逻辑 入栈操作将元素放入不为空的队列(如果是第一次入栈两个队列都可以)。出栈操作将不为空的队列中的n-1个元素放入另一个队列中最后将剩下的元素出队。获取栈顶元素将不为空的队列中所有的元素放入另一个队列中返回最后一个元素即可 代码
class MyStack {public QueueInteger q1;public QueueInteger q2;public MyStack() {q1 new LinkedList();q2 new LinkedList();}//入栈public void push(int x) {//如果都为空,在q1中添加if (empty()) {q1.offer(x);return;}if (q1.isEmpty()) {q2.offer(x);} else {q1.offer(x);}}//出栈public int pop() {//如果模拟栈为空,返回if (empty()) {return -1;}if (!q1.isEmpty()) {//q1不为空int size q1.size();for (int i 0; i size - 1; i) {q2.offer(q1.poll());}return q1.poll();} else {int size q2.size();for (int i 0; i size - 1; i) {q1.offer(q2.poll());}return q2.poll();}}//获取栈顶元素
public int top() {//如果模拟栈为空,返回if (empty()) {return -1;}if (!q1.isEmpty()) {//q1不为空int size q1.size();int ret -1;for (int i 0; i size; i) {ret q1.poll();q2.offer(ret);}return ret;} else {int size q2.size();int ret -1;for (int i 0; i size; i) {ret q2.poll();q1.offer(ret);}return ret;}}//判断模拟栈是否为空,如果两个队列都为空则为空public boolean empty() {return q1.isEmpty() q2.isEmpty();}
}4.2 用栈实现队列 题目链接 用栈实现队列 解题思路 使用两个栈实现队列入队和出队的逻辑其中一个栈(s1)只进行入栈操作表示入队列另一个栈(s2)只进行出栈操作表示出队如果s2空了再将s1中所有元素都入s2这个栈
代码
class MyQueue {public StackInteger s1;public StackInteger s2;public MyQueue() {s1 new Stack();s2 new Stack();}public void push(int x) {s1.push(x);}public int pop() {if (empty()) {return -1;}//如果s2为空,把s1的所有元素拿过来if (s2.empty()) {while (!s1.empty()) {s2.push(s1.pop());}}return s2.pop();}public int peek() {if (empty()) {return -1;}//如果s2为空,把s1的所有元素拿过来if (s2.empty()) {while (!s1.empty()) {s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.empty() s2.empty();}
}今天的内容就到这里感谢老铁们的点赞、收藏、评论~❤
