北京邮电大学信息与通信工程学院

数据结构实验报告

实验名称： 实验一——栈和队列 学生姓名： 吴挺斌 班 级： 2017211116 班内序号： 21

学 号： 2017210473 日 期： 2018年04月22日

1． 实验要求

根据栈和队列的抽象数据类型的定义，按要求实现一个栈或一个队列。 要求：

1、 实现一个共享栈 2、 实现一个链栈 3、 实现一个循环队列 4、 实现一个链队列

编写测试main()函数测试线性表的正确性。

2. 程序分析

2.1 存储结构

1.共享栈存储结构：顺序结构。

第1页

北京邮电大学信息与通信工程学院

2.链栈存储结构：单链表。

3.队列存储结构：顺序结构。

4.链队列存储结构：单链表。

2.2 关键算法分析

①共享栈

关键算法：对栈进行操时要先明确是哪一个栈才能进行相应处理，同时用两个标识top_1

第2页

北京邮电大学信息与通信工程学院

和top_2分别指向两个栈顶。 代码详细分析：

template

void SeqStack::Push(int n, T x) {

if (n == 1) {

if (top_1 + 1 == top_2) throw\上溢\ top_1++;

date[top_1] = x; } else {

if (top_2 - 1 == top_1) throw\上溢\ top_2--;

date[top_2] = x; } }

在代码中我用了 int n,第一步先来判断入的是哪一个栈，然后根据输入进行分别处理。 时间复杂度：入栈出栈时间复杂度均为O（1）. ②链栈

关键算法：入栈和出栈的过程。 代码详细分析： template

void LinkStack::Push(T x) {

Node*p = new Node; p->date = x; p->next = top;

第3页