C语言学习(十二)栈和队列
栈
栈是一个特殊的线性表,只能在一端操作;
栈顶(top):允许操作 的一端;
栈底(bottom):不允许操作的一端
1.栈:是限定仅在表尾进行插入和删除操作的线性表;又称后进先出的线性表。LIFO结构。
栈顶top:允许插入和删除的一端;
栈底bottom:另外一端;
2. 空栈:不含任何数据元素的栈;top=-1; 3. 栈的操作:
进栈,压栈,入栈:栈的插入操作;
出栈,弹栈:栈的删除操作;
栈中有一个元素时,top=0;
注意:top为栈顶元素在数组中的位置,下标为0的一端作为栈底
链式栈
栈只是栈顶作为插入和删除 操作,那么该将链表的头部还是 尾部作为栈顶呢?
由于单链表有头节点,栈也 必须有栈顶,于是将两者合二为一 即将链表的头部作为栈顶,那么 链表的头节点就可以省去了。 那么当链栈为空时,top=NULL。
队列
a .队列是只允许在一端进行插入操作,在另一端进行删除操作的线性表;
先进先出的线性表,FIFO。
队头:允许删除的一端;
队尾:允许插入的一端;
c.循环队列:
1.队列顺序存储的不足:
(1)队列元素在队头出列,即下标为0的位置。也就意味着队列出列后所有元素向前移动一个位置,以保证队头不为空。然而队头不一定在下标为0的位置。
(2)避免出现只有一个元素时,队头和队尾的重合处理麻烦,引入front指向队头元素,rear指向队尾元素的下一个位置;front=rear时,队列不是还剩一个元素,而是空队列;
(3) 当front指向数组中第i个位置,rear已经指向数组最后,但是front前还有空位置可以继续存放。因此将队尾的元素继续存放在数组前 i 个位置。
2.循环队列定义: 把头尾相接的顺序存储结构称为循环队列; 但是当循环队列数组存满时,front = rear与空队列的条件冲突,以此我们保留一个元素空间作为满的条件,即队列满时还有一个空闲单元。
判断队列满的条件: (rear+1)%QueueSize==front;
当front = 0时,rear + 1 = SIZE + front 为满
当fornt !=0时,rear + 1 = front 为满
通用的计算队列长度公式为: (rear-front+QueueSize)%QueueSize;
当rear > front 时,length = rear -front
当rear < front 时,length = SIZE - front + rear
队列的链式存储其实就是线性表的单链表,只不过只能尾进头出。
为了方便操作,我们将队头指针指向链队列的头结点,尾指针指向终端结点。空队列时,两者都指向头结点。