java 实现数据结构之队列
浏览数：37 /
时间：2015年06月08日
队列是一种特殊的线性表，它只允许在表的前端(front)进行删除操作，只允许在表的后端（rear）进行插入操作。
1.队列的顺序存储结构及实现
public class SequenceQueue<T> { private int DEFAULT_SIZE = 10; //保存数组的长度。 private int capacity; //定义一个数组用于保存顺序队列的元素 private Object[] elementData; //保存顺序队列中元素的当前个数 private int front = 0; private int rear = 0; //以默认数组长度创建空顺序队列 public SequenceQueue() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //以一个初始化元素来创建顺序队列 public SequenceQueue(T element) { this(); elementData[0] = element; rear++; } /** * 以指定长度的数组来创建顺序队列 * @param element 指定顺序队列中第一个元素 * @param initSize 指定顺序队列底层数组的长度 */ public SequenceQueue(T element , int initSize) { this.capacity = initSize; elementData = new Object[capacity]; elementData[0] = element; rear++; } //获取顺序队列的大小 public int length() { return rear - front; } //插入队列 public void add(T element) { if (rear > capacity - 1) { throw new IndexOutOfBoundsException("队列已满的异常"); } elementData[rear++] = element; } //移除队列 public T remove() { if (empty()) { throw new IndexOutOfBoundsException("空队列异常"); } //保留队列的rear端的元素的值 T oldValue = (T)elementData[front]; //释放队列的rear端的元素 elementData[front++] = null; return oldValue; } //返回队列顶元素，但不删除队列顶元素 public T element() { if (empty()) { throw new IndexOutOfBoundsException("空队列异常"); } return (T)elementData[front]; } //判断顺序队列是否为空队列 public boolean empty() { return rear == front; } //清空顺序队列 public void clear() { //将底层数组所有元素赋为null Arrays.fill(elementData , null); front = 0; rear = 0; } public String toString() { if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (int i = front ; i < rear ; i++ ) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } } }
2.循环队列（顺序结构存储实现）
import java.util.Arrays; public class LoopQueue<T> { private int DEFAULT_SIZE = 10; //保存数组的长度。 private int capacity; //定义一个数组用于保存循环队列的元素 private Object[] elementData; //保存循环队列中元素的当前个数 private int front = 0; private int rear = 0; //以默认数组长度创建空循环队列 public LoopQueue() { capacity = DEFAULT_SIZE; elementData = new Object[capacity]; } //以一个初始化元素来创建循环队列 public LoopQueue(T element) { this(); elementData[0] = element; rear++; } /** * 以指定长度的数组来创建循环队列 * @param element 指定循环队列中第一个元素 * @param initSize 指定循环队列底层数组的长度 */ public LoopQueue(T element , int initSize) { this.capacity = initSize; elementData = new Object[capacity]; elementData[0] = element; rear++; } //获取循环队列的大小 public int length() { if (empty()) { return 0; } return rear > front ? rear - front : capacity - (front - rear); } //插入队列 public void add(T element) { if (rear == front && elementData[front] != null) { throw new IndexOutOfBoundsException("队列已满的异常"); } elementData[rear++] = element; //如果rear已经到头，那就转头 rear = rear == capacity ? 0 : rear; } //移除队列 public T remove() { if (empty()) { throw new IndexOutOfBoundsException("空队列异常"); } //保留队列的rear端的元素的值 T oldValue = (T)elementData[front]; //释放队列的rear端的元素 elementData[front++] = null; //如果front已经到头，那就转头 front = front == capacity ? 0 : front; return oldValue; } //返回队列顶元素，但不删除队列顶元素 public T element() { if (empty()) { throw new IndexOutOfBoundsException("空队列异常"); } return (T)elementData[front]; } //判断循环队列是否为空队列 public boolean empty() { //rear==front且rear处的元素为null return rear == front && elementData[rear] == null; } //清空循环队列 public void clear() { //将底层数组所有元素赋为null Arrays.fill(elementData , null); front = 0; rear = 0; } public String toString() { if (empty()) { return "[]"; } else { //如果front < rear，有效元素就是front到rear之间的元素 if (front < rear) { StringBuilder sb = new StringBuilder("["); for (int i = front ; i < rear ; i++ ) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } //如果front >= rear，有效元素为front->capacity之间、0->front之间的 else { StringBuilder sb = new StringBuilder("["); for (int i = front ; i < capacity ; i++ ) { sb.append(elementData[i].toString() + ", "); } for (int i = 0 ; i < rear ; i++) { sb.append(elementData[i].toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } } } }
3.队列的链式存储结构及实现
public class LinkQueue<T> { //定义一个内部类Node，Node实例代表链队列的节点。 private class Node { //保存节点的数据 private T data; //指向下个节点的引用 private Node next; //无参数的构造器 public Node() { } //初始化全部属性的构造器 public Node(T data , Node next) { this.data = data; this.next = next; } } //保存该链队列的头节点 private Node front; //保存该链队列的尾节点 private Node rear; //保存该链队列中已包含的节点数 private int size; //创建空链队列 public LinkQueue() { //空链队列，front和rear都是null front = null; rear = null; } //以指定数据元素来创建链队列，该链队列只有一个元素 public LinkQueue(T element) { front = new Node(element , null); //只有一个节点，front、rear都指向该节点 rear = front; size++; } //返回链队列的长度 public int length() { return size; } //将新元素加入队列 public void add(T element) { //如果该链队列还是空链队列 if (front == null) { front = new Node(element , null); //只有一个节点，front、rear都指向该节点 rear = front; } else { //创建新节点 Node newNode = new Node(element , null); //让尾节点的next指向新增的节点 rear.next = newNode; //以新节点作为新的尾节点 rear = newNode; } size++; } //删除队列front端的元素 public T remove() { Node oldFront = front; front = front.next; oldFront.next = null; size--; return oldFront.data; } //访问链式队列中最后一个元素 public T element() { return rear.data; } //判断链式队列是否为空队列 public boolean empty() { return size == 0; } //清空链队列 public void clear() { //将front、rear两个节点赋为null front = null; rear = null; size = 0; } public String toString() { //链队列为空链队列时 if (empty()) { return "[]"; } else { StringBuilder sb = new StringBuilder("["); for (Node current = front ; current != null ; current = current.next ) { sb.append(current.data.toString() + ", "); } int len = sb.length(); return sb.delete(len - 2 , len).append("]").toString(); } } }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
