数据结构栈（顺序栈、链栈、插入push、删除pop）、队（循环队，链队、入队push，出队pop）知识点梳理

您所在的位置：网站首页 › 顶top › 数据结构栈（顺序栈、链栈、插入push、删除pop）、队（循环队，链队、入队push，出队pop）知识点梳理

数据结构栈（顺序栈、链栈、插入push、删除pop）、队（循环队，链队、入队push，出队pop）知识点梳理

2024-07-09 07:59| 来源: 网络整理| 查看: 265

数据结构栈知识点梳理一栈的定义

栈（stack）是限定仅在表尾进行插入和删除操作的线性表

不含任何元素的栈称为空栈

允许插入和删除的一端成为栈顶（top），另一端称为栈底（bottom）

具有LIFO（Last In First Out）结构

栈元素具有线性关系，即前驱和后继，是特殊的线性表

二栈的插入、删除栈的插入操作—进栈（push）

在这里插入图片描述

栈的删除操作—出栈（pop）

在这里插入图片描述

三栈的抽象数据类型 ADT 栈(stack) Data 同线性表。元素具有相同的类型，相邻元素具有前驱和后继关系 Operation InitStack(&S):初始化操作，建立一个空栈S DestroyStack(*S):若栈存在，则销毁它 ClearStack(*S):将栈清空 StackEmpty(S):若栈为空，返回true，否则返回false GetTop(S,*e):若栈存在且非空，用e返回S的栈顶元素 Push(*S,e):若栈S存在，插入新元素e到栈S中并称为栈顶元素 Pop(*S,*e):删除栈S中栈顶元素，并用e返回其值 StackLength(S):返回栈S的元素个数 endADT 四栈的顺序存储结构

栈只能在一头插入和删除，下标为0的一端作栈底比较好。定义一个top变量来指示栈顶元素在数组中的位置。

存储栈的长度StackSize，栈顶位置top必须小于StackSize。

当栈有一个元素时，top=0，所以空栈的判定条件为top=-1

出栈和入栈的时间复杂度都是O(1)

栈的结构定义 typedef int SElemType;/*SElemType 类型根据实际情况而定，这里假设为int*/ typedef struct { SElemType data[MAXSIZE]; int top;/*栈顶指针*/ }SqStack; 进栈操作

在这里插入图片描述

进栈push操作

Status Push(SqStack *S,SElemType e) { if(S->top == MAXSIZE - 1)/*栈满*/ { return ERROR; } S->top++;/*栈顶指针+1*/ S->data[S->top] = e;/*将新插入元素赋值给栈顶空间*/ return OK; } 出栈操作 Status Pop(SqStack *S,SElemType *e) { if(S->top == -1) return ERROR; *e = S->data[S->top]; /*将要删除的栈顶元素赋值给e*/ S->top--; return OK; } 五两栈共享空间

栈的顺序存储

优点：插入和删除操作不需要元素

缺点：需要提前确认存储空间，或者用编程手段扩容，空间利用率不高

解决方法：两栈共享空间，为了增加空间利用率，可以用一个数组来存储两个栈

如图：让一个栈的栈底为数组的始端（下标为0处），另一个栈为栈的末端（下标n-1处），两个栈的元素增加，向中间延伸

栈1为空，top1 == -1；栈2为空，top2 == n；栈满 top1+1 == top2

在这里插入图片描述

/*两栈共享空间结构*/ typedef struct { SElemType data[MAXSIZE]; int top1; int top2; }SqDoubleStack; 插入操作

增加一个StackNumber判断插入栈1还是栈2

/*插入元素e为新的栈顶元素*/ Status Push(SqDoubleStack *S,SElemType e,int stackNumber) { if(S->top1+1 == S->top2) return ERROR; if(stackNumber == 1) S->data[++S->top1]=e; else if(stackNumber == 2) S->data[--S->top2]=e; return OK; } 插入操作 /*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR*/ Status Pop(SqDoubleStack *S,SElemType *e,int stackNumber) { if(stackNumber == 1) { if(S->top1 == -1) return ERROR; *e = S->data[S->top1--]; } else if(stackNumber == 2) { if(S->top2 == MAXSIZE) return ERROR; *e = S->data[S->top2++]; } return OK; } 六栈的链式存储结构

链栈不需要头结点

基本不存在栈满的情况，除非内存没有空间

链栈空top == NULL

在这里插入图片描述

链栈结构代码 typedef struct StackNode { SElemType data; struct StackNode *next; }StackNode,*LinkStackPtr; typedef struct LinkStack { LinkStackPtr top; int count; }LinkStack; 进栈操作

在这里插入图片描述

/*插入元素e为新的栈顶元素*/ Status Push(LinkStack *S,SElemType e) { LinkStackPtr s = (LinkStackPtr)malloc(sizeof(StackNode)); s->data=e; s->next=S->top; S->top=s; S->count++; return OK; } 出栈操作

