Dynamic diagram demonstration: two implementation methods of hand rolling stack!
Before we start, let's talk with friends about our plans for the later stage. In the following articles, we plan to write some content about data structures and algorithms. The reason is very simple. The underlying structure determines the superstructure. Today, when the framework is flying all over the world, we should not only learn how to use the framework, but also understand its principle and underlying data structure, Only in this way can we make better use of it.
Of course, in addition to the above reasons, another important factor is to get the interview done.
With the increasingly fierce competition in the software development industry, the difficulty of the interview is also gradually increasing, because enterprises can only improve the difficulty of the interview if they want to select the best person from a large number of interviewers, and one of the brain burning hard core skills of algorithm and data structure has naturally become the preferred subject of the interview. And with the passage of time, the frequency and proportion of algorithms and data structures will continue to increase. Therefore, in order to comply with the development trend of the times, we also need to make some adjustments. Therefore, in some later articles, I will update some articles on Algorithms and data structures one after another. I hope you can like them.
Stack
Stack is also called stack (stack for short). It is a linear table that inserts and deletes data at the same end.
Stack is one of the most basic and common data structures. Its data structure and operation flow are shown in the following figure:
Among them, one end that allows insertion and deletion is called the top of the stack, and the other end is called the bottom of the stack. The bottom of the stack is fixed and the top of the stack is floating.
When the element in the stack is zero, the stack is called an empty stack. Adding data is generally called pushing or pushing, and deleting data is called pop. Stack is a linear table of last in first out (LIFO).
Physical structure & logical structure
Before hand rolling algorithm, let's first understand two important concepts in data structure: physical structure and logical structure.
When we talk about the words "physical" and "logical", we can think of logical deletion and physical deletion in the database.
The so-called physical deletion refers to the process of deleting data from the physical structure through the deletion command; Logical deletion refers to changing the data to the "deleted" state through the modification command, which is not the real deletion of data.
The logical structure and physical structure here are similar to the above concepts. The so-called physical structure means that data can be stored in physical space. For example, arrays and linked lists belong to physical data structures; The logical structure is used to describe the logical relationship between data. For example, the stack to be discussed in this paper belongs to the logical structure.
Maybe some people are blindfolded when they see here. It doesn't matter. I'll give you an example to understand.
If people are used to express the physical structure and logical structure, the real flesh and blood people belong to the physical structure, and people's thoughts and beliefs belong to the logical structure.
Custom stack I: array implementation
Through the above content, we know that the stack belongs to a logical structure, so there can be many ways to implement it, such as array or linked list. Let's implement the stack with array first. The main methods of stack are as follows:
① Define structure
Let's define its structure first:
public class MyStack<E> {
private Object[] value = null; // 栈存储容器
private int top = -1; // 栈顶（的指针）
private int maxSize = 0; // 栈容量
// 构造函数（初始化默认容量）
MyStack() {
this.maxSize = 10;
}
// 有参构造函数
MyStack(int initSize) throws Exception {
if (initSize <= 0) {
throw new Exception("栈容量必须大于 0");
} else {
value = new Object[initSize];
maxSize = initSize;
top = -1;
}
}
}
The data in the stack will be stored in the object [] value array. The top variable represents the pointer at the top of the stack. In fact, it stores the subscript of the element at the top of the stack, which will change with the entering of the stack (last in first out). Maxsize represents the maximum capacity of the stack.
② Stack
This method adds data to the stack. The implementation code is as follows:
// 入栈（数据添加）
public boolean push(E e) throws Exception {
if (maxSize - 1 == top) {
throw new Exception("入栈失败，栈已满");
} else {
value[++top] = e;
return true;
}
}
Each time there is data insertion, just add a value to the array and add the subscript + 1 at the top of the stack.
The stack operation is shown in the following figure:
③ Out of stack
This method deletes the data in the stack. The implementation code is as follows:
// 数据移除（出栈）
public E pop() throws Exception {
if (top <= -1) {
throw new Exception("移除失败，栈中已无数据");
} else {
return (E) value[top--];
}
}
Just delete the stack top data (the last added data) in the array and modify the stack top subscript - 1.
The stack operation is shown in the following figure:
④ Data query
In addition to the above operation methods, we also need to add a method to query stack top data:
// 数据查询
public E peep() throws Exception {
if (top <= -1) {
throw new Exception("移除失败，栈中已无数据");
} else {
return (E) value[top];
}
}
⑤ Code test
So far, the data structure of the stack has been implemented. Next, let's test:
// 代码测试
public static void main(String[] args) throws Exception {
MyStack stack = new MyStack(10);
stack.push("Hello");
stack.push("Java");
System.out.println(stack.peep());
stack.pop();
System.out.println(stack.pop());
}
The results of the above procedures are:
From the above code, we can see that the order of adding stack is hello and Java, while the order of output is Java and Hello, which conforms to the definition of stack (last in first out).
Custom stack II: linked list implementation
In addition to arrays, we can also use the linked list to implement the stack structure. Its implementation is slightly more complex. Let's first look at the data structure of the linked list itself:
Let's first define a linked list node:
public class Node {
Object value; // 每个节点的数据
Node next; // 下一个节点
public Node(Object value) {
this(value,null);
}
/**
* 创建新节点
* @param value 当前节点数据
* @param next 指向下一个节点（头插法）
*/
public Node(Object value,Node next) {
this.value = value;
this.next = next;
}
}
Next, we use the linked 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 <= 0) {
throw new Exception("栈容量不能小于等于0");
}
top = null;
maxSize = initSize;
leng = 0;
}
/**
* 容量是否已满
* @return
*/
public boolean isFull() {
return leng >= maxSize;
}
/**
* 是否为空
* @return
*/
public boolean isEmpty() {
return leng <= 0;
}
/**
* 入栈
* @param val
* @return
* @throws Exception
*/
public boolean push(Object val) throws Exception {
if (this.isFull()) {
// 容量已满
throw new Exception("容量已满");
}
top = new Node(val,top); // 存入信息，并将当前节点设置为头节点
leng++;
return true;
}
/**
* 出栈（移除）
* @return
* @throws Exception
*/
public Node pop() throws Exception {
if (this.isEmpty()) {
throw new Exception("栈为空，无法进行移除操作");
}
Node item = top; // 返回当前元素
top = top.next;
leng--;
return item;
}
/**
* 查询栈顶信息
* @return
*/
public Node peek() throws Exception {
if (isEmpty()) {
throw new Exception("你操作的是一个空栈");
}
return top;
}
// 代码测试
public static void main(String[] args) throws Exception {
StackByLinked stack = new StackByLinked(10);
stack.push("Hello");
stack.push("Java");
System.out.println(stack.peek().value);
stack.pop();
System.out.println(stack.pop().value);
}
}
The results of the above procedures are: