JavaSE

• JavaSE Queue/Stack
• 环形队列
• • C++环形队列
  • Java环形队列

Stack底层是一个数组

import java.util.Arrays;

class MyStack{
    private Object[] array;
    private int useSize;
    MyStack(){
        this.array=new Object[1];
        this.useSize=0;
    }
    private void dilatation(){
        this.array= Arrays.copyOf(this.array,this.array.length*2);
    }
    public void push(E num){
        if(array.length==this.useSize){
            dilatation();
            System.out.println("INFO:扩容成功");
        }
        array[useSize++]=num;
    }
    public Object pop(){
        if(isEmpty()){
            throw new RuntimeException("栈为空");
        }
        Object num=array[useSize-1];
        this.array[useSize-1]=null;
        this.useSize--;
        return num;
    }
    public boolean isEmpty(){
        return useSize==0;
    }
}

Queue底层是一个链表

class Node{
    public int val;
    public Node next;
    public Node(int val){
        this.val=val;
        next=null;
    }
}

class MyQueue{//实现普通队列
    private Node head;
    private Node last;
    public MyQueue(){
        this.head=null;this.last=null;
    }
    public void offer(int val){
        if(head==null){
            this.head=new Node(val);
            this.last=this.head;
        }
        else{
            Node newNode=new Node(val);
            this.last.next=newNode;
            this.last=newNode;
        }
    }
    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }
        int oldval=head.val;
        if(head==last){
            this.last=null;
        }
        this.head=this.head.next;
        return oldval;
    }
    public boolean isEmpty(){
        return head==null;
    }
}

public class TestQueue {
    public static void main(String[] args) {
        MyQueue queue=new MyQueue();
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        System.out.println(queue.poll());
        System.out.println(queue.poll());
        System.out.println(queue.poll());
//        System.out.println(queue.head);
//        System.out.println(queue.last);
    }
}

环形队列首尾指针移动规则：

front=(front+1)%array.length 来达到将数组抽象为环形的方法

判断空和满有三种策略

1. 添加useSize判断满和空
2. 添加标志位判断满和空
3. 空开一个空间来判断空还是满

注意：方法2，3 获取环形队列尾部的方法时 last指向的是环形队列尾部的下一个位置。所以需要公式 (last+array.length-1)%array.length来计算last指向的上一个节点

struct QueueNode{
    int val;
    bool isUsed;//标记位
    QueueNode():val(-1),isUsed(false){}
};

class MyCircularQueue {
    vectorvet;
    int front;
    int last;
public:
    MyCircularQueue(int k) {
        vet.resize(k);
        front=0;
        last=0;
    }
    
    bool enQueue(int value) {
        if(isFull()){
            return false;
        }
        vet[last].val=value;
        vet[last].isUsed=true;
        last=(last+1)%vet.size();
        return true;
    }
    
    bool deQueue() {
        if(isEmpty()){
            return false;
        }
        vet[front].isUsed=false;
        front=(front+1)%vet.size();
        return true;
    }
    
    int Front() {
        if(isEmpty()){
            return -1;
        }
        return vet[front].val;
    }
    
    int Rear() {
        if(isEmpty()){
            return -1;
        }
        return vet[(last+vet.size()-1)%vet.size()].val;
    }
    
    bool isEmpty() {
        return front==last&&vet[front].isUsed==false;
    }
    
    bool isFull() {
        return front==last&&vet[front].isUsed==true;
    }
};

class MyCircularQueue {
    private int[]arrry;
    private int front;
    private int last;
    public MyCircularQueue(int k) {
        this.arrry=new int[k+1];
        this.front=0;
        this.last=0;
    }
    
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        this.arrry[this.last]=value;
        this.last=(this.last+1)%this.arrry.length;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front=(this.front+1)%this.arrry.length;
        return true;
    }
    
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.arrry[this.front];
    }
    
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        return this.arrry[(this.last+this.arrry.length-1)%this.arrry.length];
    }
    
    public boolean isEmpty() {
        return this.last==this.front;
    }
    
    public boolean isFull() {
        return (this.last+1)%this.arrry.length==this.front;
    }
}