一、栈

1.1 栈的实现

栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。java没有栈这样的数据结构，如果想利用先进后出（FILO）这样的数据结构，就必须自己实现。要实现Stack，至少应该包括：

• pop() 出栈操作，弹出栈顶元素。
• push(E e) 入栈操作
• peek() 查看栈顶元素
• isEmpty()栈为空

另外，实现一个栈，还应该考虑到几个问题：

• 栈的初始大小以及栈满以后如何新增栈空间
• 对栈进行更新时需要进行同步
  （转自：https://segmentfault.com/a/1190000002516799）

有三种实现：
实现一：数组实现

package cn.list;
import java.util.EmptyStackException;

public class MyArrayStack {
    private int[] array;// 用数组实现
    private int top; // 栈顶指针
    private final static int size = 100;

    public MyArrayStack() {
        array = new int[size];
        top = -1; // 栈空的时候
    }

    // 压栈
    public void push(int element) {
        if (top == size - 1) {
            resize();//这里进行扩容
        } else
            array[++top] = element;
    }

    // 弹栈
    public int pop() {
        if (top == -1) {
            throw new EmptyStackException();
        }
        return array[top--];
    }

    // 判断是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 返回栈顶元素
    public Integer peek() {
        if (top == -1) {
            throw new EmptyStackException();
        }
        return array[top];
    }
    //返回栈中元素个数
    public int size(){
        return top + 1 ;
    }
    private void resize(){
        assert size == array.length;//表示当条件成立时程序立即中止并返回一个错误消息
        int[] newArr = new int[size * 2 + 1];
        System.arraycopy(array, 0, newArr, 0, size);
        array = newArr;
    }
}

实现二：容器实现

package cn.list;
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;

public class MyArrayListStack<T> implements Stack<T> {
    private List<T> list; // 用容器实现

    MyArrayListStack() {
        list = new ArrayList<T>();
    }

    // 弹栈
    public T pop() {
        if (this.isEmpty() == true) {
            throw new EmptyStackException();
        }
        return list.remove(list.size() - 1);
    }

    // 压栈
    public void push(T element) {
        list.add(element);
    }

    // 判断是否为空
    public boolean isEmpty() {
        return list.size() == 0;
    }

    // 返回栈顶元素
    public T peek() {
        if (this.isEmpty() == true) {
            throw new EmptyStackException();
        }
        return list.get(list.size() - 1);
    }
    public int size(){
        return list.size();
    }
}

interface Stack<T> {
    public T pop();

    public void push(T element);

    public boolean isEmpty();

    public T peek();
    public int size();
}

实现三：链表实现

package cn.list;
import java.util.LinkedList;

//自己实现栈，使用LinkedList实现
public class MyLinkedListStack<T> {
    private LinkedList<T> list = new LinkedList<T>();

    public MyLinkedListStack() {
    }

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

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

    public T peek() {
        if (isEmpty()) {
            throw new java.util.EmptyStackException();
        }
        return list.getLast();
    }

    public T pop() {
        if (isEmpty()) {
            throw new java.util.EmptyStackException();
        }
        return list.removeLast();
    }

    public void push(T element) {
        list.addLast(element);
    }

    public int size(){
        return list.size();
    }
}

1.2 栈的应用

（转自：http://blog.csdn.net/hengjie2009/article/details/8478863）

1.2.1 平衡符号

问题描述： 在编写代码并且编译时，难免会因为少写了一个')'和被编译器报错。也就是说，编译器会去匹配括号是否匹配。当你输入了一个'('，很自然编译器回去检查你是否有另一个')'符号与之匹配。如果所有的括号都能够成对出现，那么编译器是能够通过的。否则编译器会报错。例如字符序列“(a+b)”是匹配的， 而字符序列"(a+b]"则不是。

