0232-用栈实现队列

用栈实现队列

方案一

要我们在插入元素的时候每次都都从前面插入即可，比如如果一个队列是1,2,3,4，那么我们在栈中保存为4,3,2,1，那么返回栈顶元素1，也就是队列的首元素，则问题迎刃而解。所以此题的难度是push函数，我们需要一个辅助栈tmp，把s的元素也逆着顺序存入tmp中，此时加入新元素x，再把tmp中的元素存回来，这样就是我们要的顺序了，其他三个操作也就直接调用栈的操作即可。

上面那个解法虽然简单，但是效率不高，因为每次在push的时候，都要翻转两边栈，下面这个方法使用了两个栈input和output，其中新进栈的都先缓存在input中，入股要pop和peek的时候，才将input中所有元素移到output中操作，提高了效率。

C-源代码

typedef char LinkStackData;

//节点
typedef struct link_stack_node {
    LinkStackData data;
    struct link_stack_node *next;
}LinkStackNode;

typedef struct link_stack {
    LinkStackNode *top;//栈顶
    int count;//栈大小
}LinkStack;

LinkStack *linkStackCreate() {
    LinkStack *stack = NULL;
    
    stack = (LinkStack *)malloc(sizeof(LinkStack));
    if (stack == NULL) {
        return NULL;
    }
    
    stack->top = NULL;
    stack->count = 0;
    
    return stack;
}

bool linkStackIsEmpty(LinkStack *stack) {
    return stack->count == 0;
}


int linkStackPush(LinkStack *stack, LinkStackData data) {
    LinkStackNode *p = NULL;
    
    p = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    if (p == NULL) {
        return -1;
    }
    
    p->data = data;
    p->next = stack->top;
    stack->top = p;
    stack->count++;
    
    return 0;
}

int linkStackTop(LinkStack *stack, LinkStackData *data) {
    if (linkStackIsEmpty(stack)) {
        return -1;
    }
    
    LinkStackNode *p = stack->top;
    *data = p->data;
 
    return 0;
}

int linkStackPop(LinkStack *stack, LinkStackData *data) {
    if (linkStackIsEmpty(stack)) {
        return -1;
    }
    
    LinkStackNode *p = stack->top;
    *data = p->data;
    stack->top = p->next;
    stack->count--;
    
    free(p);
    
    return 0;
}

void linkStackDestory(LinkStack *stack) {
    LinkStackNode *p = NULL;
    
    while (stack->top) {
        p = stack->top;
        stack->top = p->next;
        stack->count--;
        free(p);
    }
    
    free(stack);
}
typedef struct {
    
    LinkStack *output;
    LinkStack *input;
} MyQueue;

MyQueue* myQueueCreate(int maxSize) {
    
    MyQueue *queue = (MyQueue *)malloc(sizeof(MyQueue));
    queue->output = linkStackCreate();
    queue->input = linkStackCreate();
    
    return queue;
}

void shiftStack(MyQueue *queue) {
    
    if (!linkStackIsEmpty(queue->output)) {
        
        return;
    }
    
    while (!linkStackIsEmpty(queue->input)) {
        
        char data;
        linkStackTop(queue->input, &data);
        linkStackPush(queue->output, data);
        linkStackPop(queue->input, &data);
    }
}

void myQueuePush(MyQueue* obj, int x) {
    
    linkStackPush(obj->input, x);
}

int myQueuePop(MyQueue* obj) {
    
    shiftStack(obj);
    
    char data;
    linkStackPop(obj->output, &data);
    
    return data;
}

int myQueuePeek(MyQueue* obj) {
    
    shiftStack(obj);
    
    char data;
    linkStackTop(obj->output, &data);
    
    return data;
}

bool myQueueEmpty(MyQueue* obj) {
    
    return linkStackIsEmpty(obj->output) && linkStackIsEmpty(obj->input);
}

void myQueueFree(MyQueue* obj) {
    
    linkStackDestory(obj->output);
    linkStackDestory(obj->input);
    free(obj);
}

void test_0232(void) {
    MyQueue *queue = myQueueCreate(5);
    myQueuePush(queue, 1);
    myQueuePush(queue, 2);
    myQueuePush(queue, 3);
    myQueuePush(queue, 4);
    
    while (!myQueueEmpty(queue)) {
        int data = myQueuePop(queue);
        printf("%d\n",data);
    }
}

参考Grandyang