徐州弘智学历培训
您现在的位置: 弘智主页 > 计算机等级考试 > 二级VB >

2016年计算机二级公共基础知识学习教程:数据结构与算法

时间:2015-05-06 来源:弘智教育 点击:
(四)栈和队列

  1.栈及其基本运算

  1)栈

  栈是一种特殊的线性表,它是限定在一端进行插入和删除的线性表。它的插入和删除只能在表的一端进行,而另一端是封闭的,不允许进行插入和删除操作。

  在栈中,允许插入和删除操作一端称为栈顶,不允许插入和删除操作的一端则称为栈底。栈顶的元素总是最后被插入的元素,也是最先被删除的元素。它遵循的原则是:先进后出或后进先出。

  堆栈指针总是指向栈顶元素的。

  2)栈的顺序存储及其运算

  在栈的顺序存储空间S(1:m)中,S(bottom)通常为栈底元素,S(top)为栈顶元素。Top=0表示栈空;top=m表示栈满。

  1)入栈运算

  即在栈的顶部插入一个新元素。操作方式是:将栈顶指针加1,再将元素插入至指针所指的位置。

  2)退栈运算

  退栈运算即将栈顶元素取出并赋给一个指定的变量。操作方式是:先将栈顶元素赋给指定的变量,再将栈顶指针减1。

  3)读栈顶元素

  将栈顶元素赋给某一指定变量,但栈顶指针不变。

  2.队列及其基本运算

  1)队列

  队列即是允许在一端进行插入,而在另一端进行删除的线性表。允许插入的一端称为队尾,通常用一个尾指针指向队尾;允许删除的一端称为队首,通常用一个队首指针指向排队元素的前一个位置。

  队列遵循的规则是:先进先出或后进后出

  2)循环队列及其运算

  队列的顺序存储结构一般采用循环队列的形式。

  循环队列,即是次队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。

  在循环队列中,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置,因此,从排头指针front指向的后一个位置到队尾指针rear指向的位置之间所有的元素均为队列中的元素。

  循环队列的初始状态为空,即rear=front=m。这里m即为队列的存储空间。

  循环队列的基本运算:入队运算和退队运算。

  入队运算:每进行一次入队运算,队尾指针加1。当队尾指针rear=m+1时,即表示队列空间的尾部已经放置了元素,则下一个元素应该旋转到队列空间的首部,即rear=1

  退队运算:每退队一个元素,排头指针加1。当排头指针front=m+1时,即排头指针指向队列空间的尾部,退队后,排头指针指向队列空间的开始,即front=1。

  在队列操作时,循环队列满时,front=rear,队列空时,也有rear=front,即在队列空或满时,排头指针和队尾指针均指向同一个位置。要判断队列空或满时,还应增加一个标志,s值的定义:

  判断队列空与队列满的条件下:

  队列空的条件:s=0

  队列满的条件:s=1、front=rear

  (1)入队运算

  即在队尾加入一个新元素。这个运算有两个基本操作:首先,将队尾指针加1,即rear=rear+1,当rear=m+1时,置rear=1,然后,将新元素插入到队尾指针指向的位置。

  当循环队列非空(s=1),且front=rear时,队列满,不能进行入队操作。此情况称“上溢”。

  (2)退队操作

  即将队首的元素赋给一个指定的变量。该运算也有两个基本操作:首先,将排头指针加1,即front=front+1,当front=m+1时,置front=1,然后,将排头指针指向的元素赋给指定的变量。

  当循环队列为空(s=0)时,不能进行退队运算。此种情况称为“下溢”。

弘智介绍 | 培训课程 | 徐州网络培训