数据结构与算法之队列、栈

　　除了数组、链表，线性的数据结构中还有很重要的几种结构：队列、栈。

　　队列，一种先进先出的数据结构（FIFO），其实队列可以看成是一个两个口的管道，从一个口进，另一个口出，先进去的必定得在另一个口先出去，否则后面的都出不去；栈，一种后进先出的数据结构（LIFO），栈更像是只有一个口的管道，只有一个开口可以进出，先进去的在底部，所以必须得让后进去的先出去，它才能出去。

　　实现队列和栈可以用顺序存储结构，也可以用链式存储结构。这里采用的是链表来实现，同时还有用两个栈实现一个队列和用两个队列实现一个栈的算法（采用STL中的queue和stack）。

1、队列

　　队列中最常用的操作就是入队列（push），出队列（pop)，查看队首的值（front）。入队列是加入队列的尾部，出队列是删除最前面的节点。

typedef struct ListNode{
    int element;
    int *next;
}ListNode;
typedef struct LinkedQueue{
    int size;
    ListNode *front;
    ListNode *back;
}LinkedQueue;

/* alloc a node.*/
ListNode* allocNode(int element){
    ListNode *pNode = (ListNode*)malloc(sizeof(ListNode));
    if(pNode){
        pNode->element = elemnt;
        pNode->next = NULL;
    }
    return pNode;
}

/* alloc a queue.*/
LinkedQueue* allocLinkedQueue(){
    LinkedQueue *pQueue = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    if(pQueue){
        pQueue->size = 0;
        pQueue->front = NULL;
        pQueue->back = NULL;
    }
    return pQueue;
}

/* pop a node out of the queue.*/
bool pop(LinkedQueue *pQueue){
    if(NULL == pQueue)
       return false;
    LinkedQueue *pNode = pQueue->front;
    if(pQueue->front == pQueue->back)
        pQueue->back = NULL;
    pQueue->front = pQueue->front->next;
    free(pNode);
    pQueue->size --;
    return true;
}

/* push a node into the queue.*/
bool push(LinkedQueue *pQueue,int element){
    if(NULL == pQueue)
        return false;
    pQueue->size ++;
    if(NULL == pQueue->front){
        pQueue->front = pQueue->back = allocNode(element);
    }
    else
        pQueue->back = allocNode(element);
    return true;
}

/* get the front element from the queue.*/
bool front(LinkedQueue *pQueue,int *element){
    if(pQueue->size){
        *element = pQueue->front->element;
        return true;
    }
    else
        return false;
}

2、栈

　　栈中最常用的操作就是入栈（push），出栈（pop)，查看栈顶的值（front）。入栈是加入栈的顶部，出栈删除栈顶的节点。

typedef struct ListNode{
    int element;
    struct ListNode *next;
}ListNode;
typedef struct LinkedStack{
    ListNode *topNode;
    ListNode *downNode;
    int stackLength;
}LinkedStack;

/* get the top node from the stack.*/
int top(LinkedStack *pStack){
   return pStack->topNode->element; 
}

/* pop the top node from the stack.*/
void pop(LinkedStack **pStack){
    ListNode *pNode = (*pStack)->topNode->next;
    free(*pStack);
    *pStack = pNode;
}

ListNode* allocNode(int element){
    ListNode *pNode = (ListNode*)malloc(sizeof(ListNode));
    if(NULL != pNode){
        pNode->element = element;
        pNode->next = NULL;
    }
    return pNode;
}

/* push a node into the stack.*/
void push(LinkedStack **pStack,int element){
    ListNode *pNode = allocNode(element);
    pNode->next = (*pStack)->topNode;
    (*pStack)->topNode = pNode;
}

3、用两个栈实现一个队列

　　队列是先进先出，而栈是后进先出，怎么在栈中实现让一个元素先进先出？关键是利用好另一个栈。队列中主要的操作也不过就是push(),pop(),front()。

　　实现push就跟栈中的push一样，完全不需要修改。而要实现pop和front呢？这就需要借助另一个栈。首先在栈stack1中push，当有pop或者front操作时，我们把元素从stack1中出栈并压入stack2中。这样stack1中底部的元素就变为stack2顶部的元素了，然后从stack2中执行pop或者front操作。以后的pop或者front操作，都先从stack2中执行，当stack2中元素size为0时，就从stack1中出栈并压入stack2中然后执行；而每次pop操作只需要在stack1中执行。

bool pop(){
    if(!pQueue.stack2.size() && !pQueue.stack1.size())
        return false;
    if(!pQueue.stack2.size()){
        while(pQueue.stack1.size()){
            pQueue.stack2.push(pQueue.stack1.top());
            pQueue.stack1.pop();
        }
    }
    pQueue.stack2.pop();
    return true;
}

int front(){
    if(!pQueue.stack2.size()){
        while(pQueue.stack1.size()){
            pQueue.stack2.push(pQueue.stack1.top());
            pQueue.stack1.pop();
        }
    }
    return pQueue.stack2.top();
} 

4、用两个队列实现一个栈

　　栈中最主要的操作就是push(),pop(),top()。

　　push操作每次把元素加入到queue1中即可，而pop和top操作就需要借助另一个队列了。假设queue1中压入了5个元素：1,2,3,4,5。则此时需要pop，也就是删除元素5。那么现在就需要把元素1,2,3,4pop了，才能pop元素5，但是栈操作中元素1,2,3,4不应该被pop掉,所以，就需要把1,2,3,4push到queue2中。每次pop操作,就先检查queue1中是否有元素，如果有n个元素，就把前面的n-1个元素pop,然后push到queue2中，然后执行pop；否则，就先把queue2中的n-1元素转移到queue1中，然后执行pop操作。top操作与pop操作类似。

bool pop(){
    if(!pStack.queue1.size() && !pStack.queue2.size())
        return false;
    
    if(pStack.queue1.size())    {
        while(pStack.queue1.size() != 1){
            pStack.queue2.push(pStack.queue1.front());
            pStack.queue1.pop();
        }
        pStack.queue1.pop();
        return true;
    }
    else{
        while(pStack.queue2.size() != 1){
            pStack.queue1.push(pStack.queue2.front());
            pStack.queue2.pop();
        }
        pStack.queue2.pop();
        return true;
    }
}

int top(){
    if(pStack.queue1.size())    {
        while(pStack.queue1.size() != 1){
            pStack.queue2.push(pStack.queue1.front());
            pStack.queue1.pop();
        }
        return pStack.queue1.front();
    }
    else{
        while(pStack.queue2.size() != 1){
            pStack.queue1.push(pStack.queue2.front());
            pStack.queue2.pop();
        }
        int top = pStack.queue2.front();
        pStack.queue2.pop()
        pStack.queue1.push(top);
        return top;
    }
}

完整代码详见：https://github.com/whc2uestc/DataStructure-Algorithm