栈和队列

栈和队列相关知识学习思维导图，内容涵盖他们的定义及特点、实现方式、分类等知识，适用于预习、复习的参照。

栈和队列

• 栈：先进后出，后进先出
  • 定义及特点
    • 定义：仅在表尾进行插入或删除操作的线性表（只允许在一端进行插入、删除操作的线性表）
      • 栈顶（表尾）：允许插入——进栈、压栈、入栈
      • 栈底（表头）：允许删除——出栈
    • 空栈：不含任何元素的栈
  • 实现：栈顶指针（用于增加或移除元素）
    • 概要
  • 分类
    • 顺序栈（数组实现）
      • 定义顺序栈
        • 定义栈（数组）
          • //定义栈 string stack[200];//栈中存放数据类型 栈名[栈的大小]
        • 定义栈顶指针（int类型）
          • // 定义栈顶指针 int top=0;//整型（int） 栈顶指针名=0（初始位置）
        • 实际定义时类似于队列
        • 定义栈底指针
      • 初始化：为顺序栈动态分配一个预定义大小的数组空间
        • 1.为顺序栈分配一个maxsize的数组空间
        • 2.栈顶指针top置为0，表示空栈
          • int top=0;
        • 3.栈stack置为最大容量maxsize
          • string stack[naxsize];//栈中数据类型 栈名[栈的最大容量]
      • 判空：判断栈顶指针是否为0
        • if(top==0){//栈空 } else{//栈非空 }
      • 判满：判断顺序栈是否满了
        • 比较栈顶指针和栈的最大容量
          • if(top>=maxsize) {//如果栈顶指针≥栈的最大容量 return 0;//返回0（error） ｝
      • 入栈：在栈顶插入一个新元素
        • 1.判断栈是否满了（满了返回error）
        • 2.压入新元素，栈顶指针加一
          • stack [top++]=name;//栈名[栈顶指针++]=元素内容
      • 出栈：将栈顶元素删除
        • 1.判空，空返回0
        • 2.栈顶指针减一，栈顶元素出栈
          • top--;//栈顶指针减一 stack[top];//栈顶元素内容
      • 取栈顶元素：栈非空时，返回当前栈顶元素，但不移动栈顶指针（不删除栈内元素）
        • 1.判空，空返回0
        • 2.通过栈顶指针获取元素
          • stack[top];//栈顶元素
    • 链栈
  • C++中stack模板
    • 引入模板类，声明一个栈类
      • stack<string> myStack
    • top()：返回栈顶元素，类型为T&。 如果栈空返回值未定义。
    • push(const T& obj)：将对象副本压入栈顶。 通过调入底层容器的push_back()函数完成的。
    • push(T&&obj)：以移动对象的方式将对象压入栈顶。 这是通过调用底层容器的有右值引用参数的push_back()函数完成的。
    • pop()：弹出栈顶元素。
    • size()：返回栈中元素的个数。
• 队列：先进先出，后进后出
  • 普通队列
  • 循环队列