3. 栈和队列 (算法和数据结构笔记)

3. 栈和队列

● 顺序栈

//起始部分

#include "stdio.h"

#include "stdlib.h"

#include "io.h"

#include "math.h"

#include "time.h"

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define MAXSIZE 20 /* 存储空间初始分配量*/

typedef int Status;

typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

/* 顺序栈结构*/

包括①存放栈中元素的数组; ②栈顶指针(下面严蔚敏的代码中还声明了栈底指针)

typedef struct

{

SElemType data[MAXSIZE];

int top; /* 用于栈顶指针*/

}SqStack;

Status visit(SElemType c)

{

printf("%d ",c);

return OK;

}

/* 构造一个空栈S */

只需将栈顶指针设置为-1

Status InitStack(SqStack *S)

{

/* S.data=(SElemType *)malloc(MAXSIZE*sizeof(SElemType)); */

S->top=-1;

return OK;

}

/* 把S置为空栈*/

Status ClearStack(SqStack *S)

{

S->top=-1;

return OK;

}

/* 若栈S为空栈，则返回TRUE，否则返回FALSE */

Status StackEmpty(SqStack S)

{

if (S.top==-1)

return TRUE;

else

return FALSE;

}

/* 返回S的元素个数，即栈的长度*/

int StackLength(SqStack S)

{

return S.top+1;

}

/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */

Status GetTop(SqStack S,SElemType *e)

{

if (S.top==-1)

return ERROR;

else

*e=S.data[S.top];

return OK;

}

/* 入栈: 插入元素e为新的栈顶元素*/

①栈顶指针 S->top 自增，给需要进栈的元素腾出内存空间;

②赋值, 即给对应的数组元素赋值：S->data[S->top]=e.

Status Push(SqStack *S,SElemType e)

{

if(S->top == MAXSIZE -1) /* 栈满*/

{

return ERROR;

}

S->top++; /* 栈顶指针增加一*/

S->data[S->top]=e; /* 将新插入元素赋值给栈顶空间*/

return OK;

}

/* 出栈: 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */

① S->top 自减;

② 读取要出栈的元素;

Status Pop(SqStack *S,SElemType *e)

{

if(S->top==-1)

return ERROR;

*e=S->data[S->top]; /* 将要删除的栈顶元素赋值给e */

S->top--; /* 栈顶指针减一*/

return OK;

}

/* 从栈底到栈顶依次对栈中每个元素显示*/

Status StackTraverse(SqStack S)

{

int i;

i=0;

while(i<=S.top)

{

visit(S.data[i++]);

}

printf("n");

return OK;

}

//主函数

int main()

{

int j;

SqStack s;

int e;

if(InitStack(&s)==OK)

for(j=1;j<=10;j++)

Push(&s,j);

printf("栈中元素依次为：");

StackTraverse(s);

Pop(&s,&e);

printf("弹出的栈顶元素e=%dn",e);

printf("栈空否：%d(1:空0:否)n",StackEmpty(s));

GetTop(s,&e);

printf("栈顶元素e=%d 栈的长度为%dn",e,StackLength(s));

ClearStack(&s);

printf("清空栈后，栈空否：%d(1:空0:否)n",StackEmpty(s));

return 0;

}

/下面是严蔚敏版本的比较复杂的写法;

//栈的顺序存储

//说明部分

#include <stdio.h>

#include<stdlib.h>

#include<math.h>

#define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/

#define STACK_INCREMENT 2 /* 存储空间分配增量*/

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

typedef int Status;

typedef int SElemType;

typedef struct SqStack

{

SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */

SElemType *top; /* 栈顶指针*/

int stacksize; /* 当前已分配的存储空间，以元素为单位*/

}SqStack; /* 顺序栈*/

/* 顺序栈的基本操作(9个) */

/* 构造一个空栈S */

void InitStack(SqStack *S)

{

(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));

if(!(*S).base)

exit(OVERFLOW); /* 存储分配失败*/

(*S).top=(*S).base;

(*S).stacksize=STACK_INIT_SIZE;

}

/* 销毁栈S，S不再存在*/

void DestroyStack(SqStack *S)

{

free((*S).base);

(*S).base=NULL;

(*S).top=NULL;

(*S).stacksize=0;

}

/* 把S置为空栈*/

void ClearStack(SqStack *S)

{

(*S).top=(*S).base;

}

/* 若栈S为空栈，则返回TRUE，否则返回FALSE */

Status StackEmpty(SqStack S)

