[Java知识库]玩转JAVA---------栈和队列

栈（Stack）

概念

栈（Stack）继承于Vector，底层是一个数组
栈是先进后出的数据结构

1、判断进出栈的顺序

答案是C

2、计算机通过栈进行计算

中缀表达式——>后缀表达式
（加括号，移符号，去括号）

把数字放入栈中
遇到算术运算符，从栈中提出两个数字运算，先右后左（针对 - 和 /）
运算结果放入栈中
如此循环，直到栈为空结束，得到计算结果

XABCD-*E/+=

使用栈

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

        Stack<Integer> stack = new Stack<>();
        stack.push(10); //入栈
        stack.push(20);
        stack.push(30);
        stack.push(40);
        System.out.println(stack);

        int ret = stack.pop();  //40
        System.out.println(ret);

        int ret1 = stack.peek();  //30
        System.out.println(ret1);

        boolean flg = stack.empty();  //false
        System.out.println(flg);

        System.out.println(stack);
        int index = stack.search(20); //返回下标，30-1 ， 20-2 ，10-3
        System.out.println(index);

用顺序表实现一个栈

public class MyStack<T> {
    private T[] elem;  //数组
    private int top;     //数组中可以存放元素的下标，也叫栈顶指针

    public MyStack() {
        this.elem =(T[])new Object[10];
    }

    public void push(T element) {
        //1、先判断栈是否是满的,满了扩容
        //2、添加元素
        if (this.top == this.elem.length) {
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }
        this.elem[top] = element;
        top++;
//      this.elem[top++]=element;

    }

    public T pop(){
        if(empty()){
           throw new UnsupportedOperationException("栈为空");
        }
        T ret=this.elem[this.top-1];
        this.top--;            //真正的删除
//      int ret=this.elem[--top];
        return ret;
    }

    public T peek(){
        if(empty()){
            throw new UnsupportedOperationException("栈为空");
        }
        T ret=this.elem[this.top-1];
        return ret;
    }

    public boolean empty(){
        return this.top==0;
    }

    @Override
    public String toString() {
        return "MyStack{" +
                "elem=" + Arrays.toString(elem) +
                ", top=" + top +
                '}';
    }

}

话说，栈能否通过单向链表实现呢？
当然可以啦！！！
只是
如果入栈用尾插法，入栈和出栈时间复杂度O(n)；即使用last指向栈顶元素，入栈时间复杂度可变为O(1)，但是出栈需要使用栈顶元素的前一个元素，时间复杂度仍为O(n);双向链表可以使入栈和出栈的时间复杂度均为O(1)
如果入栈用头插法，有head指向头元素，入栈和出栈的时间复杂度均为O(1)，

队列（Queue）

概念

底层是链表
先进先出，即进到队头而且从队头出

使用队列

Queue<Integer> queue = new LinkedList<>();
//或 LinkedList<Integer> linkedList = new LinkedList<>();

通过链表实现一个队列

用first指向队头；用last指向队尾
进队尾插；出队头删
时间复杂度都为O(1)
实现方法时注意判断对列是否为空

class Node{
    private int val;
//可以不用改成public
    private Node next;
    public Node(int val){
        this.val=val;
    }
    public int getVal() {
        return val;
    }
    public void setVal(int val) {
        this.val = val;
    }
    public Node getNext() {
        return next;
    }
    public void setNext(Node next) {
        this.next = next;
    }
}
public class MyQueue {
    private Node first;
    private Node last;
    //尾插入队
    public void offer(int val){
        Node node = new Node(val);
        //先判断是否为空
        if(empty()){
            this.first=node;
            this.last=node;
        }else{
            this.last.setNext(node);
            this.last=node;
        }
    }
//出队
    public int poll(){
        if(empty()) {
            throw new UnsupportedOperationException("队列为空！！");
        }
        int ret = this.first.getVal();
        this.first = this.first.getNext();
        return ret;
        
    }
//得到队头元素，不删除
    public int peek(){
        if(empty()){
            throw new UnsupportedOperationException("队列为空！！！");
        }
        return this.first.getVal();
    }

    public boolean empty(){
        return this.first==null;
    }
}