Sword finger offer:[day 1 stack and queue (simple)] --- > use two stacks to realize the queue

---

One 、 Title Description

Use two stacks to implement a queue . The declaration of the queue is as follows , Please implement its two functions appendTail and deleteHead, The functions of inserting integers at the end of the queue and deleting integers at the head of the queue are respectively completed .( If there are no elements in the queue ,deleteHead Operation return -1 )

Example 1：

Input ：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
Output ：[null,null,3,-1]

Example 2：

Input ：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
Output ：[null,-1,null,null,5,2]

Tips ：

1 <= values <= 10000
At most appendTail、deleteHead Conduct 10000 Secondary call

Two 、 Thought analysis

notes ： Some contents and pictures in the analysis of ideas are for reference. I'll make a self-help deduction for you, seniors , Thank them for their selfless dedication

Topic interpretation

["CQueue","appendTail","deleteHead","deleteHead"] 
 This line represents the operation of each line of code 

[[],[3],[],[]]
 This represents the parameters corresponding to each line of code operation .[] Represents that there are no parameters ,[3] The parameters representing this operation are 3

 give an example ：
CQueue  Means to create a new CQueue object , The corresponding required parameters are [], That is, this operation does not require parameters .
appendTail  It means to execute a appendTail() operation , The corresponding element to be operated is 3.
deleteHead  It means to execute a deleteHead operation , The corresponding required parameters are [], That is, this operation does not require parameters .
deleteHead  It means to execute a deleteHead operation , The corresponding required parameters are [], That is, this operation does not require parameters .

Thought analysis

Queue up operation of stack and queue 、 The out of queue operation is shown in the following figure ：

It can be seen that ：
① The queue operation is basically the same as the stack operation , Are inserted backward in turn .
② When the team , Pop up the team head element . And we only have stacks here , The element at the head of the queue corresponds to the element at the bottom of the stack , We can't directly pop up the elements at the bottom of the stack .
Solution ： You can pop up all the elements of the stack in turn , Put it on another stack . Suppose you have a stack of three elements A=[1,2,3] Empty stack B=[]. If the A And add the element to the stack B , Until the stack A It's empty , be A=[], B=[3,2,1]. It can be seen that , The stack B The top element of the stack is the stack A At the bottom of the stack , The first element of the team . meanwhile , To continue popping the first element , You can continue to pop up directly B Top element of .

3、 ... and 、 The overall code

The overall code is as follows

#define MAX 10000
typedef struct {
    
    int *Stack1; // Stack 1
    int *Stack2; // Stack 2
    int top1;    // Pointing stack 1 Top element of 
    int top2;    // Pointing stack 2 Top element of 
} CQueue;


CQueue* cQueueCreate() {
    
    CQueue* C = (CQueue*)malloc(sizeof(CQueue)); // Create a queue 
    C->Stack1 = (int*)malloc(sizeof(int)*MAX);   // Create a stack 1
    C->top1 = -1;                                // Stack 1 There are no elements at this time ,top1=-1
    C->Stack2 = (int*)malloc(sizeof(int)*MAX);   // Create a stack 2
    C->top2 = -1;                                // Stack 2 There are no elements at this time ,top2=-1
    return C;
}

void cQueueAppendTail(CQueue* obj, int value) {
    
    //top1+1, And will vlue Assign a value to Stack1[top+1]
    obj->Stack1[++obj->top1] = value;
}

int cQueueDeleteHead(CQueue* obj) {
    
    if(obj->top2 != -1){
    
        //Stack2 Not empty , Go straight back to Stack2 Top element of , And let top2-1
        return obj->Stack2[obj->top2--];
    }
    else{
    
        while(obj->top1 != -1){
     
            //Stack2 It's empty ,Stack1 Not empty , At this time will be Stack1 The elements of are pressed to Stack2 in 
            obj->Stack2[++obj->top2] = obj->Stack1[obj->top1--];
        }
        // take Stack1 Element pressed to Stack2 At the end of , here Stack1 It's empty 
        // Check Stack2 Is it empty , If it is empty, there are no elements in the queue . If it is not empty, return Stack2 Top element of 
        return obj->top2==-1? -1 : obj->Stack2[obj->top2--];
    }

}

void cQueueFree(CQueue* obj) {
    
    free(obj->Stack1);
    free(obj->Stack2);
    free(obj);
}

/** * Your CQueue struct will be instantiated and called as such: * CQueue* obj = cQueueCreate(); * cQueueAppendTail(obj, value); * int param_2 = cQueueDeleteHead(obj); * cQueueFree(obj); */

function , Verification passed