转载

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

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

队列,一种先进先出的数据结构(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

正文到此结束
Loading...