【数据结构】栈与队列（三）-阿里云开发者社区

【数据结构】栈与队列（三）

2022-09-22 227

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 栈与队列

3.8 链队列

3.8.1 定义

链队列：使用链式存储的队列，使用不带头结点head的单链表。

front结点：队首元素
rear结点：队尾元素

3.8.2 链队列类

publicclassLinkQueue {
privateNodefront;     //队首（出队/删除）privateNoderear;      //队尾（入队/插入）}

3.8.3 算法：链队列入队【重点】

分析：

非空

publicvoidoffer(Objectx) {
Nodep=newNode(x);
if(front==null) {     //空front=rear=p;
//front = p;//rear = p;    } else {                //非空rear.next=p;      //1.尾指针的指针域指向新结点rear=p;           //2.尾指针指向队尾    }
}

3.8.4 算法：链队列出队【重点】

分析：空队列、一个元素、很多元素

很多元素

publicObjectpoll() {
if(front!=null) {     //非空Nodep=front;             //记录队首元素front=front.next;         //队首移动到下一个if(p==rear) {                 //只有一个元素时，队首和队尾相同rear=null;                //队首已经是null，队尾也应该是null        }
returnp.data;              //返回之前队首元素的数据    } else {                //空returnnull;
    }
}

3.9 优先级队列

3.9.1 定义

优先级队列：就是一种带优先级的队列，也就是内部需要根据关键字的值进行排序的队列。

与普通队列基本操作一致，队首删除。
区别：进行==插入==操作时，不在是队尾，对队伍中找到合适的位置。

优先级队列也可以使用两种存取方式，但常用链式存储。

默认队列

3.9.2 优先级队列相关类

数据对象：数据元素的值、结点的优先级/*{ elem: a, priority: 1}*/publicclassPriorityData {
publicObjectelem;             //数据元素的值publicintpriority;            //结点的优先级}
队列对象publicclassPriorityQueue {
privateNodefront;     //队首privateNoderear;      //队尾}
数据之间关系node.next//指针域node.data//数据域，存放的数据类型是 PriorityData

3.9.3 算法：优先级队列入队

需求：数字越==小==优先级越高。
分析：
前提：从队首进入，依次进行比较
情况1：队首插入（p如果指向队首front，表示新结点优先级的数字小）

publicvoidoffer(PriorityDatax) {
Nodes=newNode(x);               //构建新结点// 如果空if(front==null) {     //空front=rear=s;
    } else {                //非空// 1) 移动：按照优先级进行移动，优先级大就需要继续移动Nodep=front;     //用于记录前驱（之前的）Nodeq=front;     //用于记录下一个while( q!=null&& (x.priority>=q.data.priority )) {
p=q;          //记录前驱q=p.next;
        }
// 2) 插入if(q==front) {          // 2.1 队首s.next=front;         //新结点s指向队首frontfront=s;              //队首指针，指向队列的开始        } elseif (q==null) { // 2.2 队尾rear.next=s;          //队尾指针域next,指向新结点rear=s;               //队尾指针，指向队尾        } else {                // 2.3 中间p.next=s;
s.next=q;
        }
    }
}

3.10 递归

3.10.1 定义

程序调用自身的编程技巧称为递归（ recursion），由两部分组成：递推、回归。

递推：方法依次调用，没有返回。
回归：程序准备依次返回。

3.10.2 算法：1-n和

packagerecursion;
/*** @author 桐叔* @email liangtong@itcast.cn*/publicclassTestSum {
publicstaticvoidmain(String[] args) {
System.out.println(sum(10));
    }
/*** 求1-n的和* @param n* @return*/privatestaticintsum(intn) {
if(n==1) {
return1;
        }
returnn+sum(n-1);
    }
}

3.10.3 算法：n!

packagerecursion;
/** 测试阶乘：*      n! = 1 * 2 * 3 * 4 * .... * n* @author 桐叔* @email liangtong@itcast.cn*/publicclassTestFactorial {
publicstaticvoidmain(String[] args) {
System.out.println(factorial(4));
    }
privatestaticintfactorial(intn) {
if(n==1) {
return1;
        }
returnn*factorial(n-1);
    }
}

3.10.4 算法：斐波那契数列

定义

0、1、1、2、3、5、8、13、21、34 .... n

固定值

f(0) = 0

f(1) = 1

后面的每一项都是前两项的和

f(2) = f(0) + f(1)

f(n) = f(n-1) + f(n-2)

算法

packagerecursion;
/*** @author 桐叔* @email liangtong@itcast.cn*/publicclassTestFibonacci {
publicstaticvoidmain(String[] args) {
// 斐波那契数列for(inti=0 ; i<=10 ; i++) {
System.out.print(fibonacci(i) +"、");
        }
    }
/*** 计算斐波那契数列的第n项* f(0) = 0* f(1) = 1* ...* f(n) = f(n-1) + f(n-2)* @param n* @return*/privatestaticintfibonacci(intn) {
if(n==0) {
return0;
        }
if(n==1) {
return1;
        }
returnfibonacci(n-1) +fibonacci(n-2);
    }
}