手把手教你Java实现栈和队列_java 队列 栈实现类

压栈 ：栈的插入操作叫做进栈 / 压栈 / 入栈， 入数据在栈顶。

出栈 ：栈的删除操作叫做出栈。 出数据在栈顶。

    public static void main(String[] args) {
        Stack<Integer> s = new Stack();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.size()); // 获取栈中有效元素个数---> 4
        System.out.println(s.peek()); // 获取栈顶元素---> 4
        s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
        System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
        if(s.empty()){
            System.out.println("栈空");
        }else{
            System.out.println(s.size());
        }
    }

从上图中可以看到， Stack 继承了 Vector ， Vector 和 ArrayList 类似，都是动态的顺序表，不同的是 Vector 是线程安全的。

那么现在，我们可以运用目前所学过的知识来模拟一下栈中的各个方法：

push方法

    public int push(int e){
        ensureCapacity();
        array[size++] = e;
        return e;
    }

pop方法

    public int pop(){
        int e = peek();
        size--;
        return e;
    }

peek方法

    public int peek(){
        if(empty()){
            throw new RuntimeException("栈为空，无法获取栈顶元素");
        }
        return array[size-1];
    }

1. 改变元素的序列

现在，我们来看这样一道题：

假设现在有这么一道oj题：要求我们逆序打印链表

那么递归的写法是这个样子的：

    // 递归方式
    void printList(Node head){
        if(null != head){
            printList(head.next);
            System.out.print(head.val + " ");
        }
    }

而如果我们使用栈，那么代码就会演变成这样:

    void printList(Node head){
        if(null == head){
            return;
        }
        Stack<Node> s = new Stack<>();
// 将链表中的结点保存在栈中
        Node cur = head;
        while(null != cur){
            s.push(cur);
            cur = cur.next;
        }
        // 将栈中的元素出栈
        while(!s.empty()){
            System.out.print(s.pop().val + " ");
        }
    }

综上，我们可以得知：通过栈的实现，我们可以将递归转化成循环

---

2. 队列(Queue)

1、概念

---

2、队列的使用  

那么在Java中，常见的队列的方法有以下几种：

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

    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(1);
        q.offer(2);
        q.offer(3);
        q.offer(4);
        q.offer(5); // 从队尾入队列
        System.out.println(q.size());
        System.out.println(q.peek()); // 获取队头元素
        q.poll();
        System.out.println(q.poll()); // 从队头出队列，并将删除的元素返回
        if(q.isEmpty()){
            System.out.println("队列空");
        }else{
            System.out.println(q.size());
        }
    }

---

3、队列模拟实现

 
public class Queue {
    // 双向链表节点
    public static class ListNode{
        ListNode next;
        ListNode prev;
        int value;
        ListNode(int value){
            this.value = value;
        }
    }
    ListNode first; // 队头
    ListNode last; // 队尾
    int size = 0;
    // 入队列---向双向链表位置插入新节点
    public void offer(int e){
        ListNode newNode = new ListNode(e);
        if(first == null){
            first = newNode;
// last = newNode;
        }else{
            last.next = newNode;
            newNode.prev = last;
// last = newNode;
        }
        last = newNode;
        size++;
    }
    // 出队列---将双向链表第一个节点删除掉
    public int poll(){
// 1. 队列为空
// 2. 队列中只有一个元素----链表中只有一个节点---直接删除
// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除
        int value = 0;
        if(first == null){
            return null;
        }else if(first == last){
            last = null;
            first = null;
        }else{
            value = first.value;
            first = first.next;
            first.prev.next = null;
            first.prev = null;
        }
        --size;
        return value;
    }
    // 获取队头元素---获取链
    public int peek(){
        if(first == null){
            return null;
        }
        return first.value;
    }
    public int size() {
        return size;
    }
    public boolean isEmpty(){
        return first == null;
    }
}

---

4、循环队列

数组下标循环的小技巧 

 如何区分空与满

1. 通过添加 size 属性记录

2. 保留一个位置

3. 使用标记