栈与队列

栈的定义

1.栈（stack）是仅限在表尾进行插入和删除的线性表。也被称为先进后出的线性表。其本身就是一个特殊的线性表，其数据元素仍具有线性关系。
2.栈的插入操作叫进栈也叫入栈（push）；删除操作叫出栈或者弹栈（pop），不含任何元素的栈叫空栈。
举个例子：
①1，2，3依次进栈，然后依次弹栈得到的新串为3，2，1
②1进，1出，2进，2出，3进，3出，新串为1，2，3
③1进，2进，2出，3进，3出，1出，新串为2，3，1
3.由于栈的进出操作都没有任何循环语句，都是在栈顶进行操作，所有其时间复杂度为O（1）。
4.栈同样可以使用顺序存储和链式存储实现。

ArrayStack栈的顺序存储

由于栈也是线性表，所以其顺序存储实际上也是在ArrayList基础上实现。
具体接口要实现的方法如下：

public interface Stack<E> extends Iterable<E>{
    public int size();
    public boolean isEmpty();
    public void push(E element);//进栈
    public E pop();//出栈
    public E peek();//判断栈顶元素
    public void clear();
}

栈的线性存储实现：

public class ArrayStack<E> implements Stack<E> {
    private ArrayList<E> list;//栈的内部其实就是有线性表实现
    public ArrayStack(){//创建一个默认容量的栈
        list = new ArrayList<E>();
    }
    public ArrayStack(int capacity){//创建一个指定容量的栈
        list = new ArrayList<>(capacity);
    }
    @Override
    public int size() {
        return list.size();
    }

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

    @Override
    public void push(E element) {
        list.add(element);
    }

    @Override
    public E pop() {
       return list.remove(list.size() - 1);
    }

    @Override
    public E peek() {
        return list.get(list.size() - 1);
    }

    @Override
    public void clear() {
        list.clear();
    }

    @Override
    public Iterator<E> iterator() {
        return list.iterator();
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(String.format("ArrayStack:%d/%d[",list.size(),list.getCapacity()));
        if (isEmpty()) {
            sb.append(']');
        }
        else{
            for (int i = 0; i < list.size();i++){
                sb.append(list.get(i));
                if (i != list.size() - 1){
                    sb.append(',');
                }else {
                    sb.append(']');
                }
            }
        }
        return sb.toString();
    }
}

应用： 十进制转十六进制的问题（利用栈解决）：

public class DecToHex {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);//获取用户输入
        System.out.println("请输入：");
        int number  = scanner.nextInt();
        ArrayStack<Character> stack = new ArrayStack<>();//创建一个栈存储余数，作为进栈的数据元素
        //计算余数
        int mod = 0;
        while (number != 0) {
            mod = number % 16;
            //获取余数  0~9 用数字表示，10~15用A~F表示
            // '0' + mod表示字符0往后第mod个字符的编码，表示以字符表示的数字
            // 'A' + mod - 10表示字符A往后mod-10个字符的编码，表示以编码表示的字母，这里用作16进制计数
            if (mod < 10) {
                stack.push((char) ('0' + mod));
            }else {
                stack.push((char) ('A' + mod - 10));
            }
            number /= 16;
        }
        while (!stack.isEmpty()){
            System.out.print(stack.pop());
        }
    }
}