上课老师用两个小时的时间讲了将近1/4本《Introduction to Algorithms》，结果当然是什么也听不懂。

所以接下来这几天，根据课上的PPT一点点捯饬捯饬关于Stacks、Queues、Linked lists、Rooted trees，以及Direct-address tables、Hash tables、Binary search tables的内容。

虽然课程针对日后的C++编程，但是课上并没讲编程上的实现。

1.Stack（栈）

首先引入了dynamic sets的概念。如果一个集合，可以进行添加或者删除的操作时，就可以被称为dynamic sets。

如果这个dynamic sets可以进行Search、Insert、Delete这三种操作，即可被成为dictionary（字典）。

Dictionary还可以进行Minimun(S), Maximum(S), Successor(S,x), Predecessor(S,x)操作。在这里S指代操作的Stack，x指代元素。

Dictionary 由key（关键码）和Element（元素）构成。

 

接下来正式讲Stack。

Stack是LIFO（Last-in, first-out）后进先出，支持Insert和Delete，但是不支持Search。

Insert又叫Push，进栈；Delete又叫Pop，出栈。

Stack有一个属性.top，可以对最近插入栈的element进行索引。初始状态下，S.top为0。

可以有如下运算

1. 判断Empty

if S.top ==0        #如果顶部，也就是最后进栈的数字为0
    return True     #空栈
else
    return False    #非空栈

 

2. Push

S.top = S.top + 1   #当前最上方栈+1
S[S.top] = x        #进+1后的那个栈

 

3. Pop

if StackEmpty(S)        #如空栈
    error"underflow"    #栈下溢，栈已空，但还想再取出信息，这种情况称为栈下溢
else S.top = S.top - 1  #删除栈顶元素
    return S[S.top + 1] #返回被删的栈key

 Remark:

栈的元素为S[1.2.3....S.top]，从1开始，而数组从0开始。

如果栈满了还在往里Push，则会overflow，就是溢出。

上面的3种操作都分别占用O(1)的时间复杂度。（挖坑：时间复杂度）

 

2.Queue（队列）

Queue（发音同'Q'）和栈一样都是线性存储结构。但是不同的是Queue是FIFO（First-in, First-out）先进先出。

同样支持Insert-EnQueue，以及Delete-DeQueue，但不支持Search。

对于Queue，有Q.head：队列的首个元素的索引；Q.tail：接下来插入的元素的索引

初始情况下，Q.head = Q.tail = 1。

1. EnQueue

Q[Q.tail] = x           #Q下一个插入元素的位置的值 = x
if Q.tail == Q.length   #如果Q尾部的位置 = Q的长度，即到了队列最后一位
    Q.tail = 1          #那么就回到首位置，因为不回就溢出
else
    Q.tail = Q.tail + 1 #代表没到队列最后，可以继续加key

 

2. DeQueue

x = Q[Q.head]           #将Q首元素的值赋给x
if Q.head == Q.length   #如果Q的首元素移动到了最后一位
    Q.head = 1          #则令首元素的key = 1，再从第1位开始移动
else Q.head = Q.head + 1#否则首元素key + 1，也就是第1个元素被delete后，第二个元素成为新的head
    return x            #返回被删除的值

 

同样的，上面的2种操作都分别占用O(1)的时间复杂度。

明天继续更Linked list以及Binary Tree。