队列/两个队列实现一个栈

谁践踏了优雅 2021-09-23 07:02 405阅读 0赞

### 顺序队列的实现 ###

/**
     * @auther: 巨未
     * @DATE: 2019/1/5  20:17
     * @Description: 顺序队列
     */
    class Cqueue{
        private int front;
        private int rear;
        private int[] elem;
        private int usedSize; //有序数据个数
        private int allSize = 0; //总共的大小
    
        public Cqueue(){
            this(10);
        }
        public Cqueue(int size){
            this.elem = new int[size];
            this.front = 0;
            this.rear = 0;
            this.usedSize = 0;
        }
        /*是否为满*/
        public boolean isFull(){
            if((rear+1)%allSize == front) {    //7+1   %8   =0
                return true;
            }
            return false;
        }
        /*入队*/
        public void push(int val) {
            if(isFull()) {
                return;
            }
            this.elem[this.rear] = val;   //rear不能++
            this.rear = (this.rear+1)%allSize; // 1+1  %8 == 1
            this.usedSize++;
        }
        /*是否为空*/
        public  boolean isEmpty(){
            if(this.rear == this.front){
               return true;
            }
            return false;
        }
        /*出队*/
        public int pop(){
            if(isEmpty()){
                throw new UnsupportedOperationException("队列为空");
            }
           int num = this.elem[this.front];
            this.front = (this.front+1) % allSize;
            this.usedSize --;
            return num;
        }
        /*得到队头元素*/
        public int getTop(){
            if(isEmpty()){
                throw new UnsupportedOperationException("队列为空");
            }
            return this.elem[this.front];
        }
        /*打印*/
        public void show(){
            for (int i = this.front; i != this.rear; i = (i+1)%allSize) {
                System.out.print(this.elem[i]+ " ");
            }
            System.out.println();
        }
        public int getUsedSize(){
            return this.usedSize;
        }
    
    
    }

### 两个队列实现一个栈 ###

public class CqueueDemo {
        /*两个队列实现一个栈：入栈*/
        public static void pushStack(Cqueue qu1,Cqueue qu2,int val){
            Cqueue queue ; //要入队的队列
            if(!qu1.isEmpty()){
                queue = qu1;
            }else{
                queue = qu2;
            }
            queue.push(val);
        }
        /*两个队列实现一个栈：出栈*/
        public static int popStcak(Cqueue qu1,Cqueue qu2){
            Cqueue pQueue1; //要出队的那个队列
            Cqueue pQueue2; //从pQueue1出队的数据放到pQueue2
            if(!qu1.isEmpty()){
                pQueue1 = qu1;
                pQueue2 = qu2;
            }else {
                pQueue1 = qu2;
                pQueue2 = qu1;
            }
            int tmp = 0;
            if(pQueue1.isEmpty()){
                System.out.println("is Empty");
            }else{  //将pQueue的数据出的只剩下一个，放入pQueue2
    
                while(pQueue1.getUsedSize()>1) {
                   tmp = pQueue1.pop();
                    pQueue2.push(tmp);
                }
               return pQueue1.pop();
                }
                return -1;
            }
    
        public static void main(String[] args) {
          Cqueue cqueue = new Cqueue();
          cqueue.push(10);
            cqueue.push(20);
            cqueue.push(31);
            cqueue.push(40);
            cqueue.show();
            System.out.println(cqueue.pop());
            cqueue.show();
            cqueue.getTop();
        }
    }