import java.util.Arrays;
public class MyStack implements IStack {
    private int[] elem;
    private int top;//數(shù)組的棧頂,以及數(shù)組棧中存放元素的數(shù)量
    private static final int DEFAULT_CAPACITY = 10;//這里是初始容量
    public MyStack() {
        elem = new int[DEFAULT_CAPACITY];
        top = -1;//數(shù)組下標(biāo)從0開始
    }
    @Override
    public void push(int item) {
        if (full()) {
            //如果滿了就擴(kuò)容
            elem = Arrays.copyOf(elem, 2 * elem.length);
        }
        elem[++top] = item;
    }
    @Override
    public int pop() throws RuntimeException {
        try {
            if (empty()) {
                throw new RuntimeException("棧為空");
            }
        } catch (RuntimeException e) {
            e.printStackTrace();
        }
        return elem[top--];//return返回后刪除棧頂?shù)脑?
    }
    @Override
    public int peek() {
        if (empty()) {
            throw new RuntimeException("棧為空");
        }
        return elem[top];//返回棧頂元素
    }
    @Override
    public int size() {
        return top+1;//去除數(shù)組0
    }
    @Override
    public boolean empty() {
        return top == -1;
    }
    @Override
    public boolean full() {
        return top == elem.length;//count==當(dāng)前的elem的總長(zhǎng)度為true
    }
}

public class MyQueue implements IQueue{
    static class Queue{
        public int elem;
        public Queue next;
        public Queue prev;
        public Queue(int elem) {
            this.elem = elem;
        }
    }
    public Queue head;
    public Queue last;
    public int size=0;
    @Override
    public void offer(int val) {
        Queue queue = new Queue(val);
        if (this.head == null) {
            this.head = queue;
            this.last = queue;
            ++size;
            return;
        }
        this.last.next=queue;
        this.last.prev=this.head;
        this.last=last.next;
        ++size;
    }
    @Override
    public int poll() {
        if(this.head==null){
            throw new RuntimeException("沒有要丟掉的隊(duì)列");
        }
        Queue cur =this.head;
        if(this.head.next==null){
            return -1;
        }
            this.head=this.head.next;
            this.head.prev=null;
            size--;
        return cur.elem;
    }
    @Override
    public int peek() {
        if(this.head!=null){
            return this.head.elem;
        }
        return 0;
    }
    @Override
    public int size() {
        return size;
    }
}

    private int[] array;
    private int front;
    private int rear;
    public MyCircularQueue(int k) {
        array=new int[k+1];
        front=0;//初始位置
        rear=0;
    }
    public boolean enQueue(int value) {
        //入列
        if(isFull()){
        //這里如果容量已經(jīng)滿了，需要先刪除后在進(jìn)行插入
            return false;
        }
        array[rear]=value;//rear下標(biāo)獲取元素
        rear=(rear+1)%array.length;//rear最終循環(huán)為0下標(biāo)
        return true;
    }
    public boolean deQueue() {
        //出列
        if(isEmpty()){
        //為空返回false
            return false;
        }
        front=(front+1)%array.length;//front只需要往后走
        return true;
    }
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return array[front];
    }
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        //這里三木操作符判斷是否為0如果為0，將rear回退到最后一個(gè)位置，不為0則-1
        int temp =  (rear==0)?array.length-1:rear-1;
        return array[temp];
    }
    public boolean isEmpty() {
        return front==rear;
    }
    public boolean isFull() {
        return (rear+1)%array.length==front;
    }
}

    Queue<Integer> q1;//主隊(duì)列
    Queue<Integer> q2;//輔助隊(duì)列
    public MyStack() {
        q1=new LinkedList<>();//構(gòu)造方法
        q2=new LinkedList<>();
    }
    public void push(int x) {
            q2.offer(x);
        while(!q1.isEmpty()){//主隊(duì)列不為空，則將主隊(duì)列出列給到輔助隊(duì)列
            q2.offer(q1.poll());
        }
        //走到這里主隊(duì)列是為空
        Queue tmp=q1;
        q1=q2;
        q2=tmp;
        //將兩個(gè)隊(duì)列交換
    }
    public int pop() {
        return q1.poll();
    }
    public int top() {
        return q1.peek();
    }
    public boolean empty() {
        return q1.isEmpty();
    }
}

class MyQueue {
    Stack<Integer> A;
    Stack<Integer> B;
    public MyQueue() {
        A=new Stack<>();
        B=new Stack<>();
    }
    public void push(int x) {
        A.push(x);
    }
    public int pop() {
        int check=peek();
        B.pop();
        return check;
    }
    public int peek() {
    //先判斷b是否是空的，如果不是空的直接返回，是空才可以往下走
               if(!B.isEmpty())return B.peek();
               //因?yàn)閎還不是空的，所以不需要將a棧放到b中
        if(A.isEmpty())return -1;
        while(!A.isEmpty()){
            B.push(A.pop());//將所有的a放到b中
        }
        return B.peek();
    }
    public boolean empty() {
        return A.isEmpty()&&B.isEmpty();
        //a和b都為空才為空
    }
}