3.堆栈和队列.ppt

while(QueueNotEmpty(myQueue)==1 StackNotEmpty(myStack)==1) { QueueDelete(myQueue,x); StackPop(myStack,y); if(x!=y) { printf(“不是回文!”); return 0; } } printf(是回文!); return 1; } StackInitiate(qstype *s) { s-top=-1; } int StackPush (qstype *s,elemtype x) { if(s-top=MAXNUM-1) return 0; else { s-stack[++(s-top)]=x; return 1; } } int StackPop (qstype *s,elemtype *y) { *y=s-stack[(s-top)]; (s-top) --; return 1; } int StackNotEmpty (qstype *s) { if(s-top0) return 0; return 1; } QueueInitiate(qqtype *q) { q-front=0; q-rear= 0; } int QueueAppend (qqtype *q,elemtype x) { if(q-rear=MAXNUM-1) return 0; q-queue[ (q-rear) ++]=x; return 1; } int QueueDelete (qqtype *q,elemtype *x) { *x=q-queue[ (q-front) ++]; return 1; } int QueueNotEmpty (qqtype *q) { if(q-rear==q-front) return 0; return 1; } 测试结果： abcdcba 是回文! abcdefg 不是回文! 线性表、栈与队列的异同点 相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。 不同点： ① 运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。 ② 用途不同，线性表比较通用；堆栈用于元素的保存次序与使用顺序相反的情况；队列用于元素的保存次序与使用顺序相同的情况。 小 结 理解：队列，队头，队尾，顺序队列，链式队列。 掌握：初始化，入队，出队的算法（顺序循环队列，链式队列），队空、队满的判断。 应用：回文判断，医院就诊等。 设计一个不带头节点的，数据元素为整型的，单链表，并进行相关操作，程序思路如下： void main() { 1、单链表初始化; 2、接受命令，按照命令格式执行相关操作 命令格式如下： 命令1的格式： 1 x 这里1是命令名称，x是一个数字，表示按照头插法来插入数据x；该命令执行完毕之后 ，按照如下格式显示链表中的所有数据： x1,x2,x3,x4,…..,这里x1是头指针指向的第一个元素。 命令2的格式： 2 x 这里2是命令名称，x是一个数字，表示按照尾插法来插入数据x；该命令执行完毕之后 ，按照如下格式显示链表中的所有数据： x1,x2,x3,x4,…..,这里x1是头指针指向的第一个元素。 命令3的格式： 3 i 这里3是命令名称，i是一个数字，表示要删除的数据位置，i从0开始；该命令执行完毕之后 ，按照如下格式显示链表中的所有数据： x1,x2,x3,x4,…..,这里x1是头指针指向的第一个元素。 } * 由上述求解过程可以看出，在计算过程中是从低位到高位顺序产生八进制数的各个数位，而显示时按照我们的习惯是从高位在前，低位在后，即按从高位到低位的顺序输出, 即后计算出的（高）位数先输出，具有后进先出的特点，因此可将计算过程中得到的八进制数顺序进栈，出栈序列打印输出的就是对应的八进制数。