C实现栈和队列

这两天再学习了数据结构的栈和队列，思想很简单，可能是学习PHP那会没有直接使用栈和队列，写的太少，所以 用具体代码实现的时候出现了各种错误 ，感觉还是C语言功底不行。栈和队列不论在面试中还是笔试中都很重要，下面就介绍一下这两天栈和队列的学习经验

一：栈的学习

基础东西：栈是在表尾进行插入和删除的线性表，由此可知表尾是栈顶，表头为栈底，没有任何元素的栈是空栈。根据栈的结构可以知道：栈修改是按后进先出的原则进行的（LIFO），基本操作有插入、删除、初始化、取栈顶元素，判断是否是空栈等等。

栈的表示和实现：和上一节介绍过的线性表相似栈有两种表示方法（顺序表示和链式表示）因为和线性表类似（特殊的线性表）我只介绍顺序栈的就可以了。

顺序栈：利用一组连续的地址来依次存储栈的各个元素（从栈底到栈顶），用top指针指示栈顶元素，base指针指示栈底元素，所以top=base可以作为空栈的判断。插入一个元素top++，出栈一个元素top--，所以非空栈的指针始终在栈顶元素的下一个位置

顺序栈的结构体表示：

1 //栈的顺序存储表示 2 typedef struct{ 3     SElemType *base;//在栈构造之前和销毁后值是NULL 4     SElemType *top; 5     int stacksize; //已分配的存储空间 6 }SqStack;

下面是我练习的代码，实现了栈的定义、栈的初始化、进栈操作、出栈操作、得到栈顶元素、遍历栈。需要注意的是出栈操作和得到栈顶元素的操作是有区别的，希望对大家栈的学习和回顾有所帮助。 代码都是自己练习过的，可以直接运行

  1 /**   2  * 栈   3  * @author:zhaoyafei   4  * @time:2015-6-16   5  */   6 #include <stdio.h>   7 #include <stdlib.h>   8    9 //预定义常量  10 #define OK 1  11 #define OVERFLOW -2  12 #define ERROR 0  13   14 #define STACK_INIT_SIZE 100 //存储空间的初始分配量  15 #define STACKINCREMENT 10   //存储空间的分配增量stackincrement  16   17 typedef int SElemType;  18   19 //栈的顺序存储表示  20 typedef struct{  21     SElemType *base;//在栈构造之前和销毁后值是NULL  22     SElemType *top;  23     int stacksize; //已分配的存储空间  24 }SqStack;  25   26 //栈的初始化操作  27   28 int InitStack(SqStack &S){  29     S.base = (int *)malloc(STACK_INIT_SIZE * sizeof(SqStack));  30     if(!S.base){  31         exit(OVERFLOW);//分配空间失败  32     }  33     S.top = S.base;  34     S.stacksize = STACK_INIT_SIZE;  35     return OK;  36 }  37   38 //进栈操作  39 int Push(SqStack &S, int e){  40     if(S.top - S.base >= S.stacksize){//栈空间已经满  41         S.base = (int *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SqStack));  42         if(!S.base){  43             exit(OVERFLOW);//分配失败  44         }  45         S.top = S.base + S.stacksize;  46         S.stacksize += STACKINCREMENT;  47     }  48     *S.top++ = e;  49     return OK;  50 }  51   52 //出栈  53 int Pop(SqStack &S,int &e){  54     if(S.top != S.base){  55         e = * --S.top;  56         return OK;  57     }else{  58         exit(OVERFLOW);  59     }  60 }  61   62 //得到顶部元素  63 void GetElem(SqStack S, int &e){  64     if(S.top != S.base){  65         e = * (S.top - 1);  66     }else{  67         exit(OVERFLOW);  68     }  69 }  70   71 //打印出栈各个元素  72 void PrintfStack(SqStack S){  73     while(*(S.top-1) && S.top != S.base){//证明不是空栈,且有值  74         S.top = S.top - 1;  75         printf("%d ",*S.top);  76     }  77     printf("/n");  78 }  79   80 int main(){  81     int e,i;  82     int TextData[6] = {9,2,8,1,7,6};  83     SqStack Sa,Sb;  84     InitStack(Sa);//初始化栈Sa;  85     for(i = 0; i < 6; i++){  86         Push(Sa,TextData[i]);  87     }  88     printf("**************栈基本操作*************/n");  89     //初始化数据  90     printf("初始化后的Sa：");  91     PrintfStack(Sa);  92       93     //得到栈顶元素  94     GetElem(Sa,e);  95     printf("Sa栈顶元素是：%d/n",e);  96   97     //初始化数据  98     printf("顶部出栈后Sa：");  99     Pop(Sa,e); 100     PrintfStack(Sa);     101 }

