正月初九,开工大吉! 2024年,更上一层楼!
其实在List的继承关系中,除了ArrayList和LinkedList之外,还有另外一个集合类stack(栈),它继承自vector,线程安全,先进后出,随着Java并发编程的发展,它在很多应用场景下被逐渐替代,成为了Java的遗落之类。不过,stack在数据结构中仍有一席之地,因此,我们有必要也应该好好的学一下!
在开始学习栈之前,先来解决一下之前一个网友在评论区问的问题:
Collection和Collections有什么区别?
虽然这两个类都在java.util包下,虽然只有一字之差,但它们的差别还是挺大的! Collection 是JDK中集合层次结构中的最根本的接口。定义了集合类的基本方法。源码中的解释:
* The root interface in the <i>collection hierarchy</i>. A collection * represents a group of objects, known as its <i>elements</i>. Some * collections allow duplicate elements and others do not. Some are ordered * and others unordered. The JDK does not provide any <i>direct</i> * implementations of this interface: it provides implementations of more * specific subinterfaces like <tt>Set</tt> and <tt>List</tt>. This interface * is typically used to pass collections around and manipulate them where * maximum generality is desired.
* The root interface in the <i>collection hierarchy</i>. A collection
* represents a group of objects, known as its <i>elements</i>. Some
* collections allow duplicate elements and others do not. Some are ordered
* and others unordered. The JDK does not provide any <i>direct</i>
* implementations of this interface: it provides implementations of more
* specific subinterfaces like <tt>Set</tt> and <tt>List</tt>. This interface
* is typically used to pass collections around and manipulate them where
* maximum generality is desired.
Collections 是一个包装类。它包含有各种有关集合操作的静态多态方法,不能实例化,Collection 集合框架的工具类。源码中的解释:
* This class consists exclusively of static methods that operate on or return* collections. It contains polymorphic algorithms that operate on* collections, "wrappers", which return a new collection backed by a* specified collection, and a few other odds and ends.
* This class consists exclusively of static methods that operate on or return
* collections. It contains polymorphic algorithms that operate on
* collections, "wrappers", which return a new collection backed by a
* specified collection, and a few other odds and ends.
栈(stack)是一种先进后出(Last In First Out,LIFO)的数据结构,类比于现实生活中的子弹上膛、泡泡圈。栈具有两个基本操作:入栈(push)和出栈(pop)。入栈表示将元素放入栈顶,而出栈表示从栈顶取出元素。
动图图解-入栈(push)
动图图解-出栈(pop)
在Java的工具包中其实帮我们封装好了一个类,java.util.Stack,它所提供的方法并不多,我们通过一个小示例感受一下。
【代码示例1】
Stack<String> stacks = new Stack<>();//push方法入栈 stacks.push("开"); stacks.push("工"); stacks.push("大"); stacks.push("吉"); stacks.push("!"); System.out.println(stacks); //pop栈顶元素出栈 String pop = stacks.pop(); System.out.println(pop); //查看栈顶元素 String peek = stacks.peek(); System.out.println(peek); //判断堆栈是否为空 boolean empty = stacks.empty(); System.out.println(empty); //查看元素在堆栈中的位置 int index = stacks.search("开"); System.out.println(index);
Stack<String> stacks = new Stack<>();
//push方法入栈
stacks.push("开");
stacks.push("工");
stacks.push("大");
stacks.push("吉");
stacks.push("!");
System.out.println(stacks);
//pop栈顶元素出栈
String pop = stacks.pop();
System.out.println(pop);
//查看栈顶元素
String peek = stacks.peek();
System.out.println(peek);
//判断堆栈是否为空
boolean empty = stacks.empty();
System.out.println(empty);
//查看元素在堆栈中的位置
int index = stacks.search("开");
System.out.println(index);
输出:
[开, 工, 大, 吉, !]!吉false4
[开, 工, 大, 吉, !]
!
吉
false
4
通过上面的代码示例我们了解了一个栈所具备的功能特点,根据它的特点,我们尝试一下手写一个栈! 首先,准备一个数组用来存储元素,可以定义为Object,这样支持多数据类型,我们这里直接选用int类型的好嘞。 自定义栈-源码:
自定义栈-源码:
/** * @ClassName Stack * @Description 手写一个int类型的堆栈 * @Author hzm * @Date 2024/2/18 14:21 * @Version 1.0 */public class Stack { private int arr[]; private int top; private int capacity; /** * 提供一个有参构造,初始化栈 * @param size */ public Stack(int size) { this.arr = new int[size]; this.top = -1; this.capacity = size; } /** * 入栈 * @param p */ public void push(int p) { if (isFull()) { System.out.println("堆栈空间溢出\n程序终止\n"); System.exit(1); } System.out.println("入栈:" + p); arr[++top] = p; } /** * 出栈 * @return */ public int pop() { if (isEmpty()) { System.out.println("空栈,不可POP"); System.exit(1); } return arr[top--]; } /** * 判断栈是否已满 * @return */ public Boolean isFull() { return top == capacity - 1; } /** * 判断栈是否为空 * @return */ public Boolean isEmpty() { return top == -1; } /** * 遍历栈内元素 */ public void printStack() { for (int i = 0; i <= top; i++) { System.out.println(arr[i]); } } /** * 返回栈的大小 * @return */ public int size() { return top + 1; } /** * 查看栈顶元素 * @return */ public void peek(){ System.out.println("栈顶元素:" + arr[top]); }}
/**
* @ClassName Stack
* @Description 手写一个int类型的堆栈
* @Author hzm
* @Date 2024/2/18 14:21
* @Version 1.0
*/
public class Stack {
private int arr[];
private int top;
private int capacity;
* 提供一个有参构造,初始化栈
* @param size
public Stack(int size) {
this.arr = new int[size];
this.top = -1;
this.capacity = size;
}
* 入栈
* @param p
public void push(int p) {
if (isFull()) {
System.out.println("堆栈空间溢出\n程序终止\n");
System.exit(1);
System.out.println("入栈:" + p);
arr[++top] = p;
* 出栈
* @return
public int pop() {
if (isEmpty()) {
System.out.println("空栈,不可POP");
return arr[top--];
* 判断栈是否已满
public Boolean isFull() {
return top == capacity - 1;
* 判断栈是否为空
public Boolean isEmpty() {
return top == -1;
* 遍历栈内元素
public void printStack() {
for (int i = 0; i <= top; i++) {
System.out.println(arr[i]);
* 返回栈的大小
public int size() {
return top + 1;
* 查看栈顶元素
public void peek(){
System.out.println("栈顶元素:" + arr[top]);
测试类中调用手写的这个stack:
public class Test { public static void main(String[] args) { Stack stack = new Stack(5); //入栈 stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); //出栈 int pop = stack.pop(); System.out.println("出栈:"+ pop); //查看栈的大小 int size = stack.size(); System.out.println("栈容量:" + size); //查看栈顶元素 stack.peek(); //打印栈内元素 stack.printStack(); }}
public class Test {
public static void main(String[] args) {
Stack stack = new Stack(5);
//入栈
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
//出栈
int pop = stack.pop();
System.out.println("出栈:"+ pop);
//查看栈的大小
int size = stack.size();
System.out.println("栈容量:" + size);
stack.peek();
//打印栈内元素
stack.printStack();
入栈:1入栈:2入栈:3入栈:4入栈:5出栈:5栈容量:4栈顶元素:41234
入栈:1
入栈:2
入栈:3
入栈:4
入栈:5
出栈:5
栈容量:4
栈顶元素:4
1
2
3
好了,今天的栈内容就写到这里吧,大家私下里可以找找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