数据结构-栈和队列

栈和队列是一种更高级的线性数据结构。

栈的特性是后进先出，底层可以基于数组实现，也可以基于链表实现。

public class EArrayStack {

    private T[] data;
    private int size;

    public EArrayStack(int capacity) {
        data = (T[])new Object[capacity];
        this.size = 0;
    }

    public void push(T e) {
        if (size == data.length) {
            throw new InternalException("stack has been full.");
        }
        data[size] = e;
        size ++;
    }

    public T pop() {
        if (size == 0) {
            throw new InternalException("stack empty");
        }
        T popElem = data[size - 1];
        size --;
        return popElem;
    }

    public T peek() {
        if (size == 0) {
            throw new InternalException("stack empty");
        }
        return data[size - 1];
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[ ");
        for (int i = 0;i < size;i ++) {
            sb.append(data[i]);
            if (i != size - 1) {
                sb.append(" -> ");
            }
        }
        sb.append(" ]");
        return sb.toString();
    }

    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(10);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack);
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack);
    }

}

在基于链表实现的栈中，利用dummyHead在头节点出进行操作，就很容易实现O(1)的入栈和出栈。

public class ELinkedStack {
    
    private Node dummyHead;
    private int size;

    public ELinkedStack() {
        dummyHead = new Node<>();
        this.size = 0;
    }

    //将新增节点插入到头节点的位置
    public void push(T e) {
        Node newNode = new Node(e);
        newNode.next = dummyHead.next;
        dummyHead.next = newNode;
        size ++;
    }

    //从头节点弹出数据
    public T pop() {
        if (size == 0) {
            throw new InternalException("stack is empty");
        }
        Node delNode = dummyHead.next;
        dummyHead.next = delNode.next;
        delNode.next = null;
        size --;
        return delNode.data;
    }

    public T peek() {
        if (size == 0) {
            throw new InternalException("stack is empty");
        }
        return dummyHead.next.data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        Node cur = dummyHead.next;
        while (cur != null) {
            sb.append(cur.data);
            if (cur.next != null) {
                sb.append(" -> ");
            }
            cur = cur.next;
        }
        sb.append(" ]");
        return sb.toString();
    }

    private static class Node {
        T data;
        Node next;

        public Node() {
            this(null);
        }

        public Node(T data) {
            this(data, null);
        }
        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        LinkedStack stack = new LinkedStack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println(stack);
        System.out.println(stack.peek());
        System.out.println(stack);
        System.out.println(stack.pop());
        System.out.println(stack);
    }
}

队列也是一个线性数据结构，所以底层也可以通过数组或链表实现。

public class EArrayRQueue {

    private E[] data;
    private int size;
    
    private int front;
    private int end;
    
    //初始化
    public EArrayRQueue(int capacity) {
        data = (E[]) new Object[capacity];
        front = 0;
        end = 0;
    }
    
    public void enqueue(E e) {
        if ((end + 1) % data.length == front) {
            throw new IllegalArgumentException("queue is full");
        }
        data[end] = e;
        end = (end + 1) % data.length;
        size ++;
    }

    public E dequeue() {
        if (end == front) {
            throw new IllegalArgumentException("queue is empty.");
        }
        E dequeueEle = data[front];
        front = (front + 1) % data.length;
        size --;
        return dequeueEle;
    }

    public boolean isEmpty() {
        return front == end;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        for (int i = front;
             i != end; i = (i + 1) % data.length) {
            sb.append(data[i]);
            sb.append(" <- ");
        }
        sb.append("]");
        return sb.toString();
    }

    public static void main(String[] args) {
        
        EArrayRQueue queue = new EArrayRQueue(4);
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println(queue);
        System.out.println(queue.dequeue());
        System.out.println(queue);
        queue.enqueue(10);
        System.out.println(queue);
        System.out.println(queue.isEmpty()  );
    }
}

由于队列是一边进另一边出，所以利用dummyHead在头节点执行出对，在尾节点利用一个tail指针进行入队操作，这样入队和出队都可以将时间复杂度控制在O(1)。

public class ELinkedQueue {

    private Node dummyHead;
    private Node tail;
    private int size;

