【算法】基本数据结构
栈
1、后进先出
2、栈有一个属性为S.top执行最新插入的元素
3、弹出称为pop,插入称为push
4、上溢和下溢:
如果试图对一个空栈执行弹出操作,则称为下溢;
如果S.top超过了n,则称为上溢,在下面伪代码中不考虑上溢问题
队列
1、先进先出
2、队列有对头head和对尾tail
3、插入称为入队(ENQUEUE),删除称为出队(DEQUEUE)
4、上溢和下溢:
当head=tail时,队列为空
当初始化时,head=tail=1
如果试图从空队列中删除一个元素,则队列发生下溢
当head=tail+1,队列是满的,此时试图向队列中插入一个元素,则队列发生上溢
链表
1、单链表或双链表,排序会未排序,循环或非循环
3、使用哨兵(头结点),忽视表头和表尾的边界条件,是下述操作变得更加简单方便
2、链表的搜索
3、链表的插入(头部插入)
4、链表的删除(先搜索在插入)