在这里插入图片描述

Status Pop(LinkStack *S,SElemType *e) { LinkStackPtr p; if(StackEmpty(*s)) return ERROR; *e=S->top->data; p=S->top; S->top = S->top->next; free(p); S->count--; return OK; } 七总结

栈在使用过程中元素变化不可预料，有时很小，有时很大，那么最好用链栈。反之，大小在可控的范围内，用顺序栈。

栈更多的应用在递归。

数据结构队知识点梳理一定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表

队列是一种先进先出（First In First Out）的线性表

允许插入的一端称队尾，允许删除的一端称队头

在这里插入图片描述

二队列的抽象数据结构 ADT 队列(Queue) Data 同线性表。元素具有相同的类型，相邻元素具有前驱和后继 Operation InitQueue(*Q):初始化操作，建立一个空队列Q DestroyQueue(*Q):若队列Q存在，则销毁它 ClearQueue(*Q):将队列清空 QueueEmpty(Q):若队列为空，返回true，否则返回false GetHead(Q,*e):若队列Q存在且非空，用e返回队列Q的队头元素 EnQueue(*Q,e):若队列存在，插入新元素e到队列Q中并成为队尾元素 DeQueue(*Q,*e):删除队列Q中的队头元素，并用e返回其值 QueueLength(Q):返回队列Q中的元素个数 endADT 三循环队列

顺序存储结构存在不足容易发生数组越界的错误，假溢出现象。

两个指针

为了避免队尾和队头重合使处理十分麻烦，所以引入两个指针。front指针指向队头元素，rear指针指向队尾元素；front==rear时，指空队列

循环队列定义

头尾相接的顺序存储结构称为循环队列。

出现的问题

在这里插入图片描述

当front==rear的时候可能是队列为空，或可能是队列为满

解决办法：

设置一个标志变量flag，当front == rear，且flag = 0时队列为空，当front == rear，且flag = 1时队列为满。当队列空时，条件就是front == rear，当队列为满的时候，修改其中的条件，保留一个元素空间，意思就是当队列满的时候，数组中还有一个空闲单元。

第二种解决方式不允许出现的情况

在这里插入图片描述

队满情况

在这里插入图片描述

四循环队列一些列操作顺序存储结构代码

队列满的条件： (rear+1)%QueueSize == front

通用的计算队列长度公式：（rear-front+QueueSize）%QueueSize

typedef int QElemType; /*循环队列的顺序存储结构*/ typedef struct { QElemType data[MAXSIZE]; int front; int rear; }SqQueue; 初始化循环队列 /*初始化一个空队列*/ Status InitQueue(SqQueue *Q) { Q->front = 0; Q->rear = 0; return OK; } 循环队列求长度 /*返回Q的元素个数，也就是当前队列的长度*/ int QueueLength(SqQueue Q) { return (Q.rear - Q.front + MAXSIZE)%MAXSIZE; } 循环队列的入队 /*若队列未满，则插入元素e为Q新的队尾元素*/ Status EnQueue(SqQueue *Q,QElemType e) { if((Q->rear+1)%MAXSIZE == Q->front) return ERROR; Q->data[Q->rear] = e; Q->rear = (Q->rear+1)%MAXSIZE; return OK; } 循环队列的出队 /*若队列不空，则删除Q中队头元素，用e返回其值*/ Status DeQueue(SqQueue *Q,QElemType *e) { if(Q->front == Q->rear) return ERROR; *e=Q->data[Q->front]; Q->front = (Q->front+1)%MAXSIZE; return OK; }

循环队列面临着数组溢出的问题，所以还需要不用担心队列长度的链式存储结构

五队列的链式存储结构

理解：队列的存储结构，相当于线性表的单链表，只不过它只能尾进头出，简称链队列

队头指针指向链队的头结点，队尾指针指向终端结点。

在这里插入图片描述

空队列，front和rear都指向头结点

在这里插入图片描述

链队的存储结构 typedef int QElemType typedef struct QNode /*结点结构*/ { QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct /*队列的链表结构*/ { QueuePtr front rear; }LinkQueue; 入队操作

在这里插入图片描述

/*插入元素e为Q的新的队尾元素*/ 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; Q->rear = s; return OK; } 出队操作

在这里插入图片描述

/*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/ Status DeQueue(LinkQueue *Q,QElemType *e) { QueuePtr p; if(Q->front == Q->rear) return ERROR; p = Q->front->next; if(Q->rear == p)/*若队头是队尾*/ Q->rear = Q->front; free(p); return OK; } 六循环队列和链队的比较

时间上：都是O(1)，循环队列事先申请空间，使用不释放；链队申请和释放结点需要耗时。

空间上：循环队列需要固定长度，会造成空间浪费。链队不存在这些问题，更加的灵活多变。

【本文地址】

公司简介

联系我们