题目描述:
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )
示例 1:
输入:
[“CQueue”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[3],[],[]]
输出:[null,null,3,-1]
示例 2:
输入:
[“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]
解题思路:
在进行这两个操作的时候要注意先要清空其中一个栈,这样子才比较好
1、添加到尾部:由于栈就是先进后出的特点,所以可以直接压入栈就是相当于添加到尾部
2、删除头部元素:可以直接将其中一个栈的全部元素依次压入另外一个栈,这样子在被压入的那个栈的栈顶就是原先栈的头部元素,直接使用栈的pop()方法就可以了
class CQueue { public: CQueue() { s1=new stack<int>; s2=new stack<int>; } void appendTail(int value) { s1->push(value); } int deleteHead() { if(s2->size()<=0){ while(s1->size()>0){ int top=s1->top(); s1->pop(); s2->push(top); } } if(s2->size()==0) return -1; int head=s2->top(); s2->pop(); return head; } private: stack<int>* s1; stack<int>* s2; };
执行结果如图
Java版的
class CQueue { Stack<Integer> stack1; Stack<Integer> stack2; public CQueue() { stack1 = new Stack<Integer>(); stack2 = new Stack<Integer>(); } public void appendTail(int value) { //将stack2全部清空并依次压入stack1 while(!stack2.isEmpty()) { stack1.push(stack2.pop()); } stack1.push(value); } public int deleteHead() { //将stack1清空,并将stack1的数据全部依次压入stack2 while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } if(stack2.isEmpty()){ return -1; } //此时stack2的栈顶元素就是stack1的栈底元素,所以可以直接使用stack2.pop()来进行达到删除头结点的目的 return stack2.pop(); } } /** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */