栈
栈的数学性质
n个不同元素进栈，出栈元素不同排列的个数为,公式称为卡特兰数。
栈的顺序存储
栈是一种操作受限的线性表，类似于线性表，它有对应的两种存储方式。
1、顺序栈
- 栈顶指针初始时位置top=-1，栈满情况：
- 入栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素，操作如下：
top->next=top; top=x 或 data[++top]=x /先加指针，再传值。
- 出栈操作：栈非空时，先取栈顶元素值，再将栈顶指针减1，操作如下：
x=top->data;top=top->next 或 x=data[top--] /先取值，再移指针。
栈空条件：top=-1；栈满条件：top==Maxsize-1；栈长：top+1，栈顶元素：data[top]
若栈顶指针初始化top=0时，即top指向栈顶元素的下一个位置，则
入栈操作：
top=x，top->next=top; 或 data[top++]=x /先传值，再上移指针。
出栈操作：
top=top->next；x=top->data 或 x=data[--top] /先下移指针，再传值。
栈空条件：top=0；栈满条件：top==Maxsize；栈长：top，栈顶元素：data[top-1]
注意：
由于顺序栈的入栈操作受数组上界的约束，当对栈的最大使用空间估计不足时，有可能发生栈上溢，因此应及时处理，避免出错。
顺序栈在进行入栈运算时，可能发生栈的上溢，在进行出栈运算时，可能发生栈的下溢。
顺序栈、链栈上进行进栈操作时,链栈可不需判断栈满。
链栈一般不需要头结点,因为无头结点的链栈运算也很方便。
共享栈
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸。
两个栈的栈顶指针都指向栈顶元素，top0=-1时，0号栈为空，top1=Maxsize=10时，1号栈为空；仅仅当两个栈顶指针相邻(top1-top0=1)时，判断为栈满。
当0号栈进栈时，top0先加1再赋值，1号栈进栈时，top1先减1再赋值；出栈时则恰好相反。
共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间都被占满时，才发生上溢。其存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。
2、链栈
链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表表头进行的，这里规定链栈没有头结点。
基于链式存储便于结点插入、删除的特性，链栈的操作和链表类似，入栈和出栈的操作都在链表的表头进行。需要注意的是，对于带头结点和不带头结点的链栈，具体实现会有所不同。
相比顺序栈，链栈最大优势在于它可以动态分配存储空间，而顺序栈采用数组存储，数组大小是固定的，不能动态分配。
小结
采用非递归方式重写递归程序时，并非必须使用栈，因为斐波拉切数组迭代实现只需要一个循环即可实现。
确定了入栈次序，未必可确定出栈次序。
对于双向循环链表，不管是表头指针还是表尾指针，都可以很方便地找到表头结点，方便在表头做插入或删除操作。而单循环链表通过尾指针可以很方便地找到表头结点，但通过头指针找尾结点则需要遍历一次链表，需要花费O(n)的时间。
链栈采用不带头结点的单链表时，进栈操作需要在首部插入一个结点x(即x->next=top),插入完后需将top指向插入的结点x。
队列
1、队列的顺序存储
队列的顺序存储是分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针front，队尾指针rear。
- 初始状态(队空条件)：Q.front==Q.rear==0
- 进队操作：队不满时，先送值到队尾元素，再将队尾指针加1.
- 出队操作：队不空时，先取队头元素值，再将队头指针加1.
1.2、循环队列
当队首指针Q.front=Maxsize-1后，再前进一个位置就自动到0，这可以利用除法取余运算来实现。
初始时：Q.front==Q.rear==0
- 队首指针进1：
Q.front = ( Q.front + 1 ) % Maxsize - 队尾指针进1：
Q.rear = ( Q.rear + 1 ) % Maxsize - 队列长度：
( Q.rear + Maxsize - Q.front ) % Maxsize - 出队入队时：指针都按顺时针方向进1
队满的判定条件
队满条件：( Q.rear + 1 ) % Maxsize = Q.front
队空条件：Q.front == Q.rear
队列中元素的个数：( Q.rear + Maxsize - Q.front ) % Maxsize
2、队列的链式存储结构
队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头结点，队尾指针指向队尾结点，即单链表的最后一个结点。
当Q.front==NULL且Q.rear==NULL时，链队列为空。
由于不带头结点的链式队列在操作上往往比较麻烦，因此通常将链队列设计成一个带头结点的单链表。
实际上带头结点的单链表比不带头结点的单链表实现操作要方便的多。
用单链表表示链式队列特别适合于数据元素变动比较大的情况，而且不存在队列满且产生溢出的问题。另外，假如程序中要使用多个队列，与多个栈的情形的情况，最好使用链式队列，这样就不会出现存储分配不合理和"溢出"的问题。
3、双端队列
双端队列是指允许两端都可以进行入队和出队操作的队列，其元素的逻辑结构仍是线性结构，将队列的两端分别称为前端和后端，两端都可以入队和出队。
输出受限的双端队列
允许在一段进行插入和删除，在另一端只允许插入的双端队列。
输入受限的双端队列
允许在一端进行插入和删除，但在另一端只允许删除的双端队列。
若限定双端队列从某个端点插入的元素只能从该端删除，则该双端队列就蜕变成为两个栈底相邻的栈了。
最适合用作链式队列的链表是：带队首指针和队尾指针的非循环单链表
最不适合用作链式队列的链表是：只带队首指针的非循环双链表
在用单链表实现队列时，队头设在链表的链头位置
用链式存储的队列进行删除操作时头尾指针可能都要修改。
栈与队列的相同与不同
不同点：
- 删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行。
- 队列先进先出，栈先进后出。
- 顺序栈能够实现多栈空间共享，而顺序队列不能。
- 遍历数据速度不同。
- 栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来。
队列则不同，它基于地址指针进行遍历，而且可以从头或尾部开始遍历无需开辟临时空间，速度要快的多。
相同点：
- 都是线性结构。
- 插入操作都是限定在表尾进行。
- 都可以通过顺序结构和链式结构实现。
- 插入与删除的时间复杂度与空间复杂度上两者均相同。
网友评论