Before the official start of the and some friends talk about the late to the back of the article plans to write something about the content of the data structure and algorithm, for the simple reason underlying structure decides the superstructure, the framework of the flying today, we not only learn how to use the framework, more to understand the principle and the underlying data structure, only in this way can we better use it.
Of course, in addition to the above reasons, another important factor is to nail the interview.
With the increasingly fierce competition in software development industry, the difficulty of interview is also gradually increasing, because the enterprise needs to select the best person from a large number of interviewees, can only increase the difficulty of interview, and algorithms and data structure more brain-intensive core skills, naturally become the first subject of interview. And with the passage of time, the frequency and proportion of algorithms and data structures will continue to increase, so in order to comply with the trend of the development of The Times, we also need to make some adjustments, so in the next few articles, I will update some articles about algorithms and data structures, I hope you can like them.
PS: Of course, with the popularity of intelligent systems (nowadays, Ri Toutiao and Tiktok), algorithms and data structures are increasingly used in enterprises, so learning algorithms and data structures is also an urgent matter.
The stack
Stack (Stack), also called Stack (referred to as the Stack), it is a linear table in the same end to insert and delete data.
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, the end that allows insertion and deletion is called the Top of the stack, and the other end is called the Bottom of the stack, with the Bottom fixed and the Top floating.
When the elements in a stack are zero, the stack is called empty. Adding data is usually called pushing, and removing data is called popping. The stack is a linear list of Last In First Out (LIFO).
Physical structure & logical structure
Before we start with algorithms, let’s take a look at two important concepts in data structures: physical structure and logical structure.
When talking about the terms “physical” and “logical”, we can think of logical and physical deletions in databases.
Physical deletion refers to the process of actually deleting data from the physical structure by using the delete command. Logical deletion refers to changing data to the “deleted” state by using a modification command, rather than actual deletion of data.
The logical structure and physical structure here are similar to the above concept. 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. Logical structures are used to describe the logical relationships between data, such as the stack described in this article.
Maybe some people are confused by this, but that’s okay. I’ll give you an example to get the idea.
If physical and logical structures are represented by human beings, then actual flesh-and-blood people belong to physical structures, while thoughts and beliefs belong to logical structures.
Custom stack I: array implementation
From the above content, we know that the stack is a logical structure, so it can be implemented in many ways, such as array implementation or linked list implementation. So let’s first use an array implementation, stack main methods are:
① Define the structure
So let’s first define its structure:
public class MyStack<E> {
private Object[] value = null; // stack storage container
private int top = -1; // top of stack (pointer)
private int maxSize = 0; / / stack capacity
// Constructor (initialize default capacity)
MyStack() {
this.maxSize = 10;
}
// Has a parameter constructor
MyStack(int initSize) throws Exception {
if (initSize <= 0) {
throw new Exception("Stack size must be greater than 0");
} else {
value = new Object[initSize];
maxSize = initSize;
top = -1; }}}Copy the codeWhere the data in the stack will be stored in the Object[] value array, the top variable represents the pointer to the top of the stack, which actually stores the subscript of the element at the top of the stack, which will change with the stack (last in, first out), and maxSize represents the maximum capacity of the stack.
(2) into the stack
This method is to add data to the stack, the implementation code is as follows:
// Push (add data)
public boolean push(E e) throws Exception {
if (maxSize - 1 == top) {
throw new Exception("Loading failed, stack is full");
} else {
value[++top] = e;
return true; }}Copy the codeEach time data is inserted, simply add a value to the array and add the subscript at the top of the stack +1.
The pushing operation is shown in the figure below:
(3) out of the stack
This method is to delete the stack of data, the implementation code is as follows:
// Remove data from the stack
public E pop(a) throws Exception {
if (top <= -1) {
throw new Exception("Remove failed, no data in stack");
} else {
return(E) value[top--]; }}Copy the codeTo unstack, simply delete the top data (the last data added to the array) and change the top subscript -1.
The stack removal operation is shown in the figure below:
④ Data query
In addition to the above operations, we need to add a method to query the data at the top of the stack:
// Data query
public E peep(a) throws Exception {
if (top <= -1) {
throw new Exception("Remove failed, no data in stack");
} else {
return(E) value[top]; }}Copy the code⑤ Code test
Now that the stack data structure is complete, let’s test it:
// Code tests
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());
}
Copy the codeThe execution results of the above programs are as follows:
Java
Hello
As you can see from the above code, we add stacks in The order of Hello, Java, and export stacks in the order of Java. Hello follows the stack definition (last in, first out).
Custom stack II: Linked list implementation
In addition to arrays, we can also use linked lists to implement stack structures. This implementation is slightly more complicated. 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; // Data for each node
Node next; // Next node
public Node(Object value) {
this(value, null);
}
/** * Create a new node *@paramValue Indicates the current node data *@paramNext points to the next node (headplug) */
public Node(Object value, Node next) {
this.value = value;
this.next = next; }}Copy the codeNext we use linked lists to implement a complete stack:
public class StackByLinked {
private Node top = null; // Stack top data
private int maxSize = 0; // Maximum stack capacity
private int leng = 0; // The actual stack capacity
public StackByLinked(int initSize) throws Exception {
if (initSize <= 0) {
throw new Exception("Stack size can't be less than or equal to zero.");
}
top = null;
maxSize = initSize;
leng = 0;
}
/** * Whether the capacity is full *@return* /
public boolean isFull(a) {
return leng >= maxSize;
}
/** * is null *@return* /
public boolean isEmpty(a) {
return leng <= 0;
}
/** * push *@param val
* @return
* @throws Exception
*/
public boolean push(Object val) throws Exception {
if (this.isFull()) {
// The capacity is full
throw new Exception("Capacity full");
}
top = new Node(val, top); // Store the information and set the current node as the head node
leng++;
return true;
}
/** ** unstack (remove) *@return
* @throws Exception
*/
public Node pop(a) throws Exception {
if (this.isEmpty()) {
throw new Exception("Stack empty, unable to remove");
}
Node item = top; Return the current element
top = top.next;
leng--;
return item;
}
/** * Query information on the top of the stack *@return* /
public Node peek(a) throws Exception {
if (isEmpty()) {
throw new Exception("You're operating on an empty stack.");
}
return top;
}
// Code tests
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); }}Copy the codeThe execution result of the above procedure is:
Java
Hello
conclusion
In this article, we use arrays and linked lists to implement the stack. Of course, we can also use other containers to implement the stack, such as the List in Java, we just need to ensure that the stack operation is last in first out order, and contain at least three important methods: on the stack, off the stack and query the top element.
The last
The study of algorithm and data structure is 3 points to learn 7 points to practice, only see without practice is not able to learn the algorithm, and learning algorithm and data structure is a step-by-step process, in a short time will not have obvious effect. Because these algorithms have evolved over hundreds of years, it takes a bit of patience to play well.
Here to tell you a learning algorithm “secret” : ** do not understand the knowledge to repeatedly see, if repeatedly see or do not understand, then don’t worry, have a rest and continue to see! Trust me, when it comes to learning algorithms, the process is the same for everyone.
Follow the public account “Java Chinese Community” to send “interview” to receive the latest interview information.
