目录
队列概念
队列分类
具体实现
队列概念
FIFO在队首出队,队尾入队,是一种先进先出的数据结构。
举例:元素添加1,2, 3,出队顺序按照排队顺序还是1,2,3就比如生活中的排队,先来的人,先站队,先出队。
队列分类基于数组实现的队列——顺序队列
基于链表实现的队列——链式队列
(由于链表是从队尾入队,对手出队若要删除时时间复杂度为O(n),所以一般使用链表队列,尾部插入,头部删除)
基础队列——FIFO
基于优先级的队列——按照优先级大小出队
循环队列——基于数组实现的队列,是一个环状结构
双端队列——可以从两端插入删除
无论哪一种队列,都必须支持三个核心 *** 作——入队(offer)出队(poll)返回队首元素(peek)
因此应当设计队列为接口。
具体实现public interface Queue{ // 设置一个泛型接口,可以接收所有类型 // 入队 void offer(E val); // 出队 E poll() throws NoSuchFieldException; // 返回队首元素 E peek() throws NoSuchFieldException; // 判断队列是否为空 boolean isEmpty(); }
package stack_queue.queue.impl; import stack_queue.queue.Queue; import java.util.NoSuchElementException; public class MyQueueimplements Queue { // 实际存储的链表的每个节点 // 此处属于内部类 成员内部类 private class Node { E val; Node next; public Node(E val) { this.val = val; } } //—————————————————————————————————— // 当前队列的大小 private int size; // 当前队列的队首和队尾 private Node head; private Node tail; @Override public void offer(E val) { // 建立新节点入队 *** 作 Node node = new Node(val); if (head == null) { head = tail = node; } else { // 不为空,尾插 tail.next = node; tail = node; } size++; } @Override public E poll() { if (isEmpty()) { throw new NoSuchElementException("queue is empty cannot poll!"); } E val = head.val; // 更新头节点,头删 Node node = head; head = head.next; node.next = null; size--; return val; } @Override public E peek() { if (isEmpty()) { throw new NoSuchElementException("queue is empty cannot peek!"); } return tail.val; } @Override public boolean isEmpty() { return size == 0; } @Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("front ["); // 链表的遍历 for (Node x = head; x != null; x = x.next) { sb.append(x.val); if (x.next != null) { // 还没走到链表尾部 sb.append(", "); } } sb.append("]"); return sb.toString(); } }
package stack_queue.queue; import stack_queue.queue.impl.MyQueue; public class QueueTest { public static void main(String[] args){ Queuequeue = new MyQueue<>(); queue.offer(1); queue.offer(3); queue.offer(5); while(!queue.isEmpty()){ System.out.println(queue.poll()); } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)