链表相比队列最大的不同依然在于链表的插入比较省时间,但是全局操作来看还是数组很省时间,因为链表的构建和连接代价比数组的创建要高很多。
由于队列不再是头插头删了,所以需要维护一个尾指针进行尾插头删
基本结构如下
private Node head; //head using for delete before private Node tail; //tail using of insert after
然后是入队操作
public void enqueue(String str) { Node newNode = new Node(str); if (isEmpty()) { head = newNode; tail = newNode; } else { tail.next = newNode; tail = newNode; } }
然后是出队操作
public String dequeue() { String deItem; if (!isEmpty()) { deItem = head.item; head = head.next; return deItem; } else return "Queue is empty"; }
public boolean isEmpty() { return head == null; }
size
public int size() { int size = 0; while (head != null) { head = head.next; size++; } return size; }