LeetCode 用两个栈实现队列

布满荆棘的人生 2023-02-21 12:49 20阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]

#### 思路： ####

定义两个栈A,B，添加元素时全部加到A中，栈A专门用来第一次添加元素，栈B是为了实现队列删除元素的特点而将元素从A中弹出到B中。  
然后当需要删除元素时分三种情况，  
1、A不空，B空此时第一次删除，将A中元素全部加入到B中，删除。  
2、B不空，直接删除B栈顶元素。  
3、A空B空，返回-1

class CQueue { 
        stack<int> stack1,stack2;
    public:
        CQueue() { 
    
        }
        
        void appendTail(int value) { 
            stack1.push(value);
        }
        
        int deleteHead() { 
            if(!stack2.empty()){ 
                int value = stack2.top();//top并不删除元素，pop删除元素但返回值为null
                stack2.pop();
                return value;
            }
            if(stack1.empty()){ return -1;}
            while(!stack1.empty()){ 
                stack2.push(stack1.top());
                stack1.pop();
            }
            int value = stack2.top();
            stack2.pop();
            return value;
        }
    };
    
    /** * Your CQueue object will be instantiated and called as such: * CQueue* obj = new CQueue(); * obj->appendTail(value); * int param_2 = obj->deleteHead(); */

##### java实现利用linkedlist #####

class CQueue { 
       LinkedList<Integer> A,B;
       public CQueue() { 
           A = new LinkedList<Integer>();
           B = new LinkedList<Integer>();
       }
       
       public void appendTail(int value) { 
           A.add(value);
       }
       
       public int deleteHead() { 
           if(!B.isEmpty()){ return B.remove();}
           if(A.isEmpty()){ return -1;}
           while(!A.isEmpty()){ 
               B.add( A.remove());
           }
           return B.remove();
       }
    }
    
    /** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200630205856727.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ==,size_16,color_FFFFFF,t_70