Java——栈和队列

• 一、栈
• • 1、使用
  • 2、应用场景
  • 3、模拟实现
• 二、队列
• • 1、使用
  • 2、模拟实现
  • 3、循环队列
  • 4、双端队列

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out） 的原则。

• 入栈： 栈的插入操作称为进栈入栈压栈，入栈的元素保存在栈顶。
• 出栈： 栈的删除操作称为出栈。出栈元素是栈顶元素。
  

    public static void method1() {
        //Stack测试
        Stack s = new Stack<>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println("s = " + s);
        System.out.println("s.pop() = " + s.pop());
        System.out.println("s = " + s);
        System.out.println("s.peek() = " + s.peek());
        if(s.empty())
            System.out.println("empty");
        else
            System.out.println("元素个数为："+s.size());
    }
    public static void main(String[] args) {
        method1();
    }

• 改变元素的序列
• 将递归转化为循环
• 括号匹配
• 逆波兰表达式求值

Stack继承了Vector，Vector与ArrayList类似，都是动态顺序表。

public class MyStack {
    E[] array;
    int size;

    public MyStack(){
        array  = (E[]) new Object[3];
    }

    //入栈
    public E push(E e){
        ensureCapacity();
        array[size++] = e;
        return e;
    }

    //出栈
    public E pop(){
        E e = peek();
        size--;
        return e;
    }

    //取栈顶元素
    public E peek(){
        if (empty()){
            throw new RuntimeException("栈为空");
        }

        return array[size--];
    }

    //判断栈是否为空
    public boolean empty(){
        return 0 == size;
    }
    
    //容量不够扩容
    public void ensureCapacity(){
        if(size == array.length)
            array = Arrays.copyOf(array,size*2);
    }
}

队列是一种只允许在其一端进行插入数据操作，在其另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

• 入队列： 进行插入操作的一端称为队尾（Tail/Rear）
• 出队列： 进行删除操作的一端称为队头（Head/Front）
  

Queue是个接口，在实例化时必须实例化linkedList的对象，因为linkedList实现了Queue接口。

    public static void method2(){
        //Queue测试
        Queue q = new linkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        System.out.println("q = " + q);
        q.add(5);
        q.add(6);
        System.out.println("q = " + q);
        System.out.println("q.size() = " + q.size());
        System.out.println("q.peek() = " + q.peek());
        System.out.println("q.poll() = " + q.poll());
        System.out.println("q = " + q);
        if (q.isEmpty())
            System.out.println("为空");
        else
            System.out.println("元素个数为："+q.size());
    }

    public static void main(String[] args) {
        method2();
    }

Java中Queue

public class MyQueue {
    public static class Node{
        private E value;
        private Node next;

        public Node(E val){
            value = val;
            next = null;
        }
    }

    Node front;
    Node back;
    int size;

    //入队列
    public boolean offer(E e){
        Node node = new Node<>(e);
        if (null == front){
            front = node;
        }else{
            back.next = node;
        }

        back = node;
        size++;
        return true;
    }

    //出队列
    public E poll(){
        if (0 == size)
            throw new RuntimeException("队列为空");

        Node delNode = front;
        front = front.next;
        if(null == front){
            back = null;
        }

        size--;
        return delNode.value;
    }

    //取队头元素
    public E peek(){
        if (0 == size)
            throw new RuntimeException("队列为空");
        return front.value;
    }


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

    public int size(){
        return size;
    }
}

两种方式实现下标的循环：

1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length。
2. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

区分循环队列的空与满

1. 使用size添加记录。
2. 预留一个位置用做判断。
3. 使用标记判断。

图2便是利用预留一个位置的方式来对循环队列是否满做判断，认为此时图2的情况便是循环队列满，即：队尾+1=队首

双端队列（deque）是允许两端都可以进行入队或出队操作的队列，说明元素可以从队头出队和入队，也可以从队尾出队和入队。