[数据结构与算法]数据结构第八章：栈与队列

一、栈

????????1、概念
?? ??????????? ?数据的插入和删除都是在同一端，不能在其他任何位置，这种逻辑结构称之为栈。
????????2、特性
?? ??????????? ?后进先出。或者说先进后出
????????3、分类
?? ??????????? ?链式栈、顺序栈

????????4、链式栈?
?? ??????????? ?用来存储栈元素的内存空间不是连续的。其实就是一个头插头删（或者尾插尾删）的特殊的链表
????????5、顺序栈
?? ??? ?????????用来存储栈元素的内存空间是连续的。

二、队列

????????1、概念
?? ??????????? ?插入数据（入队）在指定的一端，删除数据（出队）必须在另一端，不能在其他任何位置，这种逻辑结构称之为队列。
????????2、特性
?? ??????????? ?先进先出
????????3、分类
?????????? ??? ?链式队列、顺序队列

????????4、链式队列?
?? ??????????? ?用来存储队列元素的内存空间不是连续的。其实就是一个头插尾删的特殊的链表
????????5、顺序队列?
?? ??????????? ?用来存储队列元素的内存空间是连续的。
?? ?
? ? ? ? 6、链式队列的设计

????????????????管理结构体?? ??? ?
????????????????typedef int QElemType;?? ?

????????????????//数据结点
????????????????struct node{
?????????????????? ?QElemType data;
?????????????????? ?struct node *next;
????????????????};

????????????????struct list_queue{
?????????????????? ?struct node*queue;//存储链表的数据首节点地址
?????????????????? ?int size;//队列的大小，也就是队列元素的个数
????????????????};

?

????????7、顺序队列的设计
????????????????设计队列管理结构体?? ??? ?
????????????????typedef int QElemType;

????????????????struct sequent_queue{
?? ?????????????????QElemType *queue;//定义一块连续的内存空间存储队列元素，queue存储队列元素内存空间的起始地址
? ? ? ? ? ? ? ? ? ? ?int size;//队列的大小
? ????????????????? ?int ?first ;//队头偏移量
? ????????????????? ?int ?last;//队尾偏移量 ??
????????????????};

?