May 31, 2021 Article blog
This article comes from the public number: Java Chinese Community Author: Lei ge
With the increasingly fierce competition in the software development industry, the difficulty of interviewing is also gradually increasing, because enterprises from a large number of interviewees to choose the best people, can only improve the difficulty of the interview, and algorithms and data structure is more brain-burning hard core skills, naturally has become the preferred subject of the interview. And over time, the frequency and proportion of algorithms and data structures will continue to increase, so in order to adapt to the trend of the times, we also have to make some adjustments, so in some later articles, I will update some articles on algorithms and data structure, I hope you can like.
PS: Of course, with the popularity of intelligent systems (today's headlines and shakes), algorithms and data structures are being used more and more in enterprises, so learning algorithms and data structures is also urgent.
Stack, also known as a stack, is a linear table that inserts and deletes data at the same end.
Stacks are one of the most basic and common data structures, and their data structure and operation flow are shown in the following diagram:
Wherein, one end that allows insertion and deletion is called top, the other end is called bottom, the bottom of the stack is fixed, and the top of the stack floats.
When an element in a stack is zero, the stack is called an empty stack. W hen you add data, it is ofy called in-stack or in-stack (Push), and deleting data is called making or exiting (Pop). The stack is a linear table of last In Out, LIFO.
Before we go through the hand-wringing algorithm, let's look at two important concepts in the data structure: physical and logical.
When it comes to the terms "physical" and "logical," we can think of tombstones and physical deletions in the database.
The so-called physical deletion refers to the process of actually removing data from the physical structure by deleting the command, while tombstone refers to changing the data to a "deleted" state by modifying the command, not the real deletion of data.
The logical structure and physical structure here are similar to the above concepts, the so-called physical structure refers to the data can be stored in physical space, such as arrays and lists are physical data structure, while the logical structure is used to describe the logical relationship between data, such as the stack to be described in this article belongs to the logical structure.
Maybe some people see it here, it doesn't matter, I'll give you an example here.
If people are used to represent physical structures and logical structures, then the real flesh and blood of people belong to the physical structure, and people's thoughts and beliefs belong to the logical structure.
From the above, we know that the stack belongs to the logical structure, so it can be implemented in many ways, such as array implementation or linked list implementation. So let's start with an array, and the main methods of stacking are:
So let's define its structure first:
public class MyStack {
private Object[] value = null; // 栈存储容器
private int top = -1; // 栈顶(的指针)
private int maxSize = 0; // 栈容量
// 构造函数(初始化默认容量)
MyStack() {
this.maxSize = 10;
}
// 有参构造函数
MyStack(int initSize) throws Exception {
if (initSize Hello
从上述代码可以看出,我们添加栈的顺序是 `Hello`、`Java` 而输出的顺序是 `Java`、 `Hello` 符合栈的定义(后进先出)。
## 自定义栈II:链表实现
除了数组之外,我们可以还可使用链表来实现栈结构,它的实现稍微复杂一些,我们先来看链表本身的数据结构:
![链表的数据结构](https://atts.w3cschool.cn/attachments/image/20200923/1600831705876009.png "链表的数据结构")
使用链表实现栈的流程如下:
![链表实现栈的流程](https://atts.w3cschool.cn/attachments/image/20200923/1600831725907957.gif "链表实现栈的流程")
也就是说,入栈时我们将数据存储在链表的头部,出栈时我们从头部进行移除,并将栈顶指针指向原头部元素的下一个元素,实现代码如下。
我们先来定义一个链表节点:
public class Node { Object value; D ata node next per node; The next node
public Node(Object value) { this(value, null); }
/**
Next we use the list to implement a complete stack:
public class StackByLinked {
private Node top = null; // 栈顶数据
private int maxSize = 0; // 栈最大容量
private int leng = 0; // 栈实际容量
public StackByLinked(int initSize) throws Exception {
if (initSize = maxSize;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty() {
return leng Java
>
> Hello
## 总结
本文我们使用了数组和链表等物理结构来实现了栈,当然我们也可以使用其他容器来实现,比如 [Java](https://www.w3cschool.cn/java/) 中的 `List`,我们只需要保证在操作栈时是后进先出的执行顺序,并且至少包含 3 个重要方法:入栈、出栈和查询栈顶元素就可以了。
## 最后
**算法和数据结构的学习是 3 分学 7 分练**,只看不练是没办法学好算法的,而且**学习算法和数据结构是一个循序渐进的过程,短时间内不会有明显的收效**。因为这些算法经过了几百年的发展和积累才得以流传下来的,所以想要“玩得转”还需要一点耐心。
这里给你讲一个学习算法的“秘诀”:**看不懂的知识要反复看,如果反复看还是看不懂,那么别着急,休息一下再继续看!**相信我,对于学习算法这件事,所有人的过程都是一样的。
以上就是`W3Cschool编程狮`关于**动图演示:手撸堆栈的两种实现方法!**的相关介绍了,希望对大家有所帮助。