    public ELinkedQueue() {

        
        dummyHead = new Node<>();
        tail = dummyHead;
        //dummyHead.next = tail;
        size = 0;
    }

    
    public void enqueue(T e) {
        //利用last指针添加到尾部
        Node newNode = new Node<>(e);
        newNode.next = tail.next;
        tail.next = newNode;
        tail = newNode;
        size ++;
    }

    
    public T dequeue() {
        if (size == 0) {
            throw new InternalException("queue is empty.");
        }
        //出队，利用dummyHead直接移除头节点
        Node delNode = dummyHead.next;
        dummyHead.next = delNode.next;
        delNode.next = null;
        size -- ;
        return delNode.data;
    }

    public boolean isEmpty() {
        return dummyHead.next == null;
    }

    public T peek() {
        if (size == 0) {
            throw new InternalException("queue is empty.");
        }
        return dummyHead.next.data;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        Node cur = dummyHead.next;
        while (cur != null) {
            sb.append(cur.data);
            if (cur.next != null) {
                sb.append(" <- ");
            }
            cur = cur.next;
        }
        sb.append(" ]");
        return sb.toString();
    }
    
    private class Node {
        T data;
        Node next;

        public Node() {
            this(null);
        }

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

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    public static void main(String[] args) {

        

        LinkedRQueue queue = new LinkedRQueue<>();
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        System.out.println(queue);
        System.out.println(queue.dequeue());
        System.out.println(queue.peek());
        System.out.println(queue);
        queue.enqueue(100);
        System.out.println(queue);
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.dequeue());
        System.out.println(queue.isEmpty());
    }
}

利用一个双向链表和一个dummyHead以及一个dummuTail就能够轻松实现一个双端队列，并且在头尾入队和出队的操作的时间复杂度都是O(1)。

public class ELinkedDeque {

    //定义两个dummyHead
    private Node dummyHead;
    private Node dummyTail;
    private int size;

    public ELinkedDeque() {
        //初始状态，两个dummyNode互指
        dummyHead = new Node<>();
        dummyTail = new Node<>();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
        size = 0;
    }

    
    public void addFirst(T e) {
        Node newNode = new Node<>(e);
        newNode.next = dummyHead.next;
        newNode.prev = dummyHead;
        dummyHead.next.prev = newNode;
        dummyHead.next = newNode;
        size ++;
    }

    
    public T removeFirst() {
        if (dummyHead.next == dummyTail) {
            throw new IllegalArgumentException("queue is empty");
        }
        Node delNode = dummyHead.next;
        dummyHead.next = delNode.next;
        delNode.next.prev = dummyHead;
        delNode.next = null;
        delNode.prev = null;
        size --;
        return delNode.data;
    }

    
    public void addLast(T e) {
        Node newNode = new Node<>(e);
        newNode.prev = dummyTail.prev;
        newNode.next = dummyTail;
        dummyTail.prev.next = newNode;
        dummyTail.prev = newNode;
        size ++;
    }

    
    public T removeLast() {
        if (dummyHead.next == dummyTail) {
            throw new IllegalArgumentException("queue is empty");
        }
        Node delNode = dummyTail.prev;
        dummyTail.prev = delNode;
        delNode.prev.next = delNode.next;
        delNode.prev = null;
        delNode.next = null;
        size --;
        return delNode.data;
    }

    public boolean isEmpty() {
        return dummyHead.next == dummyTail;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        Node cur = dummyHead.next;
        while (cur != dummyTail) {
            sb.append(cur.data);
            if (cur.next != dummyTail) {
                sb.append(" <- ");
            }
            cur = cur.next;
        }
        sb.append(" ]");
        return sb.toString();
    }

    //双向链表节点定义
    private class Node {
        private T data;
        private Node prev;
        private Node next;

        public Node() {
            this(null);
        }

        public Node(T data) {
            this(data, null, null);
        }
        public Node(T data, Node prev, Node next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

    public static void main(String[] args) {
        
        ELinkedDeque deque = new ELinkedDeque<>();
        deque.addFirst(1);
        deque.addFirst(2);
        deque.addLast(-1);
        System.out.println(deque);
        System.out.println(deque.removeFirst());
        System.out.println(deque);
        System.out.println(deque.removeLast());
        System.out.println(deque);
        System.out.println(deque.removeFirst());
        System.out.println(deque.isEmpty());
    }
}