摘要

　　本章介绍了几种基本的数据结构，包括栈、队列、链表以及有根树，讨论了使用指针的简单数据结构来表示动态集合。本章的内容对于学过数据结构的人来说，没有什么难处，简单的总结一下。

1、栈和队列

　　栈和队列都是动态集合，元素的出入是规定好的。栈规定元素是先进后出（FILO），队列规定元素是先进先出（FIFO）。栈和队列的实现可以采用数组和链表进行实现。在标准模块库STL中有具体的应用，可以参考。

　　栈的基本操作包括入栈push和出栈pop，栈有一个栈顶指针top，指向最新如栈的元素，入栈和出栈操作操作都是从栈顶端进行的。

　　队列的基本操作包括入队enqueue和出队dequeue，队列有队头head和队尾tail指针。元素总是从队头出，从队尾入。采用数组实现队列时候，为了合理利用空间，可以采用循环实现队列空间的有效利用。

　　关于栈和队列的基本操作如下图所示：

采用数组简单实现一下栈和队列，实现队列时候，长度为n的数组最多可以含有n-1个元素，循环利用，这样方便判断队列是空还是满。

栈的C++程序如下所示：

#include
     
      #include
      
       using namespace std;typedef struct stack { int *s; int stacksize; int top; }stack; void init_stack(stack *s,int n) { s->stacksize=n; s->s=(int*)malloc(sizeof(int)*s->stacksize); s->top=0; } bool stack_empty(stack *s) { if(s->top==0) return true; else return false; } bool stack_full(stack *s) { if(s->top==s->stacksize) return true; else return false; } void push(stack *s,int x) { if(stack_full(s)) { cout<<"overflow"<
       
        top=s->top+1; s->s[s->top]=x; } int pop(stack *s) { int x; if(stack_empty(s)) { cout<<"underflow"<
        
         s[s->top]; s->top--; return x; } int top(stack *s) { return s->s[s->top]; } int main() { stack s; init_stack(&s,100); push(&s,19); push(&s,23); push(&s,34); push(&s,76); push(&s,65); cout<<"top is "<
         
          <
         
        
       
      
     

队列的C++代码实现：

#include
     
      #include
      
       using namespace std;typedef struct queue { int *q; int head,tail; int queuesize; }queue; void init_queue(queue *q,int n) { q->queuesize=n; q->q=(int*)malloc(sizeof(int)*q->queuesize); q->tail=q->head=0; } bool queue_empty(queue *q) { if(q->head==q->tail) return true; else return false; } bool queue_full(queue *q) { if(q->tail+1==q->head) return true; else return false; } int queue_length(queue *q) { return (q->tail-q->head+q->queuesize)%q->queuesize; } void enqueue(queue *q,int x) { if(queue_full(q)) { cout<<"queue overflow"<
       
        q[q->tail]=x; q->tail=(q->tail+1)%q->queuesize; } int dequeue(queue *q) { int x; if(queue_empty(q)) { cout<<"queue underflow"<
        
         q[q->head]; q->head=(q->head+1)%q->queuesize; return x; } int main() { queue q; init_queue(&q,100); enqueue(&q,10); enqueue(&q,30); cout<<"head: "<
         
          <<" tail: "<
          
           <
          
         
        
       
      
     

问题：

（1）说明如何用两个栈实现一个队列，并分析有关队列操作的运行时间。（始终用一个栈做为出，一个栈作为入队）

解答：栈中的元素是先进后出，而队列中的元素是先进先出。现有栈s1和s2，s1中存放队列中的结果，s2辅助转换s1为队列。

入队时，将元素压入s1。

出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。

（如果s1满了，s2既没有装满也不是非空，此时就不能继续入队了；如果s1满了，但s2是空的，则可以先将s1中的元素压人s2中，然后再进队。）

#include
     
      #include
      
       #include
       
        using namespace std;template 
        
         class StackToQueue { public: T dequeue(); void enqueue(const T &node); StackToQueue(){} ~StackToQueue(){} private: stack
         
           stack1; stack
          
            stack2; }; template 
           
             void StackToQueue
            
             ::enqueue(const T &node) { stack1.push(node); } template 
             
               T StackToQueue
              
               ::dequeue() { if(stack2.empty()&&stack1.empty()) { cout<<"underflow"<
               

sq; sq.enqueue(1); sq.enqueue(2); sq.enqueue(3); cout<

<