本文旨作于收集整理使用！！

导航

• Java数据结构算法（一）链表
• Java数据结构算法（三）树
• Java数据结构算法（四）图
• Java数据结构算法（五)排序
• ......

一、栈

允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不含任何数据元素的栈称为空栈。栈又称为后进先出或先进后出的线性表。
如下图所示，我们在容器最顶端的位置称为栈顶，每放入一个数字我们称之为入栈，入栈的数字就处在栈顶。每弹出一个数字我们称之为出栈，而之前的数就处于栈顶了。
换个角度，我们经常使用手机浏览器浏览网页，我们每点击浏览一个网页，那么就相当于入栈，系统会展示栈顶的页面，我们点击返回则相当于出栈，系统显示之前入栈的界面，当然这个界面现在也已经处于栈顶额。

栈的应用：无处不在的撤销操作、程序调用的系统栈、括号/符号匹配等。

1、使用数组实现栈

import java.util.Arrays;

public class ArrayStack<E> {

   private int size;
   private int top;
   private E[] data;


   public ArrayStack(int capacity) {
       if (size<=0){
           throw new IllegalArgumentException("capacity can't number=0");
       }else {
           data=(E[]) new Object[capacity];
           size=capacity;
           top=-1;
       }
   }

   public ArrayStack() {
       data=(E[]) new Object[10];
       size=10;
       top=-1;
   }

   public void push(E e){
       //判断数组是否需要扩容
       isGrow(top+1);
       data[++top]=e;
   }

   public void pop(){
       if (size>=0){
           data[top]=null;
           top--;
       }else {
           throw new IllegalArgumentException("pop failed. no data");
       }
   }

   public E peek(){
       E e=null;
       if (size>=0){
           e=data[top];
       }else {
           throw new IllegalArgumentException("No elements are available！");
       }
       return e;
   }

    /**
    * 对数组实现动态扩容，若数组容量不够，理论上直接将容量扩展一倍
    * @param minCapacity 入栈后数组长度容量
    */
   private void isGrow(int minCapacity) {
       int capacity=size;
       int newCapacity=0;
       if (capacity<=minCapacity){
           if ((capacity<<1)>Integer.MAX_VALUE){
               newCapacity=Integer.MAX_VALUE;
           }else {
               newCapacity=(capacity<<1);
           }
           this.size=newCapacity;
           Arrays.copyOf(data,newCapacity);
       }
   }
}

2、使用链表实现栈

链表实现方式也很简单，我么直接使用第一章实现的栈！

public class LikeListStack<E> {
    private SingleLinkedList<E> stack;

    public LikeListStack() {
        stack=new SingleLinkedList<>();
    }

    public void push(E e){
        stack.addLast(e);
    }

    //暂时将SingleLinkedList中的size设置为public，为了严禁可以提供get方法访问
    public void pop(){
        stack.remove(stack.size-1);
    }

    public E peek(){
        E e = stack.getLast();
        return e;
    }
}

二、队列

队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列则是一种先进先出原则。

队列的应用：任务执行顺序调度（如打印队列）、模拟现实世界中的队列（如排队等）、异步数据传输等。

队列的实现也可以用数组和链表实现。

2.1、循环队列（数组实现）

public class LoopQueue<E> {
    private int maxsize;
    private int front;
    private int rear;
    private E[] data;
    private int nItems;

    //循环队列必须制定队列的长度
    public LoopQueue(int maxsize) {
        if (maxsize<=0){
            throw new IllegalArgumentException("maxsize can't number=0");
        }else {
            this.maxsize = maxsize;
            data= (E[]) new Object[maxsize];
            front=0;
            rear=-1;
            nItems=0;
        }
    }

    public void insert(E e){
        if (!isFull()){
            if (rear==maxsize-1){
               rear=0;
            }
            data[++rear]=e;
            nItems++;
        }
    }

    public void remove(){
        if (nItems<=0){
            throw new IllegalArgumentException("No elements are available！");
        }else {
            data[front]=null;
            front++;
        }
        if (front==maxsize){
            front=0;
        }
        nItems--;
    }

    public boolean isFull(){
        return maxsize==nItems;
    }
}

2.2、单向队列（链表实现）

当然我们也可以扩展，只能在尾部删除头部插入，下面只实现头部删除尾部插入的操作。

public class singleQueue<E> {
    private SingleLinkedList<E> queue;

    public singleQueue() {
        queue=new SingleLinkedList<>();
    }

    public void insert(E e){
        queue.addLast(e);
    }

    public void remove(){
        queue.remove(0);
    }

    //.......
}