栈与队列

栈的定义:栈是一种线性表,它只能在一端进行插入或删除操作(操作受限)的线性表。
栈顶(top):允许进行插入或删除的那一端。
栈底(bottom):不允许进入插入或删除的那一端。
空栈:不包含任何元素的栈。
栈是“先进后出”或者“后进先出”。

栈的存储结构可以分为顺序栈和链栈,
顺序栈:利用一组地址连续的存储单元存放自栈底到栈顶的数据元素,同时附属一个指针指向栈顶。
栈空的条件:顺序栈的数组下标从0开始的话,满足栈空的条件是top=-1。
栈满的条件:顺序栈的数组下标从0开始的话,满足栈满的条件是top=maxsize-1。


顺序栈的计算方法:bottom>=1,栈内元素的个数|top-bottom|+1。如果bottom=top=0,表示栈空。

顺序栈的两种非法情况
上溢:顺序栈满栈时,再进行入栈操作,会发生上溢。
下溢:顺序栈空栈时,再进行出(退)栈操作,会发生下溢。

例题,设栈的存储空间为S(1:50),初试状态为top=51,现经过一系列正常的入栈与退栈之后,top=20,则栈中的元素个数为(31)。
Top=51,说明刚开始是空栈的,然后这个入栈的顺序跟平常的不一样,这个是从右到左的,
Bottom>=1,那么栈的元素个数为|top-bottom|+1
链栈:采用链式存储的栈称为链栈,链栈的优点在于多个栈共享存储空间和提高效率,并且链栈不存在栈满上溢的情况。(永远填不满) 
队列:队列也是一种线性表,只允许在表的一端进行插入操作,允许在另外一端进行删除操作。
队头:删除元素的那一端,用头指针(front)指向队头元素的前一个位置。
队尾:插入元素的那一端,用尾指针(rear)指向队尾元素。
空队:队列中没有元素。

队列是先进先出的。

队列按存储结构可分为顺序队列(循环队列)和链式队列(单链表)
循环队列的运算,元素个数=rear(尾指针)-front(头指针)
A)	如果rear-front>0,就是循环队列元素的个数
B)	如果rear-front<0,还需要加上队列的容量
C)	如果rear-front=0,可能队空或满


链式存储,队列的链式存储称为链式队列,它实际上是同一个带有队头指针和队尾指针的单链表,头指针指向队头结点,尾指针指向尾结点,即单链表的最后一个结点,
链式表队空的条件rear=front=null;
优点:单链表适合数据元素变动比较大的情况,不存在队列满或溢出的问题。
赞赏

微信赞赏支付宝赞赏

发表评论