栈和队列

栈及其基本运算

栈的基本概念

栈（stack）是限定仅在一端进行插入和删除运算的线性表。

在栈中，允许插入与删除的一端称为栈顶，而不允许插入与删除的另一端称为栈底。

栈的入口和出口是同一个口。

top=bottom=0的时候，说明栈是空的。

栈的基本运算

入栈，退栈与读栈顶元素。

入栈运算

入栈运算是指在栈顶位置插入一个新元素。

有两个基本操作：

1. 将栈顶指针加1，top=top+1；
2. 然后将新元素插入栈顶指针指向的位置；

退栈运算

取出栈顶元素，并赋值给某个变量

两个基本操作：

1. 将栈顶元素赋值给变量
2. 然后栈顶指针减1，top=top-1

读栈顶元素

将栈顶元素赋值给一个指定的变量且栈顶指针不会改变。

总结

1. 栈是按照“先进后出”或先进先出的原则组织数据的线性表
2. 在栈的入栈和退栈的运算当中，栈底指针bottom维持不变。
3. 因为栈能保存数据，因此栈具有记忆作用
4. 栈内的元素个数计算：|TOP-BOTTOM|+1,其中BOTTOM>=1,如果栈当中TOP=BOTTOM=0说明栈是空的
5. 栈是线性结构，在计算机中担当着临时存储的功能。

队列及其基本运算

队列的基本概念

队列（queue）是限定仅在表的一端进行插入，而在表的另一端进行删除的线性表。

在队列中，允许插入的一端称为队尾，允许删除的一端称为队头。

队列又称为“先进先出”或"后进后出"的线性表。

在队列中，通常用指针front指向队头元素的前一个位置，用rear指向队尾最后一个元素。

循环队列

循环队列元素个数计算:

循环队列中元素的个数=rear（尾）- front（头）。

rear-front为正数时，便是循环队列的元素个数。

rear-front为负数时,需要再加上循环队列的容量.

rear-front为零时,说明要么队列是空的,要么是满的.