{

if(S.top==S.base)

return TRUE;

else

return FALSE;

}

/* 返回S的元素个数，即栈的长度*/

int StackLength(SqStack S)

{

return S.top-S.base;

}

/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */

Status GetTop(SqStack S,SElemType *e)

{

if(S.top>S.base)

{

*e=*(S.top-1);

return OK;

}

else

return ERROR;

}

//进栈

void Push(SqStack *S,SElemType e)

{ /* 插入元素e为新的栈顶元素*/

//下面的(*S).top都可以写成S->top

if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间*/

{

(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACK_INCREMENT)*sizeof(SElemType));

if(!(*S).base)

exit(OVERFLOW); /* 存储分配失败*/

(*S).top=(*S).base+(*S).stacksize;

(*S).stacksize+=STACK_INCREMENT;

}

*((*S).top)++=e;

}

//顺序表入栈的另一写法:

Status Push(SqStack *S,SElemType e)

{

if(S->top == MAXSIZE -1) /* 栈满*/

{

return ERROR;

}

S->top++; /* 栈顶指针增加一*/

S->data[S->top]=e; /* 将新插入元素赋值给栈顶空间*/

return OK;

}

//出栈

Status Pop(SqStack *S,SElemType *e)

{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */

if((*S).top==(*S).base)

return ERROR;

*e=*--(*S).top; //等价于*e=*--(s->top);

return OK;

}

/* 从栈底到栈顶依次对栈中每个元素调用函数visit() */

void StackTraverse(SqStack S,void(*visit)(SElemType))

{

while(S.top>S.base)

visit(*S.base++);

printf("n");

}

//打印数据域的值:

void print(SElemType c)

{

printf("%d ",c);

}

void main()

{

int j;

SqStack s;

SElemType e;

InitStack(&s);

for(j=1;j<=12;j++)

Push(&s,j);

printf("栈中元素依次为：");

StackTraverse(s,print);

Pop(&s,&e);

printf("弹出的栈顶元素e=%dn",e);

printf("栈空否：%d(1:空0:否)n",StackEmpty(s));

GetTop(s,&e);

printf("栈顶元素e=%d 栈的长度为%dn",e,StackLength(s));

ClearStack(&s);

printf("清空栈后，栈空否：%d(1:空0:否)n",StackEmpty(s));

DestroyStack(&s);

printf("销毁栈后，s.top=%u s.base=%u s.stacksize=%dn",s.top,s.base, s.stacksize);

}

//栈的共享: 两个顺序栈共享一个一维数据空间：

注: ①top0=-1 时0号桟为空;

②top1=MaxSize时1号栈为空；

③仅当两个栈顶指针相邻(top1-top0=1) 时，判断为栈满;

④当0号栈进栈时top0先加1 再赋值，1号栈进栈时top1先减1再赋值；出栈时则刚好相反。

/* 两栈共享空间的结构*/

typedef struct

{

SElemType data[MAXSIZE];

int top1; /* 栈栈顶指针*/

int top2; /* 栈栈顶指针*/

}SqDoubleStack;

栈链

//起始部分

#include "stdio.h"

#include "stdlib.h"

#include "io.h"

#include "math.h"

#include "time.h"

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define MAXSIZE 20 /* 存储空间初始分配量*/

typedef int Status;

typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

/* 链栈结构定义分为①链栈的结点描述; ②链栈的整体描述*/

//链栈的结点描述

typedef struct StackNode

{

SElemType data; //存放栈的数据

struct StackNode *next;

}StackNode,*LinkStackPtr;

//链栈的整体描述

typedef struct

{

LinkStackPtr top; //top指针

int count; //栈元素的计数器

}LinkStack;

//读取链栈的数据域

Status visit(SElemType c)

{

printf("%d ",c);

return OK;

}

//(这一部分不在本程序代码内, 但应该掌握)链栈的初始化

void InitStack(StackNode &p)

{

p=(StackNode*)malloc(sizeof(StackNode)); //制造一个头结点

p->next=NULL;

}

/* 构造一个空栈S */

Status InitStack(LinkStack *S)

{

S->top = (LinkStackPtr)malloc(sizeof(StackNode));

if(!S->top)

return ERROR;

S->top=NULL;

S->count=0;

return OK;

}

/* 把S置为空栈*/

参照把一个单链表置为空的方法:

Status ClearStack(LinkStack *S)

{

LinkStackPtr p,q;

p=S->top;

while(p)

{

q=p;

p=p->next;

free(q);

}

S->count=0;

return OK;

}

