1.栈（stack）

 栈是后进先出的（LIFO） 策略的集合类型。

基本API

• push(item) 添加一个元素

• item pop(item)) 删除并返回一个元素

• isEmpty 栈是否为空

• size 栈中的元素数量

让我们创建一个用数组来实现栈的代码，并且支持可变数组大小 而且使用率永远不低于1/4

package com.qing.algorithms;

//一个可变的数组实现栈的方法
public class FixedCapacityStack<T> {

    /***
     * 一种表示泛型定容栈的数组实现
     * FixedCapacityStack(int cap) 创建一个容量为cap的空栈
     * push(item) 添加一个元素
     *item pop(item)) 删除并返回一个元素
     * isEmpty 栈是否为空
     * size 栈中的元素数量
     *
     */
    private T[] a;
    private int N = 0; //有效数量

    /***
     *
     * @param cap 最大存储数量
     */
    public FixedCapacityStack(int cap) {

        a = (T[]) new Object[cap];
    }

    public boolean isEmtry() {
        return N == 0;
    }

    //添加
    public void push(T t) {

        //如果数组没有空间 添加两倍数组长度给它
        if (N == a.length) resize(2 * a.length);
        a[N++] = t;//先赋值 然后++

    }

    //推出
    public T pop() {
        if(isEmtry()){
            return null;
        }

        T item = a[--N];//从0开始
        a[N] = null;
        //如果数组太大，只用到1/4的空间，将数组减半 
        if (N > 0 && N == a.length / 4) resize(a.length / 2);
        return item;
    }


    /***
     * 创建一个数组赋值给a
     * @param max
     */
    private void resize(int max) {

        T[] temp = (T[]) new Object[max];

        for (int i = 0; i < N; i++) {
            temp[i] = a[i];
        }

        a = temp;
    }


    public void showStack() {

        StringBuilder sb = new StringBuilder();


        System.out.println("数组大小为 "+ a.length);

        for (int i=0 ;i<N;i++) {

            T item = a[i];

            if (item != null) sb.append(" "+i + item.toString());
            else sb.append(" "+i +"null");
        }

        System.out.println(sb.toString());



    }


    public static void main(String args[]) {

        FixedCapacityStack<String> stack = new FixedCapacityStack<>(2);

        stack.push("a");
        stack.push("b");
        stack.push("c");
        stack.push("d");

        stack.showStack();

        stack.pop();
        stack.pop();
        stack.pop();

        stack.showStack();

    }

}

/**
数组大小为 4
 0a 1b 2c 3d
数组大小为 2
 0a
**/

使用单向链表实现栈代码

为什么使用单向链表？

• 因为单向列表已经满足上面的栈基本api了，但有个缺点，任意位置删除和插入与链表的长度成正比（因为删除的时候要遍历链表来判断是否等于要删除元素），实现任意插入和删除操作应该使用 双向链表

基本数据类型

  private class Node{
        T item; //当前元素
        Node next; //上一个元素 ， 因为后添加压在上面所以取名为next
    }

下面是完整代码

package com.qing.algorithms;

import java.util.Iterator;

/***
 * 使用链表实现的栈
 * 实现Iterable 可遍历
 * @param <T>
 */
public class Stack<T> implements Iterable<T> {

    private Node first; //栈顶(最近添加的元素)
    private int N =0; //元素数量



    private class Node{
        T item;
        Node next;
    }

    public int getSize(){
        return N;
    }

    public boolean isEmpty(){

        return first==null;
    }

    /***
     * 向栈顶添加元素
     * @param item
     */
    public void push(T item){
        Node oldFirst =first;//第一次push first为null
        first = new Node();
        first.item = item;
        first.next = oldFirst; //指向上一个元素
        N++;
    }

    /***
     * 向栈顶删除元素
     */
    public T pop(){

        T item = first.item;
        first =first.next;
        N--;
        return item;
    }


    @Override
    public Iterator<T> iterator() {
        return new StackIterator();
    }



    private class StackIterator implements Iterator<T>{

        private Node current = first;


        @Override
        public boolean hasNext() {
            return current!=null;
        }

        @Override
        public T next() {
            T item = current.item;
            current = current.next;
            return item;
        }

    }

    private void showStack() {

        int i =0;
        StringBuilder sb = new StringBuilder();

        for (T t : this) {
            sb.append("  " + i + t);
            i++;
        }
        System.out.println(sb.toString());
    }


    public static void main(String args[]) {

        Stack<String> stack = new Stack<>();

        stack.push("a");
        stack.push("b");
        stack.push("c");
        stack.push("d");

        stack.showStack();

        stack.pop();
        stack.pop();
        stack.pop();

        stack.showStack();

    }


}

/***
  0d  1c  2b  3a
  0a

**/

1.队列（Queue）

• void enqueue(Item item) 添加一个元素
• Item dequeue() 删除最早添加的元素
• booean isEmtry() 队列是否为null
• int size() 队列中的元素数量