经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » Java相关 » Java » 查看文章
Java集合篇之逐渐被遗忘的Stack,手写一个栈你会吗?
来源:cnblogs  作者:JavaBuild  时间:2024/2/19 9:19:28  对本文有异议

正月初九,开工大吉!
2024年,更上一层楼!

写在开头

其实在List的继承关系中,除了ArrayList和LinkedList之外,还有另外一个集合类stack(栈),它继承自vector,线程安全,先进后出,随着Java并发编程的发展,它在很多应用场景下被逐渐替代,成为了Java的遗落之类。不过,stack在数据结构中仍有一席之地,因此,我们有必要也应该好好的学一下!

Collection和Collections的区别?

在开始学习栈之前,先来解决一下之前一个网友在评论区问的问题:

Collection和Collections有什么区别?

虽然这两个类都在java.util包下,虽然只有一字之差,但它们的差别还是挺大的!
Collection 是JDK中集合层次结构中的最根本的接口。定义了集合类的基本方法。源码中的解释:

  1. * The root interface in the <i>collection hierarchy</i>. A collection
  2. * represents a group of objects, known as its <i>elements</i>. Some
  3. * collections allow duplicate elements and others do not. Some are ordered
  4. * and others unordered. The JDK does not provide any <i>direct</i>
  5. * implementations of this interface: it provides implementations of more
  6. * specific subinterfaces like <tt>Set</tt> and <tt>List</tt>. This interface
  7. * is typically used to pass collections around and manipulate them where
  8. * maximum generality is desired.

Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法,不能实例化,Collection 集合框架的工具类。源码中的解释:

  1. * This class consists exclusively of static methods that operate on or return
  2. * collections. It contains polymorphic algorithms that operate on
  3. * collections, "wrappers", which return a new collection backed by a
  4. * specified collection, and a few other odds and ends.

stack(栈)

栈(stack)是一种先进后出(Last In First Out,LIFO)的数据结构,类比于现实生活中的子弹上膛、泡泡圈。栈具有两个基本操作:入栈(push)和出栈(pop)。入栈表示将元素放入栈顶,而出栈表示从栈顶取出元素。

动图图解-入栈(push)

动图图解-出栈(pop)

在Java的工具包中其实帮我们封装好了一个类,java.util.Stack,它所提供的方法并不多,我们通过一个小示例感受一下。

【代码示例1】

  1. Stack<String> stacks = new Stack<>();
  2. //push方法入栈
  3. stacks.push("开");
  4. stacks.push("工");
  5. stacks.push("大");
  6. stacks.push("吉");
  7. stacks.push("!");
  8. System.out.println(stacks);
  9. //pop栈顶元素出栈
  10. String pop = stacks.pop();
  11. System.out.println(pop);
  12. //查看栈顶元素
  13. String peek = stacks.peek();
  14. System.out.println(peek);
  15. //判断堆栈是否为空
  16. boolean empty = stacks.empty();
  17. System.out.println(empty);
  18. //查看元素在堆栈中的位置
  19. int index = stacks.search("开");
  20. System.out.println(index);

输出:

  1. [开, 工, 大, 吉, !]
  2. false
  3. 4

手写一个stack(堆栈)

通过上面的代码示例我们了解了一个栈所具备的功能特点,根据它的特点,我们尝试一下手写一个栈!
首先,准备一个数组用来存储元素,可以定义为Object,这样支持多数据类型,我们这里直接选用int类型的好嘞。
自定义栈-源码:

  1. /**
  2. * @ClassName Stack
  3. * @Description 手写一个int类型的堆栈
  4. * @Author hzm
  5. * @Date 2024/2/18 14:21
  6. * @Version 1.0
  7. */
  8. public class Stack {
  9. private int arr[];
  10. private int top;
  11. private int capacity;
  12. /**
  13. * 提供一个有参构造,初始化栈
  14. * @param size
  15. */
  16. public Stack(int size) {
  17. this.arr = new int[size];
  18. this.top = -1;
  19. this.capacity = size;
  20. }
  21. /**
  22. * 入栈
  23. * @param p
  24. */
  25. public void push(int p) {
  26. if (isFull()) {
  27. System.out.println("堆栈空间溢出\n程序终止\n");
  28. System.exit(1);
  29. }
  30. System.out.println("入栈:" + p);
  31. arr[++top] = p;
  32. }
  33. /**
  34. * 出栈
  35. * @return
  36. */
  37. public int pop() {
  38. if (isEmpty()) {
  39. System.out.println("空栈,不可POP");
  40. System.exit(1);
  41. }
  42. return arr[top--];
  43. }
  44. /**
  45. * 判断栈是否已满
  46. * @return
  47. */
  48. public Boolean isFull() {
  49. return top == capacity - 1;
  50. }
  51. /**
  52. * 判断栈是否为空
  53. * @return
  54. */
  55. public Boolean isEmpty() {
  56. return top == -1;
  57. }
  58. /**
  59. * 遍历栈内元素
  60. */
  61. public void printStack() {
  62. for (int i = 0; i <= top; i++) {
  63. System.out.println(arr[i]);
  64. }
  65. }
  66. /**
  67. * 返回栈的大小
  68. * @return
  69. */
  70. public int size() {
  71. return top + 1;
  72. }
  73. /**
  74. * 查看栈顶元素
  75. * @return
  76. */
  77. public void peek(){
  78. System.out.println("栈顶元素:" + arr[top]);
  79. }
  80. }

测试类中调用手写的这个stack:

  1. public class Test {
  2. public static void main(String[] args) {
  3. Stack stack = new Stack(5);
  4. //入栈
  5. stack.push(1);
  6. stack.push(2);
  7. stack.push(3);
  8. stack.push(4);
  9. stack.push(5);
  10. //出栈
  11. int pop = stack.pop();
  12. System.out.println("出栈:"+ pop);
  13. //查看栈的大小
  14. int size = stack.size();
  15. System.out.println("栈容量:" + size);
  16. //查看栈顶元素
  17. stack.peek();
  18. //打印栈内元素
  19. stack.printStack();
  20. }
  21. }

输出:

  1. 入栈:1
  2. 入栈:2
  3. 入栈:3
  4. 入栈:4
  5. 入栈:5
  6. 出栈:5
  7. 栈容量:4
  8. 栈顶元素:4
  9. 1
  10. 2
  11. 3
  12. 4

好了,今天的栈内容就写到这里吧,大家私下里可以找找leetcode上关于栈的算法题做做,深刻感受一下哈!

结尾彩蛋

如果本篇博客对您有一定的帮助,大家记得留言+点赞+收藏呀。原创不易,转载请联系Build哥!

原文链接:https://www.cnblogs.com/JavaBuild/p/18020340

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号