栈和队列的实现以即相应QJ题的总结

1.首先对顺序表以及链表的区别总结

对缓存利用率的理解：

CPU处理内存中的数据有两种方式

(1)处理寄存器从内存中获取的数据 (一般是几个字节大小)

(2)内存到CPU过程中还可以通过缓存路线运输

内存的数据通过三层缓存加工，最后在第三层被CPU处理(常用于处理大数据)

从内存到缓存的数据运输是从要使用的数据开始之后的一段数据(不管是否要使用)

如果后面的数据有用就使用，不然就从新的数据段开始运输.

因此，顺序表由于空间上连续，缓存段中的有效数据多，因此缓存利用率高.

链表由于空间上不连续，缓存段中的有效数据少，因此缓存利用率低.

正篇开始

1.queue的实现

queue遵循尾进头出,因此采用链表的方式实现

为保证时间复杂度的最小，我们需要对链表的头和尾进行保存同时对大小进行管理，因此考虑使用struct 进行统一管理.

结点的创建

对象的设计

所有成员的申明

成员的实现

栈的实现

遵序头进头出，露头就秒

节点申明

成员申明

top如果想要指向最后一个元素，top = -1 的初始化才对.

但此处我们更想要top 有size的效果，因此要top = 0，但此时top就指向最后一个元素的下一位了.

下面是三道题，使用的队列和栈与上面的完全相同

1.使用两个队列实现栈

解法：先将数全部push 到一个队列中，然后将size - 1 个放进另一个队列中，剩下的一个就是stack的第一个.

代码

针对于pop和top，可以采用假设法

不断的试错后，我明白了，如果只是对指针内部成员进行修改，一级指针即可，二级指针一般出现在需要获取一级指针地址或要修改一级指针指向的时候.

用栈生成队列

解法：一个栈作为push,一个作为pop.pop完了再push.

最后一题，循环队列

解法：设计k+1个位置，使用%操作来进行循环

对于循环的再补充啊

a % N ,N的大小取决于循环圈的大小，N与循环圈等大，为了最后一位N-1到N位越界时%N为0到第一位.