栈和队列

栈(Stack)

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

image.png

实现

利用顺序表实现（尾插、尾删）

package xsk;

public class MyStack {
    public int[] arr = new int[100];
    public int size = 0;

    public void push(int val) {
        arr[size] = val;
        size++;
    }

    public int pop() {
        size--;
        return size;
    }

    public int peek() {
        if(size <= 0) {
            return -1;
        }
        return arr[size - 1];
    }

    public int size() {
        return size;
    }
}

队列(Queue)

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头（Head/Front）

image.png

实现

队列的实现可以用:顺序表：尾插表示“入队”；头删表示“出队”，也可以用链表，使用链表的效率更优一点，因为使用数组出队列头删，效率低下。

package xsk;

class Node {
    int val;
    Node next;

    Node(int val, Node next) {
        this.val = val;
        this.next = next;
    }
    Node(int val) {
        this(val, null);
    }
}
public class MyQueue {
    public Node head = null;
    public Node tail = null;
    public int size = 0;

    public void offer(int v) {
        Node newNode = new Node(v);
        if(tail == null) {
            newNode = head;
        } else {
            tail.next = head;
        }
        tail = tail.next;
        size++;
    }
    public int poll() {
        if(size == 0) {
            throw new RuntimeException("队列为空");
        }
        Node oldNode = head;
        head = head.next;
        if(head == null) {
            tail = null;
        }
        size--;
        return oldNode.val;
    }
    public int peek() {
        if(size == 0) {
            throw new RuntimeException("队列为空");
        }
        return head.val;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public int size() {
        return size;
    }
}

循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。

package xsk;

public class MyCycleQueue {
    public int[] data = new int[100];
    public int head = 0;
    public int tail = 0;
    int size = 0;

    public boolean offer(int val) {
        if(size == data.length) {
            return false;
        }
        data[size] = val;
        tail++;
        if(tail == data.length) {
            tail = 0;
        }
        size++;
        return true;
    }
    public Integer poll() {
        if(size == 0) {
            return null;
        }
        int ret =data[head];
        head++;
        if(head == data.length) {
            head = 0;
        }
        size--;
        return ret;
    }
    public Integer peek() {
        if(size == 0) {
            return null;
        }
        return data[head];
    }
}

java中栈和队列

栈(Stack)

队列(Queue)