/* 若栈S为空栈，则返回TRUE，否则返回FALSE */

Status StackEmpty(LinkStack S)

{

if (S.count==0)

return TRUE;

else

return FALSE;

}

/* 返回S的元素个数，即栈的长度*/

int StackLength(LinkStack S)

{

return S.count;

}

/* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */

Status GetTop(LinkStack S,SElemType *e)

{

if (S.top==NULL)

return ERROR;

else

*e=S.top->data;

return OK;

}

/* 入栈: 插入元素e为新的栈顶元素*/

生成LinkStackPtr型的结点s;
e赋值给s的数据域;
把s的指针域指向链栈S当前的栈顶元素;
将栈顶指针指向新结点s;

Status Push(LinkStack *S,SElemType e)

{

LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));

s->data=e;

s->next=S->top; /* 把当前的栈顶元素赋值给新结点的直接后继，见图中①*/

S->top=s; /* 将新的结点s赋值给栈顶指针，见图中②*/

S->count++;

return OK;

}

/* 出栈: 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */

Status Pop(LinkStack *S,SElemType *e)

{

LinkStackPtr p;

if(StackEmpty(*S))

return ERROR;

*e=S->top->data;

p=S->top; /* 将栈顶结点赋值给p，见图中①*/

S->top=S->top->next; /* 使得栈顶指针下移一位，指向后一结点，见图中②*/

free(p); /* 释放结点p, 见图中③ */

S->count--;

return OK;

}

//遍历链栈

Status StackTraverse(LinkStack S)

{

LinkStackPtr p;

p=S.top;

while(p)

{

visit(p->data);

p=p->next;

}

printf("n");

return OK;

}

//主函数

int main()

{

int j;

LinkStack s;

int e;

if(InitStack(&s)==OK)

for(j=1;j<=10;j++)

Push(&s,j);

printf("栈中元素依次为：");

StackTraverse(s);

Pop(&s,&e);

printf("弹出的栈顶元素e=%dn",e);

printf("栈空否：%d(1:空0:否)n",StackEmpty(s));

GetTop(s,&e);

printf("栈顶元素e=%d 栈的长度为%dn",e,StackLength(s));

ClearStack(&s);

printf("清空栈后，栈空否：%d(1:空0:否)n",StackEmpty(s));

return 0;

}

顺序队列(循环队列)

//起始部分

#include "stdio.h"

#include "stdlib.h"

#include "io.h"

#include "math.h"

#include "time.h"

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define MAXSIZE 20 /* 存储空间初始分配量*/

typedef int Status;

typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

/* 循环队列的顺序存储结构(普通队列的结点定义也是如此)*/

顺序队列的结点包括:①队列的数组(队列的基址); ②头指针和为指针(int型)

typedef struct

{

QElemType data[MAXSIZE];

int front; /* 头指针*/

int rear; /* 尾指针，若队列不空，指向队列尾元素的下一个位置*/

}SqQueue;

Status visit(QElemType c)

{

printf("%d ",c);

return OK;

}

/* 初始化一个空队列Q */

Status InitQueue(SqQueue *Q)

{

Q->front=0;

Q->rear=0;

return OK;

}

/* 将Q清为空队列*/

Status ClearQueue(SqQueue *Q)

{

Q->front=Q->rear=0; //注意写法: 我们可连续用两个等号

return OK;

}

/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */

Status QueueEmpty(SqQueue Q)

{

if(Q.front==Q.rear) /* 队列空的标志*/

return TRUE;

else

return FALSE;

}

// 销毁队列Q，Q不再存在

void DestroyQueue(SqQueue &Q)

{

if(Q.base)

free(Q.base);

Q.base=NULL;

Q.front=Q.rear=0;

}

/* 返回Q的元素个数，也就是队列的当前长度*/

int QueueLength(SqQueue Q)

{

return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;

}

/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */

Status GetHead(SqQueue Q,QElemType *e)

{

if(Q.front==Q.rear) /* 队列空*/

return ERROR;

*e=Q.data[Q.front];

return OK;

}

/* 入队: 若队列未满，则插入元素e为Q新的队尾元素*/

入队步骤:

①队满返回ERROR;

②将元素e赋值给队尾;

③rear指针向后移一个位置(若已到最后则转到数组头部)

Status EnQueue(SqQueue *Q,QElemType e)

{

if ((Q->rear+1)%MAXSIZE == Q->front) /* 队列满的判断*/

return ERROR;

Q->data[Q->rear]=e; /* 将元素e赋值给队尾*/

Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置，*/

/* 若到最后则转到数组头部*/

return OK;

}

