數據結構與算法之隊列、棧

除了數組、鏈表，線性的數據結構中還有很重要的幾種結構： 隊列、棧 。

隊列，一種先進先出的數據結構（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