【栈和队列】用栈实现队列

做题时思路：（正确）

1. 先实现栈的算法。
2. 设立队列的结构为两个栈s1和s2，s1为存储栈（存储元素），s2为辅助栈，辅助实现算法
3. 取出元素时将s1中所有元素pop到s2中，然后取出s2栈顶元素（队列中应取出元素）。然后再将所有元素放回s1

//先实现栈，再用栈的算法实现队列
typedef struct StackNode {
    struct StackNode* next;
    int val;
}StackNode;

typedef struct MyStack {
    StackNode head;
}MyStack;

void InitStack(MyStack* s) {
    s->head.next = 0;
    s->head.next = NULL;
}

int StackPush(MyStack* s, int x) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->val = x;
    newNode->next = s->head.next;
    s->head.next = newNode;
    s->head.val++;
    return 0;
}

int StackPop(MyStack* s) {
    int result = 0;
    if (s->head.next == NULL) {
        printf("栈为空");
        exit(-1);
    }
    else {
        StackNode* newNode = s->head.next;
        s->head.next = s->head.next->next;
        result = newNode->val;
        free(newNode);
        return result;
    }
}

int StackEmpty(MyStack* s) {
    return s->head.next == NULL;
}

int StackPeek(MyStack* s) {
    return s->head.next->val;
}

//用一个栈存储元素，当要取出元素时，将所有元素都弹出，然后放入到另一个栈中。取出最底层元素，然后再将所有元素放回原栈中
//s1为存储的存储栈。s2为辅助实现算法的功能栈
typedef struct {
    MyStack s1;
    MyStack s2;
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
		//开辟一个队列的空间，并初始化队列中的两个栈
    MyQueue* mq = (MyQueue*)malloc(sizeof(MyQueue));
    InitStack(&(mq->s1));
    InitStack(&(mq->s2));
    return mq;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
		//将
    StackPush(&(obj->s1),x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    int res = 0;
		//将s1中元素全部取出，放入s2中。这样可以让s1栈底元素（第一个元素），到s2栈顶，方便操作
    while(!StackEmpty(&(obj->s1))) {
        StackPush(&(obj->s2),StackPop(&(obj->s1)));
    }
		//取出s2栈顶元素
    res = StackPop(&(obj->s2));
		//将其余元素再放入s1
    while(!StackEmpty(&(obj->s2))) {
        StackPush(&(obj->s1),StackPop(&(obj->s2)));
    }
    return res;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    int res = 0;
    while(!StackEmpty(&(obj->s1))) {
        StackPush(&(obj->s2),StackPop(&(obj->s1)));
    }
    res = StackPeek(&(obj->s2));
    while(!StackEmpty(&(obj->s2))) {
        StackPush(&(obj->s1),StackPop(&(obj->s2)));
    }
    return res;
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&(obj->s1));
}

void myQueueFree(MyQueue* obj) {

}

官方答案：（优化）

1. 当我们将数据从s1出栈到s2后，不用再压栈回去。下次取数据时可以判断s2是否为空，如果是，则直接从s2取数据就可以，否则再从s1出栈
2. 主要改变了myQueuePop、myQueuePeek和myQueueEmpty三个函数

int myQueuePop(MyQueue* obj) {
    int res = 0;
    if(StackEmpty(&(obj->s2))) {
        while(!StackEmpty(&(obj->s1))) {
            StackPush(&(obj->s2),StackPop(&(obj->s1)));
        }
    }
    res = StackPop(&(obj->s2));
    return res;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    int res = 0;
    if(StackEmpty(&(obj->s2))) {
        while(!StackEmpty(&(obj->s1))) {
            StackPush(&(obj->s2),StackPop(&(obj->s1)));
        }
    }
    res = StackPeek(&(obj->s2));
    return res;
}

/** Returns whether the queue is empty. */
//现在s1和s2中必须都没有元素队列才为空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&(obj->s1))&&StackEmpty(&(obj->s2));
}