实验二 堆栈和队列基本操作的编程实现

【实验目的】

堆栈和队列基本操作的编程实现 要求：

堆栈和队列基本操作的编程实现（2学时，验证型），掌握堆栈和队列的建立、进栈、出栈、进队、出队等基本操作的编程实现，存储结构可以在顺序结构或链接结构中任选，也可以全部实现。也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】

验证性实验（学时数：2H）

【实验内容】

内容：

把堆栈和队列的顺序存储（环队）和链表存储的数据进队、出队等运算其中一部分进行程序实现。可以实验一的结果自己实现数据输入、数据显示的函数。

利用基本功能实现各类应用，如括号匹配、回文判断、事物排队模拟、数据逆序生成、多进制转换等。

【实验分析、说明过程】

分析： 进栈操作 先创建一个以x为值的新结点p，其data域值为x则进栈操作步骤如下： 将新结点p的指针域指向原栈顶S（执行语句p->next=S）。 将栈顶S指向新结点p（执行语句S=p）。 注：进栈操作的①与②语句执行顺序不能颠倒，否则原S指针其后的链表将丢失。 出栈操作 先将结点栈顶S数据域中的值赋给指针变量*x，则删除操作步骤如下： 结点p指针域指向原栈顶S（执行语句p=S）。 栈顶S指向其的下一个结点（执行语句S=S->next） 释放p结点空间（执行语句free(p)）。 队列分析：用链式存储结构实现的队列称为链队列，一个链队列需要一个队头指针和一个队尾指针才能唯一确定。队列中元素的结构和前面单链表中的结点的结

构一样。为了操作方便，在队头元素前附加一个头结点，队头指针就指向头结点。 【思考问题】

1. 栈的顺序存储和链表存储的差异？ 答：栈的顺序存储有‘后进先出’的特点，最后进栈的元素必须最先出来，进出栈是有序的，在对编某些需要按顺序操作的程序有很大的作用。 链表存储：通过链表的存储可以实现链表中任意位置的插入元素，删除任意元素，可以实现无序进出。 2. 还会有数据移动吗？为什么？ 答:栈的顺序存储不会有数据移动，移动的只是指向该数据地址的指针。 3. 栈的主要特点是什么？队列呢？ 答：栈拥有‘后进先出’的特点；队列拥有‘先进先出’的特点。 4. 栈的主要功能是什么？队列呢？

答：栈作为数据结构，其主要的用途是保存一批数据的逆序信息，从而产生逆序数据。 队列也是一种数据结构，其主要的用途按顺序保存一批数据，并且有序的队数据进行处理。 5. 为什么会有环状队列？ 答：为了解决“假溢出”的问题，把顺序结构的头尾进行相连，造出了一个所谓 的“环状队列”。 【实验小结】 (总结本次实验的重难点及心得、体会、收获)

本次实验主要是对堆栈和队列的顺序存储和链表存储的数据进队、出队等运算中一部分程序进行完善，程序的复杂度也是逐步增加，这让我们对栈和队列的认识也逐步加深。 在做本次实验中，自己亲自动手后，我栈和队列的知识又有了更深层次的了解，掌握了栈“后进先出”和队列“先进先出”的特点，学会了栈和队列的一些基本应用实例，实验的目的就是学会用栈和队列这两种数据结构进行编程，进行一些实际问题的处理，经过本次实验，我对学习也有了一些新的感悟，学了的知识要时常复习，经常巩固，不懂的知识要及时向老师或者同学请教，争取把这门课程学的更好！

【附录-实验代码】