大家好，我是讯享网，很高兴认识大家。

第三章、栈和队列

3.1栈

3.1.1栈的定义

栈(stack)是一种只能在一端进行插入或删除操作的线性表。表中允许进行插人、删除操作的一端称为栈顶(top),表的另一端称为栈底(bottom)。栈顶的当前位置是动态的，栈顶的当前位置由一个被称为栈顶指针的位置指示器来指示。当栈中没有数据元素时称为空栈。栈的插人操作通常称为进栈或入栈(push),栈的删除操作通常称为出栈或退栈(pop)。

讯享网

栈的主要特点是“后进先出"(Last In First Out,LIFO),即后进栈的元素先出栈。每次进栈的数据元素都放在原来栈顶元素之前成为新的栈顶元素,每次出栈的数据元素都是当前栈顶元素。栈也称为后进先出表。

3.1.2栈的顺序存储结构及其实现

采用顺序存储结构的栈就是顺序栈。一般的顺序存储结构采用的是数组。

#include<stdio.h> #include<stdlib.h> #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int top; //栈指针 } SqStack; int main() { system("pause"); return 0; }

讯享网

4个十分重要的要素：

• 栈空的条件: s-> top==-1。
• 栈满的条件: s-> top= = MaxSize- l(data数组的最大下标)。
• 元素e的进栈操作:先将栈顶指针top增1,然后将元素e放在栈顶指针处。
• 出栈操作:先将栈顶指针top处的元素取出放在e中，然后将栈顶指针减1。

 栈的初始化：

讯享网void InitStack(SqStack *&s) //初始化顺序栈 { s=(SqStack *)malloc(sizeof(SqStack)); s->top=-1; } 

销毁栈：

void DestroyStack(SqStack *&s) //销毁顺序栈 { free(s); }

 判断栈是否为空：

讯享网bool StackEmpty(SqStack *s) //判断栈空否 { return(s->top==-1); }

进栈：

bool Push(SqStack *&s,ElemType e) //进栈 { if (s->top==MaxSize-1) //栈满的情况，即栈上溢出 return false; s->top++; s->data[s->top]=e; return true; }

出栈：

讯享网bool Pop(SqStack *&s,ElemType &e) //出栈 { if (s->top==-1) //栈为空的情况，即栈下溢出 return false; e=s->data[s->top]; s->top--; return true; } 

取栈顶元素：

bool GetTop(SqStack *s,ElemType &e) //取栈顶元素 { if (s->top==-1) //栈为空的情况，即栈下溢出 return false; e=s->data[s->top]; return true; }

讯享网int main() { SqStack *S1; ElemType e,e1,e2; InitStack(S1); if(StackEmpty(S1)) { printf("栈为空\n"); } Push(S1,1); Push(S1,2); GetTop(S1,e); printf("栈顶元素为%d\n",e); Pop(S1,e1); printf("出栈元素为%d\n",e1); GetTop(S1,e2); printf("栈顶元素为%d\n",e2); DestroyStack(S1); system("pause"); return 0; }

 顺序栈采用一个数组存放栈中的元素。如果需要用到两个相同类型的栈，这时若为 它们各自开辟一个数组空间，极有可能出现这样的情况：第一个栈已满，再进栈就溢出了，而另一个栈还有很多空闲存储空间。解决这个问题的方法是将两个栈合起来，用一个数组来实现这两个栈，这称为共享栈(share stack)。

