Java数据结构和算法之栈与队列

时间:2020-12-05 14:40:47

  二、栈与队列

  1、栈的定义

  栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表。

  (1)通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。

  (2)当表中没有元素时称为空栈。

   (3)栈为后进先出(Last In First Out)的线性表,简称为LIFO表。 栈的修改是按后进先出的原则进行。

  每次删除(退栈)的总是当前栈中"最新"的元素,即最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除。

   Java数据结构和算法之栈与队列

                图1

  【示例】元素是以a1,a2,…,an的顺序进栈,退栈的次序却是an,an-1,…, a1。

  2、栈的基本运算

  (1)InitStack(S)

    构造一个空栈S。

  (2)StackEmpty(S)

    判栈空。若S为空栈,则返回TRUE,否则返回FALSE。  

  (3)StackFull(S)

    判栈满。若S为满栈,则返回TRUE,否则返回FALSE。

    注意: 该运算只适用于栈的顺序存储结构。

  (4)Push(S,x)

    进栈。若栈S不满,则将元素x插入S的栈顶。

  (5)Pop(S)

    退栈。若栈S非空,则将S的栈顶元素删去,并返回该元素。

  (6)StackTop(S)

    取栈顶元素。若栈S非空,则返回栈顶元素,但不改变栈的状态。

  队列的定义及基本运算

  1、定义

  队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表

Java数据结构和算法之栈与队列

                  图2

  (1)允许删除的一端称为队头(Front)。

  (2)允许插入的一端称为队尾(Rear)。

  (3)当队列中没有元素时称为空队列。

  (4)队列亦称作先进先出(First In First Out)的线性表,简称为FIFO表。

   队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾(即不允许"加塞"),每次离开的成员总是队列头上的(不允许中途离队),即当前"最老的"成员离队。    【例】在队列中依次加入元素a1,a2,…,an之后,a1是队头元素,an是队尾元素。退出队列的次序只能是a1,a2,…,an。

  2、队列的基本逻辑运算

  (1)InitQueue(Q)

     置空队。构造一个空队列Q。

  (2)QueueEmpty(Q)

    判队空。若队列Q为空,则返回真值,否则返回假值。

  (3) QueueFull(Q)

    判队满。若队列Q为满,则返回真值,否则返回假值。

    注意:此操作只适用于队列的顺序存储结构。

  (4) EnQueue(Q,x)

    若队列Q非满,则将元素x插入Q的队尾。此操作简称入队。

  (5) DeQueue(Q)

     若队列Q非空,则删去Q的队头元素,并返回该元素。此操作简称出队。

  (6) QueueFront(Q)

    若队列Q非空,则返回队头元素,但不改变队列Q的状态。