2.3 和队列的链式存储结构




2.3 和队列的链式存储结构

2.3 栈和队列的链式存储结构

  栈和队列的链式存储结构是线性链表的特殊形式,具有线性链表的一些基本特征,同时,又具有其本身的一些特殊性质。

2.3.1 栈的链式存储结构

  链栈就是使用链式存储结构实现的栈,一般情况下,可以直接使用线性链表来描述链栈。以链表尾作为栈底,以链表头作为栈顶,图2-4(a)是以不带头结点的线性链表描述的栈,图2-4(b)是带头结点的线性链表描述的栈。

  1.栈的链式存储结构
  用链式存储结构实现的栈称为链栈。通常用不带头结点的单链表表示一个栈,设置一个栈顶指针top。入栈、出栈都在top端进行。链栈是动态存储结构,元素个数动态变化,预先不需要指定。链栈的结点结构与单链表的结构相同,类型定义如下:
  
  因为栈中的主要运算是在栈顶插入和删除,将链表的头部做栈顶是最方便的,而且没有必要像单链表那样为了运算方便附加一个头结点。
  2.链栈的基本操作算法
  链栈的各个操作算法思想与顺序栈类似,不再赘述,下面仅给出算法描述。
  ① 置空栈。算法描述如下:
  
  ② 判栈空。算法描述如下:
  
  ③ 入栈。算法描述如下:
  
  ④ 出栈。算法描述如下:
  
  ⑤ 求栈长(元素个数)。算法描述如下:
  

2.3 和队列的链式存储结构

发表评论

Contact

北京考研中心大厦

Connect

Subscribe

最新考研资料,欢迎联系博主获取。