实现链表_链表实现栈和队列_3

之前用数组实现栈和队列，虽然有resize操作，但是其实还是静态数组，不是真正的动态。
当我们用链表实现栈和队列的时候，才是真正动态扩展。

LinkedQueue

package com.company.linkedlist.DummyHeadLinkedList;

import com.company.queue.Queue;
import org.omg.PortableInterceptor.INACTIVE;

/**
 * @program: Array
 * @description: 链表队列
 * @author: Gu
 * @create: 2019-04-17 22:43
 **/

public class LinkedQueue<E> implements Queue<E> {

    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }
    }

    private Node head;
    private Node tail;
    private int size;

    public LinkedQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    //此方法和之前稍微不同
    @Override
    public void enqueue(E e) {
        if (tail == null) {
            tail = new Node(e);
            head = tail;
        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException("linkedQueue为空");
        }
        Node resNoew = head;
        if (resNoew.next != null) {
            Node cur = resNoew.next;
            resNoew.next = cur.next;
            cur = null;
            size--;
        } else {
            head = null;
        }
        return resNoew.e;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException("linkedQueue为空");
        }
        return head.e;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("Queue: head ");

        Node cur = head;
        while (cur != null) {
            stringBuilder.append(cur.e);
            stringBuilder.append("->");
            cur = cur.next;
        }
        stringBuilder.append("NULL tail");
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        LinkedQueue<Integer> linkedQueue = new LinkedQueue<>();
        for (int i = 0; i < 10; i++) {
            linkedQueue.enqueue(i);
            System.out.println(linkedQueue);
            if (i % 3 == 2) {
                linkedQueue.dequeue();
                System.out.println(linkedQueue);
            }
        }
    }
}

LinkedStack

package com.company.linkedlist.DummyHeadLinkedList;

import com.company.stack.Stack;

import java.io.File;

/**
 * @program: Array
 * @description: 链表实现栈
 * @author: Gu
 * @create: 2019-04-17 22:07
 **/

public class LinkedStack<E> implements Stack<E> {
    private LinkedList linkedList;
    private int size;

    public LinkedStack() {
        this.linkedList = new LinkedList();
        this.size = 0;
    }

    public int getSize() {
        return linkedList.getSize();
    }

    @Override
    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public void push(E e) {
        linkedList.addFrist(e);
    }

    @Override
    public E pop() {
        return (E)linkedList.removeFrist();
    }

    @Override
    public E peek() {
        return (E)linkedList.getFrist();
    }

    @Override
    public String toString() {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append(String.format("栈的size：%d \n", getSize()));
        stringBuffer.append("top [");
        while (getSize() != 0) {
            stringBuffer.append(pop());
            if (getSize() == 0) {
                stringBuffer.append("]");
                break;
            }
            stringBuffer.append(",");
        }

        return stringBuffer.toString();
    }

    public static void main(String[] args) {
        LinkedStack<Integer> linkedStack = new LinkedStack<>();
        for (int i = 0; i < 5; i++) {
            linkedStack.push(i);
        }
        System.out.println(linkedStack);
    }

}