算法描述如下： 创建一个空栈，读取字符序列直到结尾。如果字符是开放符号'(''[''{'，将其入栈；如果是一个封闭符号')'']''}'，则当栈为空时报错。否则，将栈顶元素弹出。如果弹出的符号不是对应的开放符号，则报错。当字符序列结束，判断栈是否为空，为空则报错

package cn.list;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Stack;

//栈的应用：平衡符号
public class BalanceSigned {

    public static boolean isBalanceChar() {
        Stack<Character> stack = new Stack<Character>();
        String path = "D:/a.txt";
        File file = new File(path);
        try {
            FileInputStream fis = new FileInputStream(file);
            InputStreamReader isr = new InputStreamReader(fis);
            BufferedReader br = new BufferedReader(isr);
            String line = "";
            while ((line = br.readLine()) != null) {
                for (int i = 0; i < line.length(); i++) {
                    switch (line.charAt(i)) {
                    case '[':
                        stack.push('[');
                        break;
                    case '(':
                        stack.push('(');
                        break;
                    case '{':
                        stack.push('{');
                        break;
                    case '/':
                        if (i < line.length() - 1 && line.charAt(i + 1) == '*') {
                            stack.push('/');
                            stack.push('*');
                        }
                        break;
                    case ']':
                        if (stack.size() == 0 || stack.pop() != '[') {
                            System.out.print("illigal character" + "[]");
                            return false;
                        }
                        break;
                    case ')':
                        if (stack.size() == 0 || stack.pop() != '(') {
                            System.out.print("illigal character" + "()");
                            return false;
                        }
                        break;
                    case '}':
                        if (stack.size() == 0 || stack.pop() != '{') {
                            System.out.print("illigal character" + "{}");
                            return false;
                        }
                        break;
                    case '*':
                        if ((i < line.length() - 1 && line.charAt(i + 1) == '/')
                                && (stack.size() < 2 || (stack.pop() != '*' || stack
                                        .pop() != '/'))) {
                            System.out.print("illigal character" + "");
                            return false;
                        }
                        break;
                    default:
                        break;
                    }
                }
            }
            if (stack.size() != 0) {
                System.out.print("error");
                return false;
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return true;
    }

    public static void main(String[] args) {
        boolean flag = isBalanceChar();
        if (flag) {
            System.out.println("是平衡符号");
        } else {
            System.out.println("不是平衡符号");
        }
    }
}

1.2.2 中缀表达式转后缀表达式

package cn.list;
/**
 * 工具类：
 * 1、中缀表达式转化为后缀表达式
 * 2、给出一个算术表达式（中缀表达式），直接得到计算结果
 */
import java.util.Stack;
import java.util.regex.Pattern;

//中缀表达式到后缀表达式的转换
public class Infix2Suffix {
    
    private Infix2Suffix() {}

    // 方法：给出一个算术表达式（中缀表达式），得到计算结果。 例如 (5+8+10)*1，返回23
    public static double stringToArithmetic(String string) {
        return suffixToArithmetic(infixToSuffix(string));
    }

    /**
     * 中缀表达式转后缀表达式 只处理了+,-,*,/和括号，没有处理负号及其它运算符，也没对前缀表达式验证。*/
    // 方法：中缀表达式转成后缀表达式
    public static String infixToSuffix(String infix) {
        Stack<Character> stack = new Stack<Character>();
        String suffix = "";
        int length = infix.length();
        for (int i = 0; i < length; i++) {
            Character temp;
            char c = infix.charAt(i);
            switch (c) {
            // 忽略空格
            case ' ':
                break;
            // 碰到'('，push到栈
            case '(':
                stack.push(c);
                break;
            // 碰到'+''-'，将栈中所有运算符弹出，送到输出队列中
            case '+':
            case '-':
                while (stack.size() != 0) {
                    temp = stack.pop();
                    if (temp == '(') {
                        stack.push('(');
                        break;
                    }
                    suffix += " " + temp;
                }
                stack.push(c);
                suffix += " ";
                break;
            // 碰到'*''/'，将栈中所有乘除运算符弹出，送到输出队列中
            case '*':
            case '/':
                while (stack.size() != 0) {
                    temp = stack.pop();
                    if (temp == '(' || temp == '+' || temp == '-') {
                        stack.push(temp);
                        break;
                    } else {
                        suffix += " " + temp;
                    }
                }
                stack.push(c);
                suffix += " ";
                break;
            // 碰到右括号，将靠近栈顶的第一个左括号上面的运算符全部依次弹出，送至输出队列后，再丢弃左括号
            case ')':
                while (stack.size() != 0) {
                    temp = stack.pop();
                    if (temp == '(')
                        break;
                    else
                        suffix += " " + temp;
                }
                // suffix += " ";
                break;
            // 如果是数字，直接送至输出序列
            default:
                suffix += c;
            }
        }

        // 如果栈不为空，把剩余的运算符依次弹出，送至输出序列。
        while (stack.size() != 0) {
            suffix += " " + stack.pop();
        }
        return suffix;
    }

    // 方法：通过后缀表达式求出算术结果
    public static double suffixToArithmetic(String postfix) {

        Pattern pattern = Pattern.compile("\\d+||(\\d+\\.\\d+)"); // 使用正则表达式匹配数字
        String strings[] = postfix.split(" "); // 将字符串转化为字符串数组
        for (int i = 0; i < strings.length; i++){
            strings[i].trim(); // 去掉字符串首尾的空格
        }
        Stack<Double> stack = new Stack<Double>();

        for (int i = 0; i < strings.length; i++) {

            if (strings[i].equals(""))
                continue;

            // 如果是数字，则进栈
            if ((pattern.matcher(strings[i])).matches()) {

                stack.push(Double.parseDouble(strings[i]));
            } else {
                // 如果是运算符，弹出运算数，计算结果。
                double y = stack.pop();
                double x = stack.pop();
                stack.push(caculate(x, y, strings[i])); // 将运算结果重新压入栈。
            }
        }
        return stack.pop(); // 弹出栈顶元素就是运算最终结果。

    }

    private static double caculate(double x, double y, String simble) {
        if (simble.trim().equals("+"))
            return x + y;
        if (simble.trim().equals("-"))
            return x - y;
        if (simble.trim().equals("*"))
            return x * y;
        if (simble.trim().equals("/"))
            return x / y;
        return 0;
    }
}

说明：中缀表达式如a+b*c+(d*e+f)*g会转换成abc*+de*f+g*+。

二、队列

（摘自：http://www.cnblogs.com/smyhvae/p/4793339.html）
队列和栈的实现其实差不多，但是要注意一个问题，队列是从尾部添加（入队），从头部删除（出队），有两种实现方式（数组实现和链表实现），对于数组实现有“假溢出”的问题，即经过一些列的出队和入队，导致队列头尾标记都指向了数组的尾部，此时虽然数组未满，但是却不能再插入数据了，于是我们需要实现循环，即当尾部标记指向数组的尾部且数组未满的情况下，让尾部标记在下一次插入的时候指向数组的头位置。

这里我们给出两种实现方式：
方式一：数组实现

package cn.list;

//循环顺序队列，数组实现
public class MyArrayQueue implements Queue {

    static final int defaultSize = 10; // 默认队列的长度
    int front; // 队头
    int rear; // 队尾
    int count; // 统计元素个数的计数器
    int maxSize; // 队的最大长度
    Object[] queue; // 队列

    public MyArrayQueue() {
        init(defaultSize);
    }

    public MyArrayQueue(int size) {
        init(size);
    }

    public void init(int size) {
        maxSize = size;
        front = rear = 0;
        count = 0;
        queue = new Object[size];
    }

    public void append(Object obj) throws Exception {
        if (count > 0 && front == rear) {
            throw new Exception("队列已满！");
        }
        queue[rear] = obj;
        //当队列满时让尾部标记重新指向数组开始位置，达到循环的目的
        rear = (rear + 1) % maxSize;
        count++;
    }

    public Object delete() throws Exception {
        if (isEmpty()) {
            throw new Exception("队列为空！");
        }
        Object obj = queue[front];
        //开始标记在到达数组最后一个位置时也需要循环
        front = (front + 1) % maxSize;
        count--;
        return obj;
    }
    
    //取得队列头
    public Object getFront() throws Exception {
        if (!isEmpty()) {
            return queue[front];
        } else {
            return null;
        }
    }

    public boolean isEmpty() {
        return count == 0;
    }

}

// 队列接口
interface Queue {

    // 入队
    public void append(Object obj) throws Exception;

    // 出队
    public Object delete() throws Exception;

    // 获得队头元素
    public Object getFront() throws Exception;

    // 判断对列是否为空
    public boolean isEmpty();
}

方式二：链表实现

package cn.list;


//实现链式队列
public class MyListQueue implements Queue {

    Node front; //队头
    Node rear;  //队尾
    int count; //计数器

    public MyListQueue() {
        init();
    }

    public void init() {
        front = rear = null;
        count = 0;
    }

    public void append(Object obj) throws Exception {
        Node node = new Node(obj, null);

        //如果当前队列不为空。
        if (rear != null) {
            rear.next = node; //队尾结点指向新结点
        }
        rear = node; //设置队尾结点为新结点

        //说明要插入的结点是队列的第一个结点
        //此时头尾指向同一个节点
        if (front == null) {
            front = node;
        }
        count++;
    }

    public Object delete() throws Exception {
        if (isEmpty()) {
            new Exception("队列已空！");
        }
        Node node = front;
        front = front.next;
        count--;
        return node.getElement();
    }

    public Object getFront() throws Exception {
        if (!isEmpty()) {
            return front.getElement();
        } else {
            return null;
        }
    }

    public boolean isEmpty() {
        return count == 0;
    }
}

//结点类
class Node {

  Object element; //数据域
  Node next;  //指针域

  //头结点的构造方法
  public Node(Node nextval) {
      this.next = nextval;
  }

  //非头结点的构造方法
  public Node(Object obj, Node nextval) {
      this.element = obj;
      this.next = nextval;
  }

  //获得当前结点的后继结点
  public Node getNext() {
      return this.next;
  }

  //获得当前的数据域的值
  public Object getElement() {
      return this.element;
  }

  //设置当前结点的指针域
  public void setNext(Node nextval) {
      this.next = nextval;
  }

  //设置当前结点的数据域
  public void setElement(Object obj) {
      this.element = obj;
  }

  public String toString() {
      return this.element.toString();
  }
}

三、栈和队列的应用

（摘自：http://www.cnblogs.com/smyhvae/p/4795984.html）

3.1 应用一：判断回文

队列有一个很常见的应用就是判断字符串是否是回文字符串（从头看和从尾看是一样的，如soros），这可以将此字符串分别加入到栈和队列中，然后分别出栈和出队进行比较，如果都是一样的则表示是回文字符串。

3.2 栈实现队列

package cn.list;
import java.util.Stack;
//使用两个栈实现一个队列
//说的通俗一点，现在把数据1、2、3分别入栈一，然后从栈一中出来（3、2、1），放到栈二中，
//那么，从栈二中出来的数据（1、2、3）就符合队列的规律了，即负负得正。

public class MyStackQueue {

    private Stack<Integer> stack1 = new Stack<Integer>();// 执行入队操作的栈
    private Stack<Integer> stack2 = new Stack<Integer>();// 执行出队操作的栈

    // 方法：给队列增加一个入队的操作
    public void push(int data) {
        stack1.push(data);
    }

    // 方法：给队列正价一个出队的操作
    public int pop() throws Exception {
        // stack1中的数据放到stack2之前，先要保证stack2里面是空的（要么一开始就是空的，
        //要么是stack2中的数据出完了），不然出队的顺序会乱的，这一点很容易忘
        if (stack2.empty()) {
            while (!stack1.empty()) {
                // 把stack1中的数据出栈，放到stack2中【核心代码】
                stack2.push(stack1.pop());
            }
        }
        // stack2为空时，有两种可能：1、一开始，两个栈的数据都是空的；2、stack2中的数据出完了
        if (stack2.empty()) { 
            throw new Exception("队列为空");
        }
        //如果stack2不为空，则直接出栈
        return stack2.pop();
    }
}

3.3 队列实现栈

package cn.list;
import java.util.ArrayDeque;
import java.util.Queue;

//使用队列实现栈
public class MyQueueStack {

    Queue<Integer> queue1 = new ArrayDeque<Integer>();
    Queue<Integer> queue2 = new ArrayDeque<Integer>();

    // 方法：入栈操作
    public void push(int data) {
        queue1.add(data);
    }

    // 方法：出栈操作
    /*将1、2、3依次入队列一， 然后最上面的3留在队列一，
     * 将下面的1、2入队列二，将3出队列一，此时队列一空了，然后把队列二中的所有数据入队列一；
     * 将最上面的2留在队列一，将下面的3入队列二。。。依次循环。
     * */
    public int pop() throws Exception {
        int data;
        if (queue1.size() == 0) {
            throw new Exception("栈为空");
        }

        while (queue1.size() != 0) {
            if (queue1.size() == 1) {
                data = queue1.poll();
                while (queue2.size() != 0) { // 把queue2中的全部数据放到队列一中
                    queue1.add(queue2.poll());
                }
                return data;
            }
            queue2.add(queue1.poll());
        }
        throw new Exception("栈为空");// 不知道这一行的代码是什么意思
    }
}

3.4 设计含最小函数min()的栈

（摘自：http://blog.csdn.net/sgbfblog/article/details/7752878）
要求min、push、pop的时间复杂度都是O(1)
分析：
很刚开始很容易想到一个方法，那就是额外建立一个最小堆保存所有元素，这样每次获取最小元素只需要O（1）的时间。但是这样的话，PUSH和POP操作就需要O（lgn）的时间了（假定栈中元素个数为n），不符合题目的要求。可以使用一个辅助栈。
解法：
使用一个辅助栈来保存最小元素，这个解法简单不失优雅。设该辅助栈名字为minStack，其栈顶元素为当前栈中的最小元素。这意味着要获取当前栈中最小元素，只需要返回minStack 的栈顶元素即可。每次执行push操作，检查push的元素是否小于或等于minStack栈顶元素。如果是，则也push该元素到minStack 中。当执行pop操作的时候，检查pop的元素是否与当前最小值相等。如果相同，则需要将改元素从minStack中pop出去。
实例：
假定有元素3， 2， 5， 4， 2， 1依次入栈，则原始栈中元素为（1）， 辅助栈中元素为（2）

这样，第1次pop时，1从两个栈都pop出去；第2次pop时，2从两个栈都pop出去；第3次pop，元素4从原始栈pop出去，辅助栈不用pop；第4次pop，元素5从原始栈pop出去，辅助栈不需pop；第5次pop，元素2从两个栈pop出去；第6次pop，元素3从两个栈都pop出去。我们可以发现，每次push或者pop后，辅助栈的栈顶元素总是当前栈的最小元素。

package cn.list;
import java.util.Stack;

public class GetMinStack {

    private Stack<Integer> stack = new Stack<Integer>();
  //辅助栈：栈顶永远保存stack中当前的最小的元素
    private Stack<Integer> minStack = new Stack<Integer>(); 


    public void push(int data) {
        stack.push(data);  //直接往栈中添加数据

        //在辅助栈中需要做判断
        if (minStack.size() == 0 || data <= minStack.peek()) {
            minStack.push(data);
        } else {
            minStack.add(minStack.peek());   //【核心代码】peek方法返回的是栈顶的元素
        }
    }

    public int pop() throws Exception {
        if (stack.size() == 0) {
            throw new Exception("栈中为空");
        }

        int data = stack.pop();
        minStack.pop();  //核心代码
        return data;
    }

    public int min() throws Exception {
        if (minStack.size() == 0) {
            throw new Exception("栈中空了");
        }
        return minStack.peek();
    }
}

3.5 判断栈的push和pop序列是否一致

已知一组数据1、2、3、4、5依次进栈，那么它的出栈方式有很多种，请判断一下给出的出栈方式是否是正确的？
例如：
数据：
　　1、2、3、4、5
出栈1：
　　5、4、3、2、1（正确）
出栈2：
　　4、5、3、2、1（正确）
出栈3：
　　4、3、5、1、2（错误）

package cn.list;
import java.util.Stack;
/*
 * 判断栈的push和pop序列是否一致
 *  通俗一点讲：已知一组数据1、2、3、4、5依次进栈，
 *  那么它的出栈方式有很多种，请判断一下给出的出栈方式是否是正确的？
 *  
 *  例如：
数据：
　　1、2、3、4、5
出栈1：
　　5、4、3、2、1（正确）
出栈2：
　　4、5、3、2、1（正确）
出栈3：
　　4、3、5、1、2（错误）
 * */

public class StackTest {

    //方法：data1数组的顺序表示入栈的顺序。现在判断data2的这种出栈顺序是否正确
    public static boolean sequenseIsPop(int[] data1, int[] data2) {
        Stack<Integer> stack = new Stack<Integer>(); //这里需要用到辅助栈

        for (int i = 0, j = 0; i < data1.length; i++) {
            stack.push(data1[i]);
            while (stack.size() > 0 && stack.peek() == data2[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.size() == 0;
    }

    public static void main(String[] args) {

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

        int[] data1 = {1, 2, 3, 4, 5};
        int[] data2 = {4, 5, 3, 2, 1};
        int[] data3 = {4, 5, 2, 3, 1};

        System.out.println(sequenseIsPop(data1, data2));
        System.out.println(sequenseIsPop(data1, data3));
    }
}

说明：下面我们看此题的原理：

• 我们以前面的序列4、5、3、2、1为例。第一个希望被pop出来的数字是4，因此4需要先push到栈里面。由于push的顺序已经由push序列确定了，也就是在把4 push进栈之前，数字1，2，3都需要push到栈里面。此时栈里的包含4个数字，分别是1，2，3，4，其中4位于栈顶。把4 pop出栈后，剩下三个数字1，2，3。接下来希望被pop的是5，由于仍然不是栈顶数字，我们接着在push序列中4以后的数字中寻找。找到数字5后再一次push进栈，这个时候5就是位于栈顶，可以被pop出来。接下来希望被pop的三个数字是3，2，1。每次操作前都位于栈顶，直接pop即可。

• 再来看序列4、3、5、1、2。pop数字4的情况和前面一样。把4 pop出来之后，3位于栈顶，直接pop。接下来希望pop的数字是5，由于5不是栈顶数字，我们到push序列中没有被push进栈的数字中去搜索该数字，幸运的时候能够找到5，于是把5 push进入栈。此时pop5之后，栈内包含两个数字1、2，其中2位于栈顶。这个时候希望pop的数字是1，由于不是栈顶数字，我们需要到push序列中还没有被push进栈的数字中去搜索该数字。但此时push序列中所有数字都已被push进入栈，因此该序列不可能是一个pop序列。

• 也就是说，如果我们希望pop的数字正好是栈顶数字，直接pop出栈即可；如果希望pop的数字目前不在栈顶，我们就到push序列中还没有被push到栈里的数字中去搜索这个数字，并把在它之前的所有数字都push进栈。如果所有的数字都被push进栈仍然没有找到这个数字，表明该序列不可能是一个pop序列。
  通过此原理我们可以手工进行判断。