1.4 栈和队列. g: E! h* h |
1、栈及其基本运算& K: X, \: o4 _" r7 q! Y# Y) Z: Q
栈是限定在一端进行插入与删除运算的线性表。) h: P- v1 |6 q& M
在栈中,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。栈顶元素总是最后被插入的元素,栈底元素总是最先被插入的元素。即栈是按照“先进后出”或“后进先出”的原则组织数据的。
+ u/ N7 y% O0 n& d4 M 栈具有记忆作用。: L7 a2 `% G- v6 {) M, P
栈的基本运算:1)插入元素称为入栈运算;2)删除元素称为退栈运算;3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。
: k/ R8 z _3 w 栈的存储方式和线性表类似,也有两种,即顺序栈和链式栈。
5 I6 i7 O' t# `" T/ ^. E) b7 D 2、队列及其基本运算& J2 {3 c: [: A; _! U
队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。尾指针(Rear)指向队尾元素,头指针(front)指向排头元素的前一个位置(队头)。
$ L, [9 C; L4 g1 s3 P9 _3 n 队列是“先进先出”或“后进后出”的线性表。# Z9 B' F4 \5 |% ?8 X) t
队列运算包括:1)入队运算:从队尾插入一个元素;2)退队运算:从队头删除一个元素。; P c0 g* a' q3 b; g
循环队列及其运算:所谓循环队列,就是将队列存储空间的最后一个位置绕到第一个位置,形成逻辑上的环状空间,供队列循环使用。在循环队列中,用队尾指针rear指向队列中的队尾元素,用排头指针front指向排头元素的前一个位置,因此,从头指针front指向的后一个位置直到队尾指针rear指向的位置之间,所有的元素均为队列中的元素。3 O" ~6 X/ g+ Z+ L, p
*:循环队列中元素的个数=rear-front。 |