typedef struct { ElemType data[MaxSize]; int top1,top2; //栈指针 } DStack; 

 共享栈的4个要素如下：

• 栈空条件：栈1空为top1==-1，栈2空为top2==MaxSize。
• 栈满条件：top1 == top2-1。
• 元素进栈操作：进栈1操作为top1++; data[top1] =x；进栈2操作为top2--，data[top2] =x。
• 出栈x操什：出栈1操作为 x= data[ top1]；top1--；出栈2操作为 x= data[top2]；top2--。

3.13栈的链式存储结构及其实现 

这里采用的是带头节点的链表来实现的。

 重要的4个要素：

• 栈空的条件：s->next == NULL。
• 栈满的条件：由于只有内存溢出时才出现栈满，通常不考虑这样的情况．所以在链栈中可以看成不存在栈满。
• 元素e的进栈操作：新建一个节点存放e(由p指向它)，将节点p插到头节点之后(栈顶)。
• 出栈操作：取出首节点data值并将其删除。

讯享网#include<stdio.h> #include<stdlib.h> #define MaxSize 50 typedef int ElemType; typedef struct linknode { ElemType data; //数据域 struct linknode *next; //指针域 } LinkStNode; int main() { system("pause"); return 0; }

 初始化栈：

void InitStack(LinkStNode *&s) //初始化链栈 { s=(LinkStNode *)malloc(sizeof(LinkStNode)); s->next=NULL; }

销毁栈：

讯享网void DestroyStack(LinkStNode *&s) //销毁链栈 { LinkStNode *p=s->next; while (p!=NULL) { free(s); s=p; p=p->next; } free(s); //s指向尾节点,释放其空间 }

判断栈是否为空：

bool StackEmpty(LinkStNode *s) //判断栈空否 { return(s->next==NULL); }

进栈：

讯享网void Push(LinkStNode *&s,ElemType e) //进栈 { LinkStNode *p; p=(LinkStNode *)malloc(sizeof(LinkStNode)); p->data=e; //新建元素e对应的节点p p->next=s->next; //插入p节点作为开始节点 s->next=p; }

出栈：

bool Pop(LinkStNode *&s,ElemType &e) //出栈 { LinkStNode *p; if (s->next==NULL) //栈空的情况 return false; p=s->next; //p指向开始节点 e=p->data; s->next=p->next; //删除p节点 free(p); //释放p节点 return true; }

获取栈顶元素：

讯享网bool GetTop(LinkStNode *s,ElemType &e) //取栈顶元素 { if (s->next==NULL) //栈空的情况 return false; e=s->next->data; return true; }

int main() { LinkStNode *S1; ElemType e,e1,e2; InitStack(S1); if(StackEmpty(S1)) { printf("栈为空\n"); } Push(S1,1); Push(S1,2); GetTop(S1,e); printf("栈顶元素为%d\n",e); Pop(S1,e1); printf("出栈元素为%d\n",e1); GetTop(S1,e2); printf("栈顶元素为%d\n",e2); DestroyStack(S1); system("pause"); return 0; }

3.2队列 

3.2.1队列的定义

队列(queue)简称队．它也是一种操作受限的线性表．其限制为仅允许在表的一端进行插入操作，而在表的另一端进行删除操作，把进行插入的一端称为队尾(rear)，把进行删除的一端称为队头或队首(front)。 向队列中插入新元素称为进队或入队(enqueue)，新元素进队后就成为新的队尾元素； 从队列中删除元素称为出队或离队(dequeue)，元素出队后，其直接后继元素就成为队首元素。

由于队列的插入和删除操作分别是在各自的一端进行的，每个元素必然按照进入的次序出队，所以又把队列称为先进先出表(First In First Out,FIFO)。

3.2.2队列的顺序存储结构以及实现

队列里面相关元素用数组来存放。

讯享网#include<stdio.h> #include<stdlib.h> #define MaxSize 50 typedef int ElemType; typedef struct { ElemType data[MaxSize]; int front,rear; //队首和队尾指针 } SqQueue; int main() { system("pause"); return 0; }

顺序队 ：

 非常重要的4个因素：

• 队空的条件：q->front == q->rear。
• 队满的条件：q->rear == MaxSize - 1。
• 元素e的进队操作：先将rear+1，然后将元素e放到data数组的rear位置。
• 出队操作：先将front+1，然后取出data数组中front位置的元素。

初始化队列：

void InitQueue(SqQueue *&q) { q=(SqQueue *)malloc (sizeof(SqQueue)); q->front=q->rear=-1; }

销毁队列：

讯享网void DestroyQueue(SqQueue *&q) //销毁队列q { free(q); }

判断队列是否为空：

bool QueueEmpty(SqQueue *q) //判断队q是否空 { return(q->front==q->rear); }

进队列：

讯享网bool enQueue(SqQueue *&q,ElemType e) //进队 { if (q->rear==MaxSize-1) //队满上溢出 return false; //返回假 q->rear++; //队尾增1 q->data[q->rear]=e; //rear位置插入元素e return true; //返回真 }

出队列：

bool deQueue(SqQueue *&q,ElemType &e) //出队 { if (q->front==q->rear) //队空下溢出 return false; q->front++; e=q->data[q->front]; return true; } 

讯享网int main() { SqQueue *S; ElemType e1,e2; InitQueue(S); if(QueueEmpty(S)) { printf("队列为空\n"); } else { printf("队列不为空\n"); } enQueue(S,1); enQueue(S,2); deQueue(S,e1); deQueue(S,e2); printf("e1 = %d e2 = %d\n",e1,e2); system("pause"); return 0; }

 

环形队：

循环队与顺序队的结构体表示是一样的。为了区别队满和队空，循环队列最多只能存放MaxSize-1个元素。也就是空的一个位置仅仅作为标志位。并约定队空：front==rear==0。 

 非常重要的4个因素：

• 队空条件：q->front == q->rear。
• 队满条件：(q->rear + 1) % MaxSize == q->front。
• 元素x进队(需要移动队尾指针)：q->rear = (q->rear + 1) % MaxSize；q->data[q->rear] = x；
• 出队x(需移动队首指针)：q->front= (q->front + 1) % MaxSize；q->data[q->front] = x；

初始化队列：

void InitQueue(SqQueue *&q) //初始化队列q { q=(SqQueue *)malloc (sizeof(SqQueue)); q->front=q->rear=0; }

销毁队列：

讯享网void DestroyQueue(SqQueue *&q) //销毁队列q { free(q); }

判断队列是否为空：

bool QueueEmpty(SqQueue *q) //判断队q是否空 { return(q->front==q->rear); }

进队：

讯享网bool enQueue(SqQueue *&q,ElemType e) //进队 { if ((q->rear+1)%MaxSize==q->front) //队满上溢出 return false; q->rear=(q->rear+1)%MaxSize; q->data[q->rear]=e; return true; }

出队：

bool deQueue(SqQueue *&q,ElemType &e) //出队 { if (q->front==q->rear) //队空下溢出 return false; q->front=(q->front+1)%MaxSize; e=q->data[q->front]; return true; }

讯享网int main() { ElemType e1,e2; SqQueue *S; InitQueue(S); if(QueueEmpty) { printf("队列为空\n"); } else { printf("队列不为空\n"); } enQueue(S,1); enQueue(S,2); deQueue(S,e1); deQueue(S,e2); printf("e1 = %d e2 = %d\n",e1,e2); system("pause"); return 0; }

 

 3.2.3队列的链式存储结构以及实现

链式存储结构采用链表来实现，不过采用的是队列先进先出的特点来管理节点。

#include<stdio.h> #include<stdlib.h> #define MaxSize 50 typedef int ElemType; typedef struct DataNode { ElemType data; struct DataNode *next; } DataNode; //链队数据节点类型定义 typedef struct { DataNode *front; DataNode *rear; } LinkQuNode; //链队节点类型定义 int main() { system("pause"); return 0; }

重要的4个要素：

• 队空的条件：q->rear == NULL(或者q->front== NULL)。
• 队满的条件：不考虑。
• 元素e进队操作：新建一个节点存放e(由p指向它)，将p节点插入作为尾节点。
• 出队操作：取出队首节点的data值并将其删除。

队列的初始化：

讯享网void InitQueue(LinkQuNode *&q) //初始化队列q { q=(LinkQuNode *)malloc(sizeof(LinkQuNode)); q->front=q->rear=NULL; }

销毁队列：

void DestroyQueue(LinkQuNode *&q) //销毁队列q { DataNode *p=q->front,*r;//p指向队头数据节点 if (p!=NULL) //释放数据节点占用空间 { r=p->next; while (r!=NULL) { free(p); p=r;r=p->next; } } free(p); free(q); //释放链队节点占用空间 }

判断队列是否为空：

讯享网bool QueueEmpty(LinkQuNode *q) //判断队q是否空 { return(q->rear==NULL); }

进队列：

void enQueue(LinkQuNode *&q,ElemType e) //进队 { DataNode *p; p=(DataNode *)malloc(sizeof(DataNode)); p->data=e; p->next=NULL; if (q->rear==NULL) //若链队为空,则新节点是队首节点又是队尾节点 q->front=q->rear=p; else { q->rear->next=p; //将p节点链到队尾,并将rear指向它 q->rear=p; } }

出队列：

讯享网bool deQueue(LinkQuNode *&q,ElemType &e) //出队 { DataNode *t; if (q->rear==NULL) //队列为空 return false; t=q->front; //t指向第一个数据节点 if (q->front==q->rear) //队列中只有一个节点时 q->front=q->rear=NULL; else //队列中有多个节点时 q->front=q->front->next; e=t->data; free(t); return true; }

int main() { ElemType e1,e2; LinkQuNode *S; InitQueue(S); if(QueueEmpty) { printf("队列为空\n"); } else { printf("队列不为空\n"); } enQueue(S,1); enQueue(S,2); deQueue(S,e1); deQueue(S,e2); printf("e1 = %d e2 = %d\n",e1,e2); system("pause"); return 0; }

3.2.4 双端队列

有三种，主要考选择题：