数据结构笔记

顺序栈和顺序队列使用动态数组实现
以下不是C++中stack的实现

顺序栈

特点：后进先出，先进后出
栈可以用数组或者链表写
开始时，栈顶Top=-1

顺序栈操作

Push（栈顶添加元素）
Top（返回当前栈顶数据）
Pop （删除栈顶数据）
IsEmpty（检查栈是否为空）

数组实现

实现自动扩大数组大小

模板类实现和声明要写在一起

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

  template<class T>
  void ChangeSize1D(T* &a,const int oldSize, const int newSize)
  {
      if(newSize<0) throw "newSize must be >=0";
      T* temp =new T[newSize];
      int number = min(oldSize,newSize);
      std::copy(a,a+number,temp);
      delete[] a;
      a=temp;
  }

顺序队列（Queue）

特点：先进先出，后进后出

队列操作

• Push（队尾添加元素）
• Pop （队首删除元素）
• Front（返回当前队首数据）
• Rear（返回当前队尾数据）
• IsEmpty（检查队列是否为空）

实现回绕（利用数组删除后留下的空间）

1. rear=front
2. front++
3. 如果front=rear表示队列满了，要自动扩大数组大小

链表

1. 链表：1.数据域 2.链接域
2. 数组缺点：插入数据时慢，需要向后移动，删除数据时，需要向前移动。
3. 链表可以弥补这些缺点。

树

• 数组缺点：插入数据，数据要移动。
• 数组优点：二分查找
• 链表缺点：无法二分查找
• 链表优点: 插入删除数据快
• 树 = 数组的优点 + 链表的优点