欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构(栈和队列)

程序员文章站 2022-05-26 21:54:09
一、栈(Stack) 基本概念:只允许在一端进行插入或删除操作的线性表。 栈顶(Top):线性表语序进行插入和删除的那一端。 栈底(Bottom):固定的,不允许进行插入和删除的那一端。 空栈:不含任何元素的的空表。 栈的顺序存储结构:栈的顺序存储成为顺序栈,他是利用一组地址连续的存储单元存放在栈底 ......

一、栈(stack)

基本概念:只允许在一端进行插入或删除操作的线性表。

栈顶(top):线性表语序进行插入和删除的那一端。

栈底(bottom):固定的,不允许进行插入和删除的那一端。

空栈:不含任何元素的的空表。

栈的顺序存储结构:栈的顺序存储成为顺序栈,他是利用一组地址连续的存储单元存放在栈底刀栈顶的数据元素,同时附设一个指针(top)只是当前栈顶的位置。

  >>>共享栈:利用栈底位置相对不变的特性,可以让两个顺序栈共享一个一维数据空间,将两个栈的栈底分别设置在共享空间的两端,两个栈顶向共享空间的中间延伸。

栈的链式存储结构:采用链式存储的栈成为链栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况,通常采用单链表实现,并规定所有操作都是在单链表的表头的进行的。采用链式存储,便于节点的插入和删除,链栈的操作与链表类似。

二、队列(quene)

基本概念:队列简称队,也是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除,向队列中插入元素成为入队会进队,删除元素成为出队或离队。其操作的特性是先进先出(first in first out,fifo),故又成为先进先出的线性表。

队列的存储结构:队列的顺序实现是指分配一块的存储单元存放在队列中元素,并附设两个指针front和rear分别指示队头元素和队尾元素的位置。

  >>>队列的链式存储结构队列的链式表成为链式表示成为链队列,它实际上是一个同事带有队头指针和队尾指针的单链表,头指针指向队头节点,尾指针指向队尾节点。

双端队列:双端队列指允许两端都可以进行入队和出队操作的队列。包括输出受限的双端队列:允许在一端进行插入和删除;输入受限的双端队列:允许在一端进行插入和删除。