栈和队列

栈和队列都是动态集合，且在其上进行delete操作所移除的元素都是预先设定的。在栈（stack）中，被删除的是最近插入的元素，其实现的是一种后进先出策略，而在队列中，被删除的总是在集合中存在时间最长的那个元素。队列实现的是一种先进先出策略。

栈（堆盘子）

栈上的insert操作称为压入（push），无元素参数的delete操作称为弹出（POP）。要查询一个栈是否为空，可以以用STACK-EMPTY操作，如果对一个空栈进行POP操作，则称为栈下溢（错误），如果栈顶超过了n,则称栈上溢。用数组S[1,2,···n]来实现一个最多可容纳n个元素的栈，S.top指向最新插入的元素，栈中包含的元素为S[1，···，S.top]，其中S[1]是栈底元素，S[S.top]是栈顶元素。
栈的几种操作：
STACK-EMPTY

  if S.top==0;
      return TRUE;
  else return FALSE;

PUSH(S,x)

S.top=S.top+1;
S[S.top]=x;

POP(S)

if STACK-EMPTY(S)
   error("underflow")
else S.top=S.top-1;
return S[S.top+1];

队列（顾客排队）（环绕式）

队列上的INSERT操作称为入队（ENQUEUE），DELETE操作称为出队（DEQUEUE）。类似栈的POP操作一样，DEQUEUE操作也没有元素参数。 数组Q[1，···，n]来实现一个最多容纳n-1个元素的队列。Q.head指向对头元素，Q.tail指向下一个新元素将要插入的位置，当Q.head=Q.tail时，队列为空。若Q.head=Q.tail=1，如果试图从空队列中删除一个元素，则队列发生下溢。若Q.head=Q.tail+1，队列时满的，此时若试图插入一个元素，则队列发生上溢。
队列的几种操作：
ENQUEUE(Q,x)

Q[Q.tail]=x;
if Q.tail==Q.length;
        Q.tail=1;
else
        Q.tail=Q.tail+1;

DEQUEUE(Q)

x=Q[Q.head];
if Q.head=Q.length;
        Q.head=1;
else  
        Q.head=Q.head+1;
return x;

链表（其中的各对象按线性顺序排列）

数组的线性顺序是由数组下标决定的，然而与数组不同的是，链表的顺序是由各个对象里的指针决定的。

双向链表

双向链表L的每一个元素都是一个对象，每个对象有一个关键字key和两个指针，next和prev。对象中还可以包含其他辅助数据（或称为卫星数据）。设x为链表的一个元素，x.next指向它在链表中的后继元素，x.prev则指向它的前驱元素。若干x.prev为NULL，则是链表中的第一个元素，即链表的头，若x.next=NULL，则为链表的尾。属性L.head指向链表的头，若L.head=MULL，则链表L为空。

单向链表：省略prev指针

以排序链表

循环链表

链表的操作
LIST-SEARCH

x=L.head;
while x!=NULL&&x.key!=k;
       x=x.next;
return x;

LIST-INSERT(L.x)

x.next=L.head;
if L.head!=NULL;
   L.head.prev=x;
L.head=x;
x.prev=NULL;

LIST-DELETE

if x.prev!=NULL;
    x.prev.next=x.next;
else  L.head=x.next;
if x.next!=NULL;
 x.next.prev=x.prev;