二：队列的学习：

队列和栈相反，是一种先进先出（FIFO）的线性表，只能在一端进行插入，一端进行删除

基础：在队列中，进行出入的一端称作队尾，允许删除的一端称作队首。和线性表差不多可以用顺序和链式表示。

双端队列： 双端队列是限定插入和删除的操作在表的两端进行的线性表，用的不是很多。

循环队列：百度上解释：” 将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量 “，其实就是把队列首尾相连，但是要有一定的要求，不是想怎么连就怎么连。

下面给出链表的结构体：

 1 //单链队列  2 typedef struct QNode{  3     QElemType data;  4     struct QNode *next;  5 }QNode, *QueuePtr;  6   7 typedef struct{  8     QueuePtr front;  9     QueuePtr rear; 10 }LinkQueue; 11  12 //循环队列 13 typedef struct{ 14     QElemType *base; 15     int front; 16     int rear; 17 }SqQueue;

下面这段代码练习了队列的基本操作：队列结构体定义（比栈的稍微复杂一点）、在队尾插入新元素、删除队头元素、销毁队列、打印队列、循环队列的定义等等，这部分牵涉到好多的指针操作，如果有些困难可以在纸上划出队列的结构，列出指针的操作前后变化，就容易多了（个人感觉如果线性表学好了，这些操作根本不在话下）。需要注意循环队列操作中取余操作：(Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;

废话不多说，下面直接给出具体实现的代码：

  1 #include <stdio.h>   2 #include <stdlib.h>   3 //头文件   4 #define ERROR -1   5 #define OK 2;   6 #define TRUE 1;   7 #define OVERFLOW -2;   8    9 //最大队列长度  10 #define MAXQSIZE 100  11   12 typedef int Status;  13 typedef int QElemType;  14   15 //单链队列  16 typedef struct QNode{  17     QElemType data;  18     struct QNode *next;  19 }QNode, *QueuePtr;  20   21 typedef struct{  22     QueuePtr front;  23     QueuePtr rear;  24 }LinkQueue;  25   26 //循环队列  27 typedef struct{  28     QElemType *base;  29     int front;  30     int rear;  31 }SqQueue;  32   33 //********************************队列的基本操作*****************************  34 //初始化队列  35 Status InitQueue(LinkQueue &Q){  36     Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));//动态分配空间  37     if(!Q.front){  38         exit(ERROR);//分配空间失败  39     }  40     Q.front->next = NULL;  41     return OK;  42 }  43   44 //在队尾插入新元素  45 Status EnQueue(LinkQueue &Q, int e){  46     QueuePtr p;  47     p = (QueuePtr)malloc(sizeof(QNode));  48     if(!p){  49         exit(ERROR);//分配失败  50     }  51     p->data = e;  52     p->next = NULL;  53     Q.rear->next = p;  54     Q.rear = p;  55     return OK;  56 }  57   58 void DestroyQueue(LinkQueue &Q){  59     if(Q.front != Q.rear){  60         while(Q.front){  61             Q.rear = Q.front->next;  62             free(Q.front);  63             Q.front = Q.rear;  64         }  65     }  66 }  67   68 //删除队头元素,并用e返回  69 Status DeQueue(LinkQueue &Q, int &e){  70     if(Q.front != Q.rear){//先判断队列是否为空  71         QueuePtr p;  72         e = Q.front->next->data;  73         if(Q.front->next == Q.rear){//队列只有一个元素  74             p = Q.rear;  75             Q.rear = Q.front;  76             Q.front->next = NULL;  77         }else{  78             p = Q.front->next;  79             Q.front->next = p->next;  80             p->next = NULL;  81         }      82         free(p);  83         return OK;  84     }  85 }  86   87 //打印队列元素  88 void PrintQueue(LinkQueue Q){  89     if(Q.front != Q.rear){  90         do{  91             Q.front = Q.front->next;  92             printf("%d ",Q.front->data);  93         }while(Q.front->next);  94     }  95     printf("/n");  96 }  97   98 //********************************循环队列的基本操作*****************************  99 //初始化队列 100 Status InitQueueXh(SqQueue &Q){ 101     Q.base = (int *)malloc(MAXQSIZE * sizeof(int));//动态分配空间 102     if(!Q.base){ 103         exit(ERROR);//分配空间失败 104     } 105     Q.front = Q.rear = 0; 106     return OK; 107 } 108  109 //在队尾插入新元素 110 Status EnQueueXh(SqQueue &Q, int e){ 111     if((Q.rear + 1) % MAXQSIZE == Q.front){ 112         exit(ERROR);//队循环列已满 113     } 114     Q.base[Q.rear] = e; 115     Q.rear = (Q.rear + 1) % MAXQSIZE; 116     return OK; 117 } 118  119 int DestroyQueueXh(SqQueue &Q){ 120     return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE; 121 } 122  123 //删除队头元素,并用e返回 124 Status DeQueueXh(SqQueue &Q, int &e){ 125     if(Q.front == Q.rear){//先判断队列是否为空 126         return false; 127     } 128     e = Q.base[Q.front]; 129     Q.front = (Q.front + 1) % MAXQSIZE; 130     return OK; 131 } 132  133 //打印队列元素 134 void PrintQueueXh(SqQueue Q){ 135     if(Q.front != Q.rear){ 136         do{ 137             printf("%d ",Q.base[Q.front]); 138             Q.front++; 139         }while(Q.front != Q.rear); 140     } 141     printf("/n"); 142 } 143  144 //主方法 145 int main(){ 146     int e, i; 147     int Data[6] = {3,1,7,8,9,1}; 148  149     printf("****************队列的基本操作**************/n"); 150     //初始化队列 151     LinkQueue Qa, Qb; 152     InitQueue(Qa); 153     //初始化Qa 154     for(i = 0; i < 6; i++){ 155         EnQueue(Qa,Data[i]); 156     }     157     //打印Qa 158     printf("Qa的各个元素："); 159     PrintQueue(Qa); 160  161     //删除队首元素 162     DeQueue(Qa,e); 163     printf("删除Qa的队首元素：%d/n",e); 164     printf("删除首元素后的Qa: "); 165     PrintQueue(Qa); 166     printf("销毁后的Qa: "); 167     DestroyQueue(Qa); 168     PrintQueue(Qa); 169  170     printf("**************循环队列的基本操作************/n"); 171     //初始化队列 172     SqQueue QaXh, QbXh; 173     InitQueueXh(QaXh); 174     //初始化Qa 175     for(i = 0; i < 6; i++){ 176         EnQueueXh(QaXh,Data[i]); 177     }     178     //打印Qa 179     printf("QaXh的各个元素："); 180     PrintQueueXh(QaXh); 181  182     //删除队首元素 183     DeQueueXh(QaXh,e); 184     printf("删除QaXh的队首元素：%d/n",e); 185     printf("删除首元素后的QaXh: "); 186     PrintQueueXh(QaXh); 187     printf("得到QaXh的元素个数：%d/n",DestroyQueueXh(QaXh)); 188 }