文科僧的数据结构入门指南（二）:二维数组，栈与队列

Pre

• 顺序结构与链式结构：像数组这种分配的空间是连续的数据结构被称为顺序结构，而像链表这种分配的空间不为连续的，而是依靠指针域来获取指向下一个节点的地址的数据结构被称为链式结构．
• 栈与队列既可以用顺序结构来实现，又可以利用链式结构来实现

二维数组（矩阵）

一般把二维数组看成是一个具有行和列的矩阵，但其实在内存中分配的还是一段连续的空间．

如图，这是一个3行５列的二维数组，虽然在使用的过程中可以用类似a[2][3]获取到数值41的方法来使用，但是其实它在内存中依然是一个连续的空间,如row0 row1 row2其实是连着的.

栈

栈是一种先进后出的数据结构，只有在top端可以进行压入与压出，而bottom端不可做任何操作.

利用数组实现的栈(顺序栈)

同数组一样,也是分配一段连续的空间，用一个变量记录栈顶指针(top)所在的位置,当有了入栈出栈操作时就会改变该变量．
需要注意的是，这个top所指的位置既可以是最底部（top=0），又可以是栈容量加一(top=m+1),因为栈可以从最底部开始向上一个个地涨，又可以从最顶部开始向下一个个的加．
当入栈时,若top初始为0, 则会加一；若top初始为m+1, 则会减一.出栈相反.

例题:

设栈的顺序存储空间为S（1：m），初始状态为TOP＝m+1。现经过一系列入栈与退栈运算后，TOP＝20，
则当前栈中的元素个数为（C）
A） 30 B）20 C）m-19 D）m-20

因为栈的空间为S(1:m),初始为m+1,则可知为从顶部开始向下压的栈，每入栈一个则top-1.
图解

此类题可以通过画图的方式来跟随top指针的移动,top 初始指向的位置都是不可以存放元素的位置，每当有元素压入时，就指向刚刚压入的元素所在的位置．

链栈

链栈即为用一个top与bottom指针来记录位置节点的位置，并操作top与bottom节点来压入节点，压出节点.
我们之前学的栈的bottom其实都是不变的...不知道为啥你们考试的bottom是会变的...
我猜可能是这样...

因此，当top = bottom = NULL时，栈中无元素
top = bottom = 某个值 时，栈中有一个元素
top 不等于 bottom 时，有多少元素无法确定

队列

队列可以类比排队的过程，在队尾加入元素，在队首出元素
front为队首，rear为队尾, maxsize为

顺序队列

因为普通的顺序队列有缺陷（当front = rear时，无法确定是队满还是队空，因此一般的顺序队列都会空出一个元素来帮助区别队满与队空）
而顺序队列又会有假溢出的问题,所以一般使用循环队列．
循环队列 : 将这个数组想象为首尾相接的一个队列，循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0. 即当front+1 = 队列容量大小时，front重置为0.
(%为取余的意思，即为除以这个数取其余数，如5%3=2)
.
循环队列公式:
队头指针在队尾指针的下一位置时,队满.即front == (rear + 1) % MAXSIZE(队列最大容量)
当队头和队尾指针在同一位置时，队空。 front == rear;
计算循环队列中元素个数:n＝（rear-front+maxsize ) % maxsize
入队时：rear=(rear+1) % maxsize
出队时：front=(front+1) % maxsize

链队列

有两个指针来指示front与rear，与链栈不同的是，入队的时候是队尾改变，出队的时候是队首改变．
当front = rear = NULL时，队列中无元素
front = rear 不等于NULL时，队列有一个元素
front 不等于 rear时，无法确定