当前位置: 代码迷 >> 综合 >> Queue 链表实现
  详细解决方案

Queue 链表实现

热度:43   发布时间:2023-10-08 19:44:49.0
package com.arithmetic;import java.util.Iterator;
import java.util.NoSuchElementException;/*** 队列* 是一种基于先进先出策略的集合类型,按照任务产生的顺序完成他们的策略** foreach 语句迭代访问队列元素时的顺序。  就是它们加入队列的顺序** 队列链表实现*/
public class Queue<Item> implements Iterable<Item>{// 指向头结点private Node<Item> first;// 指向尾结点private Node<Item> last;private int n;public Queue() {first = null;last = null;n = 0;}boolean isEmpty() {return first == null;}public int size() {return n;}private static class Node<Item> {private Item item;private Node<Item> next;}// 返回但不删除栈顶元素public Item peek() {if (isEmpty()) {throw new NoSuchElementException("queue underflow");}return first.item;}// 增加一个元素到队列中void enqueue(Item item) {Node<Item> oldLast = last;last = new Node<Item>();last.item = item;last.next = null;if (isEmpty()) {first = last;} else {oldLast.next = last;}n++;}// 移除队列一个元素Item dequeue() {if (isEmpty()) {throw new NoSuchElementException("Queue underflow");}Item item = first.item;first = first.next;if (isEmpty()) {last = null;}n--;return item;}@Overridepublic Iterator<Item> iterator() {return new ListIterator<Item>(first);}private class ListIterator<Item> implements Iterator<Item> {private Node<Item> current;public ListIterator(Node<Item> first) {current = first;}public boolean hasNext() {return current != null;}public void remove() {throw new UnsupportedOperationException();}public Item next() {if (!hasNext()) throw new NoSuchElementException();Item item = current.item;current = current.next;return item;}}public static void main(String[] args) {Queue<String> queue = new Queue<String>();queue.enqueue("1");queue.enqueue("2");queue.enqueue("3");Iterator<String> iterator = queue.iterator();while (iterator.hasNext()) {System.out.println(iterator.next());}}
}