数据结构知识点-栈和队列

栈和队列

一、栈

栈又称为“后入先出(LIFO:Last In First Out)”线性表

空栈:0单元使用则TOP=-1;0单元不用则TOP=0

顺序栈可能发生上溢或者下溢,而链栈一般不会发生上溢

链栈的栈顶指针,相当于链表的头指针。链栈的栈顶结点,相当于链表的开始结点,入栈采用头插的方法

注意函数中形参不能反向传递,故函数中对指针形参指向的修改,不能带回主调函数。但是对指针形参所指空间的内容的修改,是可以带回主调函数的。

解决形参不能反向传递的方法:

将要带回主调函数的形参定义为全局变量(缺点:函数的独立性下降,不利于移植)

将要带回主调函数的形参作函数返回值

传地址(指针或多重指针)(C语言,定义新形参为指向原形参类型的指针,即将传值改为传址)

传引用(C++,形参定义为引用类型)

为解决不带头结点的链栈可能出现形参不能反向传递的问题,一般可采用上6所述方法,常用的方法是

将栈顶指针定义为全局变量

将修改后的栈顶指针作为函数返回值

改用带头结点的链栈

双重封装构造仅含栈顶指针的头结点

定义二重指针,即指向指针(栈顶指针)的指针,此时即可通过修改二重指针所指空间的内容(栈顶指针)来带回修改后的栈顶指针(但是双重指针比较复杂,不建议使用)

函数的设计原则之一是,不改变无关量。如在取栈顶元素等“引用(拷贝)型而非加工型”操作时,不应该将原栈顶结点作为结果返回,而应该开辟新的空间拷贝并存储取栈顶结点并返回之,否则后续对取到的栈顶结点进行操作时可能会影响原链栈数据,而返回拷贝结点可以避免之

void类型函数返回主调函数的语句:

二、队列

队列:只允许在表的一端(队头)进行删除操作,在表的另一端(队尾)进行插入的特殊线性表

顺序队列队头指针front总是指向当前队头元素的前一个位置,队尾指针rear指向当前队尾元素(队头在低位序处,队尾在高位序处)

顺序队列队空:rear\==front;队满:rear-front\==maxsize

顺序队列的假上溢:顺序队列中存在未用的存储单元,但是不能继续进行入队操作

解决方法:

将队列元素依次前移,但缺点是数据移动量大

将顺序队列构造为循环序列

链队列

循环队列解决队满和队空无法区分的方法

设置队头、队尾、及空/满标志

设置队头、队长

牺牲一个存储单元(front所指单元),即使得队满时rear指向front前一个单元,队空时二者指向同一个单元(此时队列长度为MAXSIZE-1)(推荐)

循环队列进行操作时,应该进行循环意义(%maxsize)下的操作

循环意义下的加法:(a+b)%maxsize

循环意义下的减法:(a-b+maxsize)%maxsize;加上maxsize为了使结果为正数

入队:

出队:

求队长:

队满:

队空:

数据结构初始化:开辟空间+成员赋初值

链队列仅限在表头删除表尾插入(表头为链表的开始结点,表尾为终端结点)

链队列的头结点也是采用二次封装,内含头、尾指针

与顺序对不同的是,链队的头指针指向头结点,而非其前一个结点

链队列s头结点p出队操作

更改头指针()

判断出队后是否为空,是则置空队()

释放p()

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180120G0Q27500?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券