题解 | #两个队列实现栈#

队列部分可以跳过↓

struct Node{
    int data;
    struct Node *next;
};

struct QNode{
    struct Node *rear; // add
    struct Node *front; // delete
};

typedef struct QNode * Queue;

Queue CreateQueue(){
    struct QNode *tmp1;
    tmp1 = (struct QNode *)malloc(sizeof(struct QNode*));
    tmp1->front = NULL;
    tmp1->rear = NULL;
    return tmp1;
}

void addQ(Queue PtrQ, int item){
    struct Node *tmp;
    tmp = (struct Node*)malloc(sizeof(struct Node*));
    tmp->data = item;
    tmp->next = NULL;
    if(PtrQ->front == NULL){
        PtrQ->front = tmp;
        PtrQ->rear = tmp;
    }
    else{
        PtrQ->rear->next = tmp;
        PtrQ->rear = PtrQ->rear->next;
    }
}

int deleteQ(Queue PtrQ){
    struct Node *tmp;
    int item;
    tmp = (struct Node*)malloc(sizeof(struct Node*));
    if(PtrQ->front == NULL){
        return -1001; // error
    }
    tmp = PtrQ->front;
    item = tmp->data;
    if(PtrQ->front == PtrQ->rear){
        PtrQ->front = NULL;
        PtrQ->rear = NULL;
    }
    else{
        PtrQ->front = tmp->next;
    }
    free(tmp);
    return item;
}

队列部分可以跳过↑

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param element int整型 
 * @return 无
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
static Queue q1;
static Queue q2;

// 一个队列负责按照队列的形式存储数据
void push(int element) {
    if(q1 == NULL){
        q1 = CreateQueue();
    }
    addQ(q1, element);
}

// 将除了最后进入队列的数据搬运到新队列（q2），返回最后一个进入q1的数据
int pop() {
    int item;
    q2 = CreateQueue();
    while(q1->front->next != NULL){
        addQ(q2, deleteQ(q1));
    }
    item = deleteQ(q1);
    q1 = q2;
    return item;
}

int top() {
    return q1->rear->data;
}

bool empty() {
    if(q1 == NULL){
        q1 = CreateQueue();
    }
    if(q1->front == NULL && q1->rear == NULL){
        return true;
    }
    else{
        return false;
    }
}

想法参考