&10 基本数据结构——栈，队列和链表

#1，栈（stack）

定义[来自百度]：栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

原理和操作：实现的是一种后进先出策略（last-in, first-out, LIFO），相关操作包括：判空(stack-empty)、出栈(stack-pop)和入栈(stack-push)。

特殊属性：S.top，其中，S是栈名，S.top指向最新插入的元素。若用数组实现栈，则S.top==i，i是数组的下标值。

1 stack-empty(S)
2     if S.top==0
3         return true;
4     else 
5         return false;

stack-empty

1 stack-push(S,x)
2     if S.top!=n
3         S.top=S.top+1;
4         S[S.top]=x;
5     else
6         OVERFLOW;

stack-push

1 stack-pop(S)
2     if S.top!=0
3         S.top=S.top-1;
4         return S[S.top+1];
5     else
6         UNDERFLOW;

stack-pop

#2，队列(queue)

定义[来自百度]：队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

原理和操作：实现的是一种先进先出的策略（first-in, first-out, FIFO），相关操作有：入队(en-queue)和出队(de-queue)。

特殊属性：两个，Q.head指向对头元素，Q.tail指向下一个新元素将要插入的位置，其中Q是队列名。Q={Q[0],Q[1]..., Q[n-1]}={Q[Q.head], Q[Q.head+1]...,Q[Q.tail-1]}，并在最后的位置“环绕”，感觉好像位置0紧邻在位置n-1后面形成一个环序。如果Q.head=Q.tail+1，队列是满的，再添加元素会发生上溢；同理，如果Q.head=Q.tail，继续出队则会发生下溢。

这里给出两个版本的伪代码，一个是我自己写的en-queue和de-queue，另一个是书中给出的EN-QUEUE和DE-QUEUE。

1 en-queue(Q,x)
2     if Q.head != Q.tail+1
3         Q.tail = Q.tail+1;
4         Q[Q.tail-1]=x;
5     else
6         OVERFLOW;

en-queue

1 de-queue(Q)
2     if Q.head != Q.tail
3         Q.head=Q.head+1;
4         reutrn Q[Q.head-1];
5     else
6         UNDERFLOW;

de-queue

1 EN-QUEUE(Q, x)
2     Q[Q.tail]=x;
3     if Q.tail==Q.length
4         Q.tail=1;
5     else
6         Q.tail=Q.tail+1;

EN-QUEUE

1 DE-QUEUE(Q)
2     x=Q[Q.head];
3     if Q.head==Q.length;
4         Q.head=1;
5     else
6         Q.head=Q.head+1;
7     return x;

DE-QUEUE

#3，链表（list）

定义：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

原理和操作：分单链表和双链表，单链表的任意两个相邻元素之间是单箭头，而且所有的箭头方向都相同，双链表的任意相邻元素都是双箭头。而且两种链表都有搜索(list-reserch)、插入(list-insert)和删除(list-delete)操作。

特殊属性：单链表有链表头(L.head)，指向链表的第一个元素；双链表有链表头(L.head)或者哨兵(L.nil)。

单链表的实现很容易，每个元素只有key和next两个属性值，方便处理。下面给出带(head)而非(哨兵)的双链表的各项操作伪代码：

1 lists-research(L, k)
2     x=L.head;
3     while x!=NULL and x.key!=k
4         x=x.next;
5     return x;

lists-research

1 lists-insert_head(L, x)
2     x.next=L.head;
3     if L.head!=NULL
4         x.next.prev=x;
5     L.head=x;//注意：一定要跟新list的head属性值
6     x.prev=NULL;

lists-insert_head

1 lists-delete(L, x)
2     if x.prev!=NULL
3         x.prev.next=x.next;     
4     else 
5         L.head=x.next;
6     if x.next!=NULL
7          x.next.prev=x.prev;

lists-delete

我也还在学习巩固中，如果文中所言有误，欢迎各位批评指正！