数据结构c++--表、栈和队列

数据结构c++--表、栈和队列

表、栈和队列

• STL

---

STL

标准模板库：模板库中的数据结构称为集合或容器。

1、表ADT
形如A0，A1，A2，…，A3，AN-1的一般的表，表的大小是N，我们将N=0的表称为空表。

（1）简单数组实现：
虽然数组是静态的，但是c++中的vertor类运行改变数组的大小，解决了数组大小固定的问题。

• 遍历数组：线性时间
• 查找元素：常数时间，可以通过下标来直接获取到某个元素
• 插入和删除：线性时间，插入需要后移元素，删除需要前移元素
  （2）链表实现：
  链表是有一系列不一定相连的结点组成，每个结点包含数据和指向下一个结点的指针组成，可以直接在尾结点链接新的结点，所以是动态的。
• 遍历数组：线性时间，需要从头结点遍历到尾结点
• 查找元素：线性时间。只能通过遍历来完成
• 插入和删除：如果知道元素的位置的情况下插入和删除都只需要常数时间

2、通用方法

//List和vector
int size() const:返回容器内元素的个数
void clear():删除容器内所有元素
bool empty():如果容器没有元素返回true，否则返回false
void push_back(x):在表的尾部添加x
void pop_back():删除表的尾部的对象
//List
void push_front():在表的前端添加
void pop_front():删除表的前端的对象