用棧實現(xiàn)隊列

方案一

要我們在插入元素的時候每次都都從前面插入即可，比如如果一個隊列是1,2,3,4，那么我們在棧中保存為4,3,2,1，那么返回棧頂元素1，也就是隊列的首元素，則問題迎刃而解。所以此題的難度是push函數(shù)，我們需要一個輔助棧tmp，把s的元素也逆著順序存入tmp中，此時加入新元素x，再把tmp中的元素存回來，這樣就是我們要的順序了，其他三個操作也就直接調(diào)用棧的操作即可。

上面那個解法雖然簡單，但是效率不高，因為每次在push的時候，都要翻轉(zhuǎn)兩邊棧，下面這個方法使用了兩個棧input和output，其中新進棧的都先緩存在input中，入股要pop和peek的時候，才將input中所有元素移到output中操作，提高了效率。

C-源代碼

typedef char LinkStackData;

//節(jié)點
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