Ex_1_3_29.md

title	date	draft	tags	categories
Algorithm4 Java Solution 1.3.29	2019-07-04 05:47:10 +0800	false	JAVA	TECH archives

1.3.29

Problem:

Write a Queue implementation that uses a circular linked list, which is the same as a linked list except that no links are null and the value of last.next is first whenever the list is not empty. Keep only one Node instance variable (last).

Solution：

use only one instance variable

public static class _Queue<Item> {

    Node tail;

    private class Node {

      public Node(Item item) {
        this.item = item;
      }

      Item item;
      Node next;
    }

    /**
     * insert at last
     */
    public void enqueue(Item item) {
      if (tail == null) {
        tail = new Node(item);
        tail.next = tail;
      } else {
        Node front = tail.next;
        Node n = new Node(item);
        tail.next = n;
        tail = n;
        tail.next = front;
      }
    }

    public void print() {
      Node cur = tail.next;
      while (cur != tail) {
        StdOut.printf("%s->", cur.item);
        cur = cur.next;
      }
      StdOut.println(cur.item);
    }

    public boolean isEmpty() {
      return tail == null;
    }


    /**
     * remove first element in queue
     */
    public Item dequeue() {
      if (tail == tail.next) {
        Item item = tail.item;
        tail = null;
        return item;
      }
      Node front = tail.next;
      Item item = front.item;
      tail.next = front.next;
      return item;
    }
  }

Reference：

circular-queue-array

circular-queue-list

xiaoheigit