about Queue and Stack

Wed, Sep 1, 2021 3-minute read

quick way to know Queue and Stack

Implement Stack using Queues 225

这题其实要考虑这个系统是 read heave 还是 write heave，影响后面你用 push O(n) 还是 pop O(n)的解法

push heavy

push O(1)

pop O(n)

记录了一个 top， poll（）的时候看看 q1 的 size 是不是大于 1，是的话就 poll(), 随时更新 top，这样看 top 的时候就可以很快，然后后面交换地址。

 int top;
    public void push(int x) {
        q1.offer(x);
        top = x;
    }
    
    public int pop() {
        while (q1.size() > 1) {
            top = q1.poll();
            q2.offer(top);
        }
        int value = q1.poll();
        Queue<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;
        return value;
    }
    
    public int top() {
        return top;
    }

这个就像水杯倒水一样，永远用空杯子去接水，所以杯子有水就倒倒杯子 2 中，

 public void push(int x) {
        if (q1.isEmpty()) {
            q1.offer(x);
        }
        while (!q2.isEmpty()) {
            q1.offer(q2.poll());
        }
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
    }
    
    public int pop() {
      return q2.poll();
    }
    
    public int top() {
        return q2.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }

那其实用 liskedlist 是可以达到 o1 操作的，因为加入头是 O1, 所以已进入一个新元素就是加入头，

e java.util.LinkedList.poll() method retrieves and removes the head (first element) of this list

public MyStack() {
    this.queue = new LinkedList<>();
}

 public void push(int x) {
        Queue<Integer> tmp = new LinkedList<>();
        tmp.add(x);
        tmp.addAll(this.queue);
        this.queue = tmp;
    
    public int pop() {
      return this.queue.poll();
    }
    
    public int top() {
        return this.queue.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }

Design Circular Queue 622

普通列表中

头指针，尾指针

物理意义，head 是有数据的位置， tail 是数据将要塞进去的位置

head tail 1 2

初始化： head = tail = -1, 也可以是 head = 0，就看物理意义

满: tail = size - 1， size 是初始化队列大小

空： tail = head

那如果是入站入站，tail 到了尾部，出站出战，head 到了 tail 位置，这时候是空还是满？

循环来了

循环列表实现 1

初始化： head = tail = 0, head = 0，就看物理意义

满 (tail + 1) % size = head ，浪费一个空间，但是可以空间换时间。

循环列表实现 2

新增一个容量 capacity 字段，并进行维护，当 capacity=size 表示队列已满

每次入队和出队时候都需要维护 capacity 字段

循环列表实现 3

再维护一个标记，或者当 head=tail 时同步判断当前位置是否有元素来判断当前是队空还是队满，不论队列空或者队列满时都要多一次判断方式。当数据量并发量很大时，多一次判断其实也是会对性能有所影响，常规的循环链表会采用方法 1 进行处理，也就是选择浪费一个空间的方式。

但是这个题目，里面案例是不容许空一格，所以用第三个进行判断，所以初始化： head = tail = -1.

上题中我思考过 head = -1 如何，结果因为要用 tail enque，所以 head 不在 0 位置上，deque 时候就处于 - 1，逻辑不通。


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

I'm Riley Shen