导言:栈和队列是一种受限制的线性表，比如栈和队列不能从中间某个部分插入或删除
1.栈
1.1顺序栈
利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素
关于代码：压入(push):S[top++]=a(n+1)
弹出(pop):e = S[--top]
?先使用top指针，先找到a0地址，后放入数据元素(进栈操作)，随后指针自增，指向下一位地址。如果指针指向a0地址的时候未放入元素即为空栈。待到a5放入元素后，指针移向a6的位置，入再添加元素则产生上溢，这个时候如果要用pop指针，指针先移动到下一个a5位置，进行删除元素(出栈)的操作，直到删除a0的数据之后，若再删指针移向a(-1)的位置，因为没有数据删除则无法进行删除操作，此时出现下溢。
1.2链栈(很喜欢这个名字,真的有一种重振旗鼓,坚强不屈的代入感.)
头插法：删除和插入操作都是在头部进行，s为头节点，头指针指向头节点，头节点的指针域指向首元节点，后面依次形成链表形式，因为栈是先行后出，那么如何判断c是先插入还是b先插入还是a先插入呢
因为一个元素进入栈时是沉入栈底，所以第一个插入的是a，随后第二个插入b，后为c，这里另加一条关于单链表的中间插入操作，这里我们列出两行代码 p->next = b->next,此处说明把b的指针赋值给p的指针,后给b node建立一条可以指向节点p的指针,最后断开b指向a的指针,为什么最后才断开?因为一旦之前断开导致后面的数据无法找到.代码为p->next = p,说明b节点的直接后继节点为p节点.
2.队列
所有插入删除操作限定在表的一端进行,所有删除操作在表的另一端进行
队头:允许删除的一端(出队)
队尾:允许插入的一端(入队)
2.1顺序队
什么是顺序队?它是一组连续地址存储,需设置头指针front和尾指针rear分别指向队列的列头和列尾
rear和front指针都是++i形式,先自增后使用,此处front和rear指针都指向a(-1)的位置,rear是先从-1指向0后加元素,front是先从-1指向0后进行删除数据操作,那么当rear=front都指向5的时候,是什么情况呢,比如rear一直加数据加数据,如果到栈顶继续执行,则先指向6的地方在进行加元素的操作,发现上溢,可此时真的上溢了吗,front指针一直在后面执行出队操作,所以栈此时此刻并没有满,称为假上溢,所以我们来看上面那个问题,我们并不知道是rear先到还是front先到,所以若front先到5,rear后到5则此时栈为满栈,若rear先到5,front后到5,则此时栈为空栈.此时该怎么办这时候我们想到顺序循环队列
引进mod法则,如上图,即mod法则或者有可以说%法则,?由上面当rear指针指向5位置,把5%5的值赋值给指针,让指针指向0,形成环形顺序表,然后回到0的位置继续进行增删操作
?
2.2链队列
带有头指针和尾指针,头指针指向对头节点,尾指针指向队尾节点
这里区别双向链表,双向链表只含有一个头指针和两个指针域为null的节点
此处front在左边一个个进行出队操作,rear在右边一个个进行入队操作,其顺序如下图
其操作有点类似单链表增删节点的操作,只不过我们这是在头尾进行操作
线性表分为顺序表,单链表,双向链表和循环链表,循环列表著名的有约瑟夫环,此处列出一些关于双向链表的循环链表的图示.
简单描述:具有一个指向左侧指针域为null的节点,总感觉缺少了点什么,如果我们在3的数据域下面也增加一个头指针会非常醒目,这是一个又中间为数据域左右两端都为指针域的节点结构,分别从左上和右下都是两种形式的单链表模式,非常直观
简单描述:一个头指针出发指向最右侧节点后,最右侧节点指针域不为空,而是选择继续指向头节点(或者首元节点),这里是否为首元或者头节点根据题目和你的需求来判断.
?
?总结:
线性表(有穷数据)分为链表和顺序表,现在我们来比较它们的优劣标准
1.单链表的存储比顺序表多,同等数据单链表多占用了存储空间
2.在单链表中进行插入,删除运算比在顺序表里面容易,顺序表的插入和删除需要移动后面的大量数据
3.对于顺序表,可随机访问任意元素(根据内存连续公式找到对应地址上的数据),而在单链表中,需要按照顺着链的指针逐个进行查找.
?
?
?
?
?