前言： 本系列是笔者暑假自学数据结构的笔记整理而来，共126页，3w+字。现在正式开学上课，补充老师所讲内容，并且仔细勘误，根据老师的教学进度分章节发布在上。 教材使用的是王红梅等所著的数据结构——从概念到C++实现（第三版）。 暑假自学时期主要参考的网课： 青岛大学-王卓 武汉大学-李春葆

目录

栈定义与概念基本运算 队列定义与概念基本运算环形队列与循环队列链队 栈与队列的比较

栈

定义与概念

1.栈和队列是两种常用的、重要的数据结构 2.栈和队列是限定插入和删除只能在表的“端点”进行的线性表 3.栈是一种只能在一段进行插入和删除的线性表 4.允许进行插入、删除操作的一段成为栈顶，表的另一段称为栈底 5.当栈中没有数据元素时，称为空栈 6.栈的插入操作通常称为进栈和入栈 7.栈的删除操作通常称为退栈和出栈 8.栈的主要特点是“先进后出”，即后进栈的元素先出栈，栈也称为后进先出表 Eg：

基本运算

/* 栈的基本运算如下： InitStack(&s);初始化栈，构造一个空栈s DestoryStack(&s);销毁栈，释放栈s占用的空间 StackEmpty(s);判断栈是否为空，若栈s为空，则返回真，否则返回假 Push(&S, e);进栈，将元素e插入到栈s中作为栈顶元素 Pop(&s, &e);出栈，从栈s中退出栈顶元素，并将其赋值给e GetTop(s, &e);取栈顶元素，返回当前的栈顶元素，并将其值赋值给e 栈中元素逻辑关系与线性表相同，栈可以采用与线性表相同的存储结构 因此栈分为两类，顺序栈与链栈 */ #define ElemType int #define MAXSIZE 1000 typedef struct { ElemType data[MAXSIZE]; int top//约定：top总是指向栈顶元素，初始值即空栈时为-1 //当top = MAXSIZE - 1时不能再进栈，因为栈满 //进栈时top++，出栈时top-- }SqStack; /* 顺序栈四要素 栈空条件：top = -1 栈满条件：top = MAXSIZE - 1 e进栈操作：top++；e放在top处 e退栈操作：从top处取出e；top-- */ //初始化栈 void InitStack(SqStack *&s) { s = new SqStack; s->top = -1;//注意：s叫做栈指针，而top叫做栈顶指针 } //销毁栈 void DestroyStack(SqStack *&s) { delete 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; } //判断一段字符串是否是对称的 bool symmetry(ElemType str[]) { int i; ElemType e; SqStack *st; InitStack(st);//初始化栈 for (int i = 0; str[i] != '\0'; i++) { Push(st, str[i]); } for (int i = 0; str[i] != '\0'; i++) { Pop(st, e); if (str[i] != e)//若e与当前串元素不同则不是对称串 { DestroyStack(st); return false; } } }

/* 链栈四要素 栈空条件：s->next = NULL; 栈满条件：不考虑 进栈操作：将包含e的节点插入到头结点之后 退栈操作：取出头结点之后节点的元素并删除之 */ typedef struct linknode { ElemType data; struct linknode *next; }LiStack; //初始化栈InitStack(&s) void InitStack(LiStack *&s) { s = new LiStack; s->next = nullptr; } //销毁栈DestroyStack(&s) void DestroyStack(LiStack *&s) { LiStack *p = s, *q = s->next; while (q != nullptr) { delete p; p = q; q = p->next; } delete p;//此时p指向尾结点，释放其空间 } //判断栈是否为空StackEmpty(s) bool StackEmpty(LiStack *s) { return s->next == nullptr; } //进栈Push(&s, e) void Push(LiStack *&s, ElemType e) { LiStack *p; p = new LiStack; p->data = e;//新建元素e对应的节点*p p->next = s->next;//插入*p节点作为开始节点 s->next = p; } //出栈Pop(&s, &e) bool Pop(LiStack *&s, ElemType &e) { LiStack *p; if (s->next == nullptr) { return false; } p = s->next;//p指向开始节点 e = p->data; s->next = p->next;//删除*p节点 delete p; return true; } //取栈顶元素GetTop(s, e) bool GetTop(LiStack *s, ElemType &e) { if (s->next == nullptr) { return false; } e = s->next->data; return true; } //编写一个算法判断输入的表达式中括号是否配对 bool Match(char exp[], int n) { int i = 0; char e; bool match = true; LiStack *st; InitStack(st); while (i < n && match)//扫描exp中所有字符 { if (exp[i] == '(')//遇到任何(都进栈 { Push(st, exp[i]); } } else if (exp[i] == ')') { if (GetTop(st, e) == true)//栈顶元素不为(时表示不匹配 { if (e != '(') { match = false; } else { Pop(st, e);//将栈顶元素出栈 } } else { match = false;//无法取栈顶元素时表示不匹配 } } i++;//继续处理其他字符 if (!StackEmpty(st))//栈不空时表示不匹配 { match = false; } DestroyStack(st); return match; }//只有在表达式扫描完毕且栈空时返回true

