链表、栈与队列

链表、栈和队列是最基础的数据结构,理解这些数据结构对解决算法帮助很大。

链表

1
2
3
4
5
6
7
8
9
10
11
public class Node {
int value;
Node next;

public Node(int value){
this.value = value;
}

public Node() {
}
}

操作一个链表只需要知道它的头指针就可以做任何操作了

  • 添加数据到链表中

    • 遍历找到尾节点,插入即可(只要while(temp.next != null),退出循环就会找到尾节点)
  • 遍历链表

    • 从首节点(有效节点)开始,只要不为null,就输出
  • 给定位置插入节点到链表中

    • 将原本由上一个节点的指向交由插入的节点来指向
    • 上一个节点指针域指向想要插入的节点
    • 首先判断该位置是否有效(在链表长度的范围内)
    • 找到想要插入位置的上一个节点

  • 获取链表的长度

    • 每访问一次节点,变量++操作即可
  • 删除给定位置的节点

    • 将原本由上一个节点的指向后面一个节点
    • 首先判断该位置是否有效(在链表长度的范围内)
    • 找到想要插入位置的上一个节点

  • 对链表进行排序

    • 使用冒泡算法对其进行排序
  • 找到链表中倒数第k个节点

    • 设置两个指针p1、p2,让p2比p1快k个节点,同时向后遍历,当p2为空,则p1为倒数第k个节点
  • 删除链表重复数据

    • 操作跟冒泡排序差不多,只要它相等,就能删除了
  • 查询链表的中间节点

    • 这个算法也挺有趣的:一个每次走1步,一个每次走两步,走两步的遍历完,然后走一步的指针,那就是中间节点
  • 递归从尾到头输出单链表

    • 只要下面还有数据,那就往下找,递归是从最后往前翻
  • 反转链表

    • 有递归和非递归两种方式。

栈的特性

数据结构的栈长的是这个样子:

其实非常好理解,我们将栈可以看成一个箱子

  • 往箱子里面放东西叫做入栈
  • 往箱子里面取东西叫做出栈
  • 箱子的底部叫做栈底
  • 箱子的顶部叫做栈顶

说到栈的特性,肯定会有一句经典的言语来概括:先进后出(LIFO, Last In First Out)

  • 往箱子里边放苹果,箱子底部的苹果想要拿出来,得先把箱子顶部的苹果取走才行

集合中的栈

Stack集合类是继承Vector类的 主要有以下成员方法:

Stack集合成员方法

队列

队列特性

数据结构的队列长的是这个样子:

其实队列非常好理解,我们将队列可以看成小朋友排队

  • 队尾的小朋友到指定的地点了–>出队
  • 有新的小朋友加入了–>入队

相对于栈而言,队列的特性是:先进先出

  • 先排队的小朋友肯定能先打到饭!

队列也分成两种:

  • 静态队列(数组实现)
  • 动态队列(链表实现)

这次我就使用数组来实现静态队列了。值得注意的是:往往实现静态队列,我们都是做成循环队列

做成循环队列的好处是不浪费内存资源

集合中的队列

集合中的队列分为单向队列和双向队列。实现的是接口形式:

单向队列集合的方法

单向队列

双向队列集合的方法:

总结

数据结构的栈和队列的应用非常非常的多,这里也只是最简单的入门,理解起来也不困难。

  • 栈:先进后出
  • 队列:先进先出

  算法

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×