The title
Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. (If there are no elements in the queue, the deleteHead operation returns -1)
Example 1:
Input: [” CQueue appendTail “, “”,” deleteHead “, “deleteHead”] [[], [3], [], []] output: [3, null, null, 1]
Example 2:
Input: [” CQueue deleteHead “, “”,” appendTail “, “appendTail”, “deleteHead”, “deleteHead”] [[], [], [5], [2], [], []] output: [null, 1, null, null, 5, 2]
Tip:
- 1 <= values <= 10000
- At most 10000 calls are made to appendTail and deleteHead
Train of thought
A queue is represented by two stacks. The first two stacks that come to mind store elements in turn. When queuing, all elements in stack 1 except the bottom of stack are removed from stack and put into stack 2, and then the only elements in stack 1 are removed, and finally all elements are put back into stack 1. Queue directly into the stack 1 can be. But this was too time inefficient, so we thought of two stacks of left delete and left insert operations.
Insert into stack 1, delete from stack 2, queue in is still directly into stack 1, and queue out is the top element from stack 2. First, check if stack 2 is empty, if not, pop it directly: if it is empty, push the element on stack 1 directly into stack 2, and then pop the element on top of stack. Of course, check to return -1 if there are no elements.
class CQueue {
public:
stack<int> stackOne;
stack<int> stackTwo;
CQueue(){}void appendTail(int value) {
stackOne.push(value);
}
int deleteHead() {
if(stackTwo.empty()) {
while(!stackOne.empty()) {
stackTwo.push(stackOne.top());
stackOne.pop();
}
}
if(stackTwo.empty())
return -1;
else {
int ans = stackTwo.top();
stackTwo.pop();
returnans; }}};/** * Your CQueue object will be instantiated and called as such: * CQueue* obj = new CQueue(); * obj->appendTail(value); * int param_2 = obj->deleteHead(); * /
Copy the code