队列

定义与概念

1.队列简称队，也是一种运算受限的线性表 2.队列只能选取一个端点进行插入操作，另一个端点进行删除操作 3.把进行插入的一端称作队尾rear 4.把进行删除的一端称作队首或队头front 5.向队列中插入新元素称为进队或入队，新元素进队后就称为新的队尾元素 6.队列的主要特点是先进先出，所以又把队列称为先进先出表

基本运算

/* 队列的基本运算如下： InitQueue(&q):初始化队列，构建一个空队列q DestroyQueue(&q):销毁队列，释放队列q占用的存储空间 QueueEmpty(q):判断队列是否为空，若队列q为空，则返回真，否则返回假 enQueue(&q, e):进队列，将元素e进队作为队尾元素 deQueue(&q, &e):出队列，从队列q中出队一个元素，并将其值赋值给e 既然队列中元素逻辑关系与线性表的相同，队列可以采用与线性表相同的存储结构 队列分为顺序队和链队 */ #define ElemType int #define MAXSIZE 100 typedef struct { ElemType data[MAXSIZE]; int front, rear;//队首，队尾指针 //因为队列两端都在变化，所以需要两个指针来标示队列的状态 //约定rear总是指向队尾元素 //元素进队，rear++ //约定front指向当前队中队首元素的前一位置 //元素出队，front++ //当rear == MAXSIZE - 1时不能再进队 }SqQueue; /* 顺序队的四要素，初始front = rear = -1 队空条件：front = rear 队满条件：rear = MAXSIZE - 1 元素e进队：rear++;data[rear] = e 元素e出队：front++;e = data[front] */ //初始化队列 void InitQueue(SqQueue *&q) { q = new SqQueue; q->front = -1; q->rear = -1; } //销毁队列 void DestroyQueue(SqQueue *&q) { delete q; } //判断队列是否为空 bool QueueEmpty(SqQueue *q) { return q->front == q->rear; } //进队列 bool enQueue(SqQueue *&q, ElemType e) { if (q->rear == MAXSIZE - 1) { return false; } q->rear++; q->data[q->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; }

环形队列与循环队列

解决办法靠环形队列或循环队列

/* 环形队列的四要素 队空条件：front = rear 队满条件：(rear + 1)%MAXSIZE = front 进队e操作：rear = (rear + 1)%MAXSIZE;将e放在rear处 出队e操作：front = (front + 1)%MAXSIZE;取出front处元素e 在环形队列中，实现队列的基本运算算法与非环形队列类似 */

根据以上推论和题意设计有