/* 出队: 若队列不空，则删除Q中队头元素，用e返回其值*/

入队步骤:

①队空返回ERROR;

②将队头元素赋值给e;

③front指针向后移一位置(若已到最后则转到数组头部)

Status DeQueue(SqQueue *Q,QElemType *e)

{

if (Q->front == Q->rear) /* 队列空的判断*/

return ERROR;

*e=Q->data[Q->front]; /* 将队头元素赋值给e */

Q->front=(Q->front+1)%MAXSIZE; /* front指针向后移一位置，*/

/* 若到最后则转到数组头部*/

return OK;

}

/* 遍历队列: 从队头到队尾依次对队列Q中每个元素输出*/

①设置int型变量i, i=Q.front;

②当i+Q.front)!=Q.rear, 进入循环--读取Q.data[i]的值, 然后将(i+1)%MAXSIZE赋值给i--如此继续循环

Status QueueTraverse(SqQueue Q)

{

int i;

i=Q.front;

while((i+Q.front)!=Q.rear)

{

visit(Q.data[i]);

i=(i+1)%MAXSIZE;

}

printf("n");

return OK;

}

//主函数

int main()

{

Status j;

int i=0,l;

QElemType d;

SqQueue Q;

InitQueue(&Q);

printf("初始化队列后，队列空否？%u(1:空0:否)n",QueueEmpty(Q));

printf("请输入整型队列元素(不超过%d个),-1为提前结束符: ",MAXSIZE-1);

{

/* scanf("%d",&d); */

d=i+100;

if(d==-1)

break;

i++;

EnQueue(&Q,d);

}while(i<MAXSIZE-1);

printf("队列长度为: %dn",QueueLength(Q));

printf("现在队列空否？%u(1:空0:否)n",QueueEmpty(Q));

printf("连续%d次由队头删除元素,队尾插入元素:n",MAXSIZE);

for(l=1;l<=MAXSIZE;l++)

{

DeQueue(&Q,&d);

printf("删除的元素是%d,插入的元素:%d n",d,l+1000);

/* scanf("%d",&d); */

d=l+1000;

EnQueue(&Q,d);

}

l=QueueLength(Q);

printf("现在队列中的元素为: n");

QueueTraverse(Q);

printf("共向队尾插入了%d个元素n",i+MAXSIZE);

if(l-2>0)

printf("现在由队头删除%d个元素:n",l-2);

while(QueueLength(Q)>2)

{

DeQueue(&Q,&d);

printf("删除的元素值为%dn",d);

}

j=GetHead(Q,&d);

if(j)

printf("现在队头元素为: %dn",d);

ClearQueue(&Q);

printf("清空队列后, 队列空否？%u(1:空0:否)n",QueueEmpty(Q));

return 0;

}

● 链队列

//起始部分

#include "stdio.h"

#include "stdlib.h"

#include "io.h"

#include "math.h"

#include "time.h"

#define OK 1

#define ERROR 0

#define TRUE 1

#define FALSE 0

#define MAXSIZE 20 /* 存储空间初始分配量*/

typedef int Status;

typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */

//单链表的结点类型和单链表类型

单链表的结点QNode类型包括①数据;②指向下一结点的QNode型指针

typedef struct QNode /* 结点结构*/

{

QElemType data;

struct QNode *next;

}QNode,*QueuePtr;

typedef struct /* 队列的链表结构*/

{

QueuePtr front,rear; /* 队头、队尾指针*/

}LinkQueue;

Status visit(QElemType c)

{

printf("%d ",c);

return OK;

}

/* 构造一个空链队列Q */

空链队列:

或者

分配一个QueuePtr型的sizeof(QNode)大小的空间, 赋值给Q->rear, 然后赋值给Q->front;
如果分配不成功, exit(OVERFLOW);
将Q->front头结点的指针域赋值为NULL.

Status InitQueue(LinkQueue *Q)

{

Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q->front) //如果分配不成功

exit(OVERFLOW);

Q->front->next=NULL;

return OK;

}

/* 销毁链队列Q */

非空链队列:

第一次循环完成后:

依次删除队头元素直到队列为空。

Status DestroyQueue(LinkQueue *Q)

