X16数据结构部分01

• 队列代码实现：
• 循环队列代码实现：
• 循环队列官方代码实现：
• 队列思想解决数据流的移动平均值：
• 队列思想解决墙与门算法：最短路径模板
• 岛屿问题：深度优先搜索解决
• 总目录

package dc;

import java.util.List;
import java.util.ArrayList;


public class d11{
    public static void main(String[] args) {
        MyQueue q = new MyQueue();
        q.enQueue(5);
        q.enQueue(3);
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
        q.deQueue();
        if (q.isEmpty() == false) {
            System.out.println(q.Front());
        }
    }
}

class MyQueue {
    // store elements
    private List data;
    // 指针指向队列的头部
    private int p_start;
    public MyQueue() {
        data = new ArrayList();
        p_start = 0;
    }

    
    public boolean enQueue(int x) {
        data.add(x);
        return true;
    }

    
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        
        p_start++;
        return true;
    }

    
    public int Front() {
        return data.get(p_start);
    }

    
    public boolean isEmpty() {
        return p_start >= data.size();
    }
}

class MyCircularQueue {
    private int[] mContainer;

    private int mContainerSize;

    private int mHead;

    private int mTail;


    public MyCircularQueue(int k) {
        mContainerSize = k;
        mContainer = new int[k];
        mHead = -1;
        mTail = -1;
    }

    
    public boolean enQueue(int value) {
        if(isFull()) {
            return false;
        }
        if(isEmpty()) {
            mHead ++;
            mTail ++;
            mContainer[mTail] = value;
            return true;
        }
        mTail ++;
        if(mTail > mContainerSize-1) {
            
            mTail = mTail-mContainerSize;
        }
        mContainer[mTail] = value;
        return true;
    }

    
    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }
        
        if(mHead == mTail) {
            mHead = -1;
            mTail = -1;
            return true;
        }
        mHead ++;
        if(mHead > mContainerSize-1) {
            mHead = mHead-mContainerSize;
        }
        return true;
    }

    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return mContainer[mHead];
    }

    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        return mContainer[mTail];
    }

    public boolean isEmpty() {
        return mHead == -1 && mTail == -1;
    }

    public boolean isFull() {
        if(mContainerSize == 0) {
            return true;
        }
        if(mHead == -1 && mTail == -1) {
            return false;
        }
        return (mTail-mHead+1 == mContainerSize) || (mTail-mHead == -1);
    }
}

class MyCircularQueue {
    
    private int[] data;
    private int head;
    private int tail;
    private int size;

    
    public MyCircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }
    
    
    public boolean enQueue(int value) {
        if (isFull() == true) {
            return false;
        }
        if (isEmpty() == true) {
            head = 0;
        }
        tail = (tail + 1) % size;
        data[tail] = value;
        return true;
    }
    
    
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head + 1) % size;
        return true;
    }
    
    
    public int Front() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[head];
    }
    
    
    public int Rear() {
        if (isEmpty() == true) {
            return -1;
        }
        return data[tail];
    }
    
    
    public boolean isEmpty() {
        return head == -1;
    }
    
    
    public boolean isFull() {
        return ((tail + 1) % size) == head;
    }
}

package dc;

import java.util.linkedList;
import java.util.Queue;


public class d13 {
    
    public static void main(String[] args) {
        MovingAverage m = new MovingAverage(3);
        System.out.println(m.next(1));
        System.out.println(m.next(10));
        System.out.println(m.next(3));
        System.out.println(m.next(5));
    }
}




class MovingAverage {
    private Queue queue;
    
    private int maxSize;

    //Initialize your data structure here.
    public MovingAverage(int Size) {
        queue = new linkedList();
        maxSize = Size;
    }

    public double next(int value){
        int sum = 0;
        if(queue.size()>=maxSize){
            
            queue.poll();
            queue.offer(value);
        } else{
            queue.offer(value);
        }
        for(Integer x:queue){
            sum+=x;
        }
        return (sum*1.0)/queue.size();
    }
}

package dc;

import java.util.linkedList;
import java.util.Queue;
import java.util.Arrays;
import java.util.List;


public class d14 {
    
    public static void main(String[] args) {
    }
}

class Solution {
    
    private static final int EMPTY = Integer.MAX_VALUE;
    private static final int GATE = 0;
    
    private static final List DIRECTIONS = Arrays.asList(
            new int[] { 1,  0},
            new int[] {-1,  0},
            new int[] { 0,  1},
            new int[] { 0, -1}
    );

    public void wallsAndGates(int[][] rooms) {
        
        int m = rooms.length;
        if (m == 0) return;
        int n = rooms[0].length;
        
        Queue q = new linkedList<>();
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (rooms[row][col] == GATE) {
                    q.add(new int[] { row, col });
                }
            }
        }
        
        while (!q.isEmpty()) {
            
            int[] point = q.poll();
            int row = point[0];
            int col = point[1];
            
            for (int[] direction : DIRECTIONS) {
                int r = row + direction[0];
                int c = col + direction[1];
                
                if (r < 0 || c < 0 || r >= m || c >= n || rooms[r][c] != EMPTY) {
                    continue;
                }
                
                rooms[r][c] = rooms[row][col] + 1;
                q.add(new int[] { r, c });
            }
        }
    }
}

class Solution1 {
    private int count = 0;

    
    public int numIslands(char[][] grid) {
        if(grid.length == 0 || grid[0].length == 0){
            return count;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        
        for(int i=0;i < m;i++){
            for(int j=0;j < n;j++){
                if(grid[i][j] == '1'){
                    
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    
    public void dfs(char[][] grid, int i, int j){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0'){
            return;
        }
        
        grid[i][j] = '0';
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 1);
    }
}