typedef struct { ElemType data[MAXSIZE]; int front;//队头指针 int count;//队列中元素个数 }QuType;

该环形队列的四要素：

/* 该环形队列四要素： 队空条件：count = 0 队满条件：count = MAXSIZE 进队e操作：rear = (rear + 1)%MAXSIZE;将e放在rear处 出队e操作：front = (front + 1)%MAXSIZE;取出front处元素e 注意：这样的环形队列存放最多MAXSIZE个元素 */

对应算法如下：

//初始化队 void InitQueue(QuType *&qu) { qu = new QuType; qu->front = 0; qu->count = 0; } //进队 bool EnQueue(QuType *&qu, ElemType x) { int rear;//临时队尾指针 if (qu->count == MAXSIZE)//队满上溢出 { return false; } else { rear = (qu->front + qu->count)%MAXSIZE;//求队尾位置 rear = (rear + 1)%MAXSIZE;//队尾循环增一 qu->data[rear] = x; qu->count++;//元素个数增一 return true; } } //出队 bool DeQueue(QuType *&qu, ElemType &x) { if (qu->count == 0) { return false; } else { qu->front = (qu->front + 1)%MAXSIZE; x = qu->data[qu->front]; qu->count--; return true; } } //判断空队列 bool QueueEmpty(QuType *qu) { return qu->count == 0; }

显然环形队列比非环形队列更有效利用内存空间，即环形队列会重复使用已经出队元素的空间，不会出现假溢出。但如果算法中需要使用所有进队的元素来进一步求解，此时可以使用非环形队列。

链队

//单链表中数据节点类型Qnode定义 typedef struct Qnode { ElemType data;//数据元素 struct Qnode *next; }Qnode; //链队中头结点类型LiQueue定义 typedef struct { Qnode *front;//指向单链表队头结点 Qnode *rear;//指向单链表队尾结点 }LiQueue; /* 链队的四要素 队空条件：front = rear = null 队满条件：不考虑 e进队操作：将包含e的结点插入到单链表表尾 出队操作：删除单链表首数据节点 */ //初始化队列 void InitQueue(LiQueue *&q) { q = new LiQueue; q->front = q->rear = nullptr; } //销毁一个队列 void DestroyQueue(LiQueue *&q) { Qnode *p = q->front, *r;//p指向队头数据节点 if (p != nullptr)//释放数据节点占用空间 { r = p->next; while (r != nullptr) { delete p; p = r; r = p->next; } } delete p, q;//释放链队结点占用空间 } //判断队列是否为空 void QueueEmpty(LiQueue *q) { return q->rear == nullptr; } //进队 /* 包含两种情况 1.原队列为空 2.原队列非空 */ void enQueue(LiQueue *&q, ElemType e) { Qnode *p; p = new Qnode; p->data = e; p->next = nullptr; if (q->rear == nullptr)//若链队为空，新结点是队首节点又是队尾结点 { q->front = q->rear = p; } else { q->rear->next = p;//将*p结点链接到队尾，并将rear指向它 q->rear = p; } } //出队 /* 包含三种情况 1.原队列为空 2.原队列只有一个结点 3.其他情况 */ bool deQueue(LiQueue *&q, ElemType &e) { Qnode *t; if (q->rear == nullptr)//队列为空 { return false; } t = q->front;//t指向第一个数据节点 if (q->front == q->rear)//队列中只有一个结点时 { q->front = q->rear = nullptr; } else { q->front = q->front->next;//队列中有多个结点时 } e = t->data; delete t; return true; }

Eg： 采用一个不带头节点只有一个尾结点指针rear的循环单链表存储队列，设计队列的初始化，进队和出队等算法。

//初始化队列 void initQueue(LinkList *&rear) { rear = nullptr; } //判空 bool queue(LinkList *rear) { return rear == nullptr; } //进队 void enQueue(LinkList *&rear, ElemType x) { LinkList *p; p = new LinkList;//创建新结点 p.data = x; if (rear == nullptr)//原链队为空 { p->next = p;//构成循环链表 rear = p; } else { p->next = rear->next;//将*p结点插入到*rear节点之后 rear->next = p; rear = p;//rear指向新插入的结点 } } //出队 bool deQueue(LinkList *&rear, ElemType &x) { LinkList *q; if (rear == nullptr)//队空 { return false; } else if (rear->next == rear)//原队只有一个结点 { x = rear->data; delete rear; rear = nullptr; } else//原队中有两个或以上的结点 { q = rear->next; x = q->data; rear->next = q->next; delete q; } }

栈和队列都是存放多个数据的容器，通常用于存放临时数据。 1.如果先放入的数据先处理，则使用队列 2.如果后放入的数据先处理，则使用栈

栈与队列的比较

一些习题： 1.设循环队列的存储空间为a[0…20],且当前队头指针(f指向队首元素的前一位置)和队尾指针(r指向队尾元素)的值分别为8和3，则该队列中元素个数为？ 解：16，这里的MAXSIZE=21，其中的元素个数是(r-f+MAXSIZE)%MAXSIZE= 2.假设用一个不带头结点的单链表表示队列，队头在链表的(？)位置。 解：链头 3.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为？ 解：2和4，rear=0，进队2个元素后，rear循环递增2，rear=2；front=3，出队一个元素后，front循环递增1，front=4. 4.一个循环队列中用data[0…n-1]数组保存队中元素，另设置一个队尾指针rear和一个记录队中实际元素个数的变量count，则该队中最多可以存放的元素个数为？ 解：n个，队满的条件为count==n 5.已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别为？ 解：0和n-1，在循环队列中，进队操作是队尾指针rear循环递增1，再在该处放置进队的元素，本题要求第一个进入队列的元素存储在A[0]处，则rear应为n-1，才能使得(rear+1)%n =0。而队头指针指向队头元素，此时队头位置为0，所以front的初值为0。

以上 如果此篇博客对您有帮助欢迎点赞与转发 有疑问请留言或私信 2020/10/3