{

while(Q->front) //①q->front是队列的队首头节点，不为NULL时执行循环

{

Q->rear=Q->front->next; //②将Q->rear指向离队首, 即离头结点最近的节点(下一个结点)

free(Q->front); //③释放队首的头节点所在内存单元

Q->front=Q->rear;//④执行完这一句后, Q.front和Q.rear都指向刚才离原来队首最近的节点(现在已经变成了新的头结点)。

//倘若执行Destoryqueue()前节点的个数>=2，则第一次执行次循环后仍满足循环条件继续循环，

//最终整个队列的内存全部被释放，队列被销毁。

}

return OK;

}

/* 将Q清为空队列*/

Status ClearQueue(LinkQueue *Q)

{

QueuePtr p,q;

Q->rear=Q->front;

p=Q->front->next;

Q->front->next=NULL;

while(p)

{

q=p;

p=p->next;

free(q);

}

return OK;

}

/* 若Q为空队列,则返回TRUE,否则返回FALSE */

Status QueueEmpty(LinkQueue Q)

{

if(Q.front==Q.rear)

return TRUE;

else

return FALSE;

}

/* 求队列的长度*/

int QueueLength(LinkQueue Q)

{

int i=0;

QueuePtr p;

p=Q.front;

while(Q.rear!=p)

{

i++;

p=p->next;

}

return i;

}

/* 若队列不空,则用e返回Q的队头元素,并返回OK,否则返回ERROR */

Status GetHead(LinkQueue Q,QElemType *e)

{

QueuePtr p;

if(Q.front==Q.rear)

return ERROR;

p=Q.front->next;

*e=p->data;

return OK;

}

/* 入队: 插入元素e为Q的新的队尾元素*/

声明QueuePtr型的结点s, 赋值为(QueuePtr)malloc(sizeof(Node));
如果分配失败, 返回exit(OVERFLOW);
将e赋值给s结点的数据域, 将NULL赋值给s结点的指针域;
将Q->rear指针指向的结点的指针域指向s结点;
将Q->rear指针指向结点s.

Status EnQueue(LinkQueue *Q,QElemType e)

{

QueuePtr s=(QueuePtr)malloc(sizeof(QNode));

if(!s) /* 存储分配失败*/

exit(OVERFLOW);

s->data=e;

s->next=NULL;

Q->rear->next=s; /* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中①*/

Q->rear=s; /* 把当前的s设置为队尾结点，rear指向s，见图中②*/

return OK;

}

/* 出队: 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */

出队操作就是头结点的后继结点出队，将头结点的后继改为它后面的结点:

若链表除头结点外只剩一个元素时，则需将rear指向头结点:

Status DeQueue(LinkQueue *Q,QElemType *e)

{

if(Q->front==Q->rear)

return ERROR; //①如果队列空, 返回ERROR;

QueuePtr p;

p=Q->front->next; /* ②将欲删除的头结点后的第一个节点暂存给p，见图中①*/

*e=p->data; /* ③将欲删除的头结点后的第一个节点的值赋值给e */

Q->front->next=p->next;/* ④将Q->front头结点的指针域指向p的下一结点, 见图中②*/

if(Q->rear==p) /* ⑤如果链表除头结点外只剩一个元素时，需将rear指向头结点，见图中③*/

Q->rear=Q->front;

free(p);

return OK;

}

/* 从队头到队尾依次对队列Q中每个元素输出*/

Status QueueTraverse(LinkQueue Q)

{

QueuePtr p;

p=Q.front->next;

while(p)

{

visit(p->data);

p=p->next;

}

printf("n");

return OK;

}

//主函数

int main()

{

int i;

QElemType d;

LinkQueue q;

i=InitQueue(&q);

if(i)

printf("成功地构造了一个空队列!n");

printf("是否空队列？%d(1:空0:否) ",QueueEmpty(q));

printf("队列的长度为%dn",QueueLength(q));

EnQueue(&q,-5);

EnQueue(&q,5);

EnQueue(&q,10);

printf("插入个元素(-5,5,10)后,队列的长度为%dn",QueueLength(q));

printf("是否空队列？%d(1:空0:否) ",QueueEmpty(q));

printf("队列的元素依次为：");

QueueTraverse(q);

i=GetHead(q,&d);

if(i==OK)

printf("队头元素是：%dn",d);

DeQueue(&q,&d);

printf("删除了队头元素%dn",d);

i=GetHead(q,&d);

if(i==OK)

printf("新的队头元素是：%dn",d);

ClearQueue(&q);

printf("清空队列后,q.front=%u q.rear=%u q.front->next=%un",q.front,q.rear,q.front->next);

DestroyQueue(&q);

printf("销毁队列后,q.front=%u q.rear=%un",q.front, q.rear);

return 0;

}