堆栈和队列

堆栈和队列，栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶，表的另一端称为栈底。

堆栈和队列

• 栈
  • 定义
    • 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶，表的另一端称为栈底。栈顶的当前位置是动态的，栈顶的当前位置由一个被称为栈顶指针的位置指示器来指示。当栈中没有数据元素时称为空栈。栈的插入操作通常称为进栈或入栈(push)，栈的删除操作通常称为出栈或退栈(pop).
  • 特点
    • 后进先出(Last In First Out)，即后进栈的元素先出栈
  • 4要素
    • 栈空的条件: s->top==-1
    • 栈满的条件: s->top==MaxSize-1(data数组的最大下标)
    • 元素e的进栈操作:先将栈顶指针top增1，然后将元素e放在栈顶指针处
    • 出栈操作:先将栈顶指针top处的元素取出放在e中，然后将栈顶指针减1
  • 6中基本运算算法
    • 初始化栈initStack(&s)
    • 销毁栈DestroyStack(&s)
    • 判断栈是否为空StackEmpty(s)
    • 进栈Push(&s,e)
    • 出栈Pop(&s,&e)
    • 取栈顶元素GetTop(s,&e)
  • 栈的链式存储结构
    • 栈中数据元素的逻辑关系呈线性关系，所以栈可以像线性表一样采用链式存储结构。采用链式存储结构的栈称为链栈。 链栈的优点是不存在栈满上溢出的情况。
• 队列
  • 定义
    • 队列简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入操作，而在表的另一端进行删除操作。把进行插入的一端称为队尾(rear)，把进行删除的—端称为队头或队首(front)，向队列中插入新元素称为进队或入队(enqueue),新元素进队后就成为新的队尾元素;从队列中删除元素称为出队或离队(dequeue),元素出队后，其直接后继元素就成为队首元素。 队列称为先进先出表(First ln First Out,FIFO)
  • 顺序存储结构
    • 采用顺序存储结构的队列称为顺序队
    • 环形队列
      • 元素进队时队尾指针rear增1，元素出队时队首指针增1，当队满的条件成立时(rear==MaxSize-1)，表示此时队满了(上溢出)，不能再进队元素。队列中还可能有空位置，因为队满条件设置不合理导致队满条件成立而队列中仍然有空位置的情况称为假溢出。解决方法是把data数组的前端和后端连接起来，形成一个环形数组，即把存储队列元素的数组从逻辑上看成一个环，称为环形队列或循环队列。
  • 链式存储结构
    • 采用链式存储结构的队列称为链队。
    • 单链表链队:只允许在单链表的表头进行删除操作(出队)和在单链表的表尾进行插入操作(进队)，因此需要使用队头指针front和队尾指针rear两个指针。和链栈—样，链队中也不存在队满上溢出的情况
  • 双端队列
    • 所谓双端队列是指两端都可以进行进队和出队操作的队列。将队列的两端分别称为前端和后端，两端都可以进队和出队。其元素的逻辑关系仍然是线性的。