栈

定义

在计算机科学中，stack是一种线性的数据结构，只能在其一端添加数据和移除数据。习惯来说，这一端称之为栈顶，另一端不能操作数据的称之为栈底，就像一个装书的容器一样，放从最上面放，拿从最上面拿。

常见的栈方法接口实现

public interface Stack<E> {

    /**
     * 向栈顶压入元素
     * @param value-待压入值
     * @return 压入成功返回true，否则返回false
     */
    boolean push(E value);

    /**
     * 从栈顶弹出元素
     * @return 栈非空返回栈顶元素，栈为空返回null
     */
    E pop();

    /**
     * 返回栈顶元素，不弹出
     * @return 栈非空返回栈顶元素，栈位空返回null
     */
    E peek();

    /**
     * 判断栈是否为空
     * @return 空返回true，否则返回false
     */
    boolean isEmpty();

    /**
     * 判断栈是否已满
     * @return 满返回true，否则返回false
     */
    boolean isFull();
}

单向链表实现栈

和队列差不多，就是少了一个尾指针，不在尾部拿值

//单向链表带哨兵实现栈
public class LinkedListStack<E> implements Stack<E> ,Iterable<E>{

    private int capacity;
    private int size;
    private Node<E> head = new Node<>(null, null);

    public LinkedListStack(int capacity) {
        this.capacity = capacity;
    }

    static class Node<E> {
        E value;
        Node<E> next;

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }




    @Override
    public boolean push(E value) {
        if(isFull()) {
            return false;
        }
        // head -> 2 -> 1 -> null
        head.next = new Node<>(value, head.next);
        size++;
        return true;
    }

    @Override
    public E pop() {
        if(isEmpty()) {
            return null;
        }
        Node<E> first = head.next;
        //移除操作
        head.next = first.next;
        size--;
        return first.value;
    }

    @Override
    public E peek() {
        if(isEmpty()) {
            return null;
        }
        return head.next.value;
    }

    @Override
    public boolean isEmpty() {
        //return head.next == null;
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = head.next;
            @Override
            public boolean hasNext() {
                return p != null;
            }

            @Override
            public E next() {
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}

数组实现栈

//数组实现栈
public class ArrayStack<E> implements Stack<E>, Iterable<E>{

    private E[] array;
    private int top;// 栈顶指针

    /*
        底          顶
        0   1   2   3
        a   b   c   d
        t(指针)
     */

    @SuppressWarnings("all")
    public ArrayStack(int capacity) {
        //数组初始化
        this.array = (E[]) new Object[capacity];
    }

    @Override
    public boolean push(E value) {
        if(isFull()) {
            return false;
        }
        //先找array[top]的值再自增，一举两得
        array[top++] = value;
        //top++;
        return true;
    }

    @Override
    public E pop() {
        if(isEmpty()) {
            return null;
        }
        //因为在push方法中已经移动了指针，所以要取栈顶值是减一后的值
        //包含了top减一的情况了
        return array[--top];
    }

    @Override
    public E peek() {
        if(isEmpty()) {
            return null;
        }
        //因为在push方法中已经移动了指针，所以要取栈顶值是减一后的值
        return array[top - 1];
    }

    @Override
    public boolean isEmpty() {
        return top == 0;
    }

    @Override
    public boolean isFull() {
        return top == array.length;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = top;
            @Override
            public boolean hasNext() {
                return p > 0;
            }

            @Override
            public E next() {
                return array[--p];
            }
        };
    }
}

力扣关于栈的题

有效的括号 T20

遍历字符串每位字符比较，出现左括号存入相对应的右括号到栈中，接着出现右括号就进行比对，比对失败就是false

public boolean isValid(String s) {
        Stack<Character>stack = new Stack<Character>();
        for(char c: s.toCharArray()){
            if(c=='(')stack.push(')');
            else if(c=='[')stack.push(']');
            else if(c=='{')stack.push('}');
            else if(stack.isEmpty()||c!=stack.pop())return false;
        }
        return stack.isEmpty();
    }

逆波兰表达式求值 T150

public int evalRPN(String[] tokens) {

        /*
            解题思路：
                -遇到数字压入栈
                -遇到运算符，就从栈中弹出两个数字做运算，将结果压入栈
                -遍历结束，栈中剩下的数字就是结果
         */
        //里面也实现了栈的方法
        LinkedList<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            switch (token) {
                case "+" : {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a+b);
                    break;
                }
                case "-" : {
                    Integer b = stack.pop();//注意先后顺序，先压后出
                    Integer a = stack.pop();
                    stack.push(a-b);
                    break;
                }
                case "*" : {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a*b);
                    break;
                }
                case "/" : {
                    Integer b = stack.pop();
                    Integer a = stack.pop();
                    stack.push(a/b);
                    break;
                }
                default: {  //剩下的就是数字
                    stack.push(Integer.parseInt(token));
                }
            }
        }
        return stack.pop();
    }

双栈实现队列 T232

//定义两个栈
    LinkedList<Integer> s1 = new LinkedList<>();
    LinkedList<Integer> s2 = new LinkedList<>();

    public void push(int x) {
        //往队列尾部添加值就是先在一个栈中压入值
        s2.push(x);
    }

    public int pop() {
        //从队列头部移除值就是从s2出来在压入s1就行
        if(s1.isEmpty()) {
            while(!s2.isEmpty()) {
                s1.push(s2.pop());
            }
        }
        return s1.pop();
    }

    public int peek() {
        if(s1.isEmpty()) {
            while(!s2.isEmpty()) {
                s1.push(s2.pop());
            }
        }
        return s1.peek();
    }

    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }

单队列实现栈 T225

//单队列
    Queue<Integer> a;

    //计算元素的个数
    int i;

    public void push(int x) {
        //把新添加的元素前面的元素都移动到它的后面去
        a.offer(x);
        for (int j = 0; j < i; j++) {
            a.offer(a.poll());
        }
        i++;
    }

    //移除列头元素
    public int pop() {
        i--;
        return a.poll();
    }

    public int top() {
        return a.peek();
    }

    public boolean empty() {
        return a.isEmpty();
    }