栈和队列的基本实现

一、栈

1、栈是一种只能从一端（栈 顶）插入元素和取出元素的线性结构。

2、特点：先进后出，后进先出。最先添加的在栈 底，最先出栈的在栈 顶。

添加和删除元素都在栈顶。

3、栈的基本操作

（1）向当前栈中添加元素

push (E , e)

public class Stack<E> {
    private int size;  //当前栈的元素个数
    private List<E> data=new ArrayList<>();// 实际存储数据的动态数组，此时在栈中只能在数组末尾添加和删除元素
    public void push(E val){
        data.add(val);
        size++;
    }
     public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < size; i++) {
            sb.append(data.get(i));
            if (i != size - 1) {
                // 还没到数组末尾
                sb.append(", ");
            }
        }
        sb.append("] top");
        return sb.toString();
    }
}

（2）查看当前的栈顶元素

peek( ) 

public E peek(){
        if (isEmpty()) {
            throw new NoSuchElementException("stack is empty!cannot peek");
        }
        return data.get(size - 1);
    }
 private boolean isEmpty() {
        return size == 0;
    }

 （3）弹出当前的栈顶元素 

pop( )

public E pop() {
        if (isEmpty()) {
            // 栈为空无法弹出
            throw new NoSuchElementException("stack is empty!cannot pop!");
        }
        E val = data.remove(size - 1);  //删除数组的最后一个元素（即栈顶元素）
        size --;
        return val;
    }

 二、队列

（1）队列是只能在一端（队尾）添加元素，在一端（队首）删除元素的线性表。

（2）特点：先进先出，后进后出

入队顺序为12345，出队顺序也是12345。

（3）队列也是基于数组/链表，但在对队列进行出队操作时，只能在队列头部进行，若采用数组的方案，每次出队一个元素，就需要移动剩下的所有元素，较为复杂。因此队列更适合采用链表来实现。 

（4）基于链表实现的队列

/**基于链表实现的普通队列**/
public  class LinkedQueue<E> implements Queue<E> {
    //当前队列中的元素个数
    private int size;
    // 当前队列的队首元素
    private Node<E> head;
    // 当前队列的尾部元素
    private Node<E> tail;
    @Override
    public boolean isEmpty() {
        return size==0;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty!cannot peek!");
        }
        return head.val;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            throw new NoSuchElementException("queue is empty!cannot poll!");
        }
        // 删除当前的队首元素，即head
        E val = head.val;
        Node<E> node = head;
        head = head.next;
        node.next = node = null;
        size --;
        return val;
    }

    @Override
    public void offer(E val) {
        Node<E> node=new Node<>(val);
        //链表为空时，即是头结点也是尾结点
        if(head==null){
            head=tail=node;
        }else{
            //链表的尾插
            tail.next=node;
            tail=node;  //尾插后，node成为新的尾结点
        }
        size++;
    }
    //覆写toString方法，打印队列
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("front [");
        for (Node x = head;x != null;x = x.next) {
            sb.append(x.val);
            if (x.next != null) {
                sb.append(", ");
            }
        }
        sb.append("] tail");
        return sb.toString();
    }
}

（5）基于整型实现的循环队列

public abstract class LoopQueue implements Queue<Integer> {
    private Integer[] data;
    private int head;
    private int tail; //指向队尾元素的下一个索引
    public LoopQueue(int size){
        //循环队列中要浪费一个空间，判断元素是否已满
        data=new Integer[size+1];
    }

    @Override
    public void offer(Integer val) {
        if(isFull()){
            throw new ArrayIndexOutOfBoundsException("Loop is full,can not offer");
        }
        data[tail]=val;
        tail=(tail+1)%data.length;
    }

    @Override
    public Integer poll() {
        if(isEmpty()){
            throw new NoSuchElementException("LoopQueue is empty,can not offer");
        }
        //将队首元素出队
        Integer val=data[head];
        head=(head+1)%data.length;  //队首元素出队后，队首向后移动一个单位
        return val;
    }

    @Override
    public Integer peek() {
        if(isEmpty()){
            throw new NoSuchElementException("LoopQueue is empty,can not peek");
        }
        return data[head];
    }

    @Override
    public boolean isEmpty() {
        return head==tail;
    }

    public boolean isFull(){
        return (tail + 1) % data.length == head;
    }

    public String toString(){
        StringBuilder sb=new StringBuilder();
        sb.append("front [");
        //tail=0时，最后一个元素就在数组末尾，否则，最后一个元素的索引为tail-1
        int lastIndex=tail==0?data.length-1:tail-1;
        for(int i=head;i!=tail;){
            sb.append(data[i]);
            if(i!=lastIndex){
                sb.append(",");
            }
            i=(i+1)%data.length;
        }
        sb.append("] tail");
        return sb.toString();
    }
}