2011年计算机二级公共基础知识考点知识4

　　1.4.1栈及其基本运算 (P16—P18)

　　1.什么是栈

　　栈是限定在一端进行插入与删除的另一端称为栈底。即栈是按照“先进后出”(FILO)或“后进先出”(LIFO)的原则组织数据的，因此，栈也被称为“先进后出”表或“后进先出”表。由此可以看出，栈具有记忆作用。

　　2.栈的顺序存储及其运算(采用顺序存储结构的栈称为顺序栈)

　　栈的基本运算有三种：入栈、退栈与读栈顶元素。

　　(1) 入栈运算(2)退栈运算(3)读栈顶元素

　　1.4.2队列及其基本运算 (P18—P20)

　　1.什么是队列

　　队列(queue)是指允许在一端进行插入、而在另一端进行删除的线性表。允许插入的一端称为队尾，通常用一个称为尾指针(rear)的指针指向队尾元素，一端称为排头(也称为队头)通常也用一个排头指针(front)指向排头元素的前一个位置。

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

　　3. 循环队列及其运算

　　在实际应用中，队列的顺序存储结构一般采用循环队列的形式。

　　所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

　　(1) 入队运算

　　(2) 退队运算