The previous article “GIF Demo: Two Ways to Implement a Handlift Stack!” We use arrays and linked lists to implement a custom stack structure. How is the stack implemented in the JDK? Let’s take a look.
Before we begin, let me explain the meaning of the word “stack” again, because some readers have been confused by this word.
In Chinese, Stack means Stack, but in order to distinguish it from Heap, we usually call Stack for short. Therefore, when “Stack” is connected together, it may mean Stack, while when “Heap and Stack” is separated by a semicolon, it means Heap and Stack, as shown below:
Implementation of the JDK stack
How is the stack implemented in the JDK?
In the JDK, the implementation class of Stack is Stack, and its inheritance relationship is shown in the following figure:
The Stack contains the following methods:
Among the most important methods are:
- Push: method of pushing (adding data);
- Pop: unstack and return the current element (remove data);
- Peek: Query the top of the stack element.
Stack implementation source code is as follows:
public class Stack<E> extends Vector<E> {
/** * create an empty stack */
public Stack(a) {}Vector#addElement (); /** * add Vector#addElement */
public E push(E item) {
addElement(item);
return item;
}
/** * unstack and return the current element, calling Vector#removeElementAt's remove element method */
public synchronized E pop(a) {
E obj; // Returns information about the current top element to be removed
int len = size();
obj = peek(); // Query the current top element of the stack
removeElementAt(len - 1); // Remove the top element of the stack
return obj;
}
/** * to query the top element of the stack, call Vector#elementAt's query method */
public synchronized E peek(a) {
int len = size(); // Query the current stack length
if (len == 0) // If the stack is empty, throw an exception
throw new EmptyStackException();
return elementAt(len - 1); // Query information about the top element of the stack
}
/** * Check whether the stack is empty */
public boolean empty(a) {
return size() == 0;
}
// Ignore other methods...
}
Copy the codeVector (); Stack (); Stack (); Stack (); Stack ();
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable
{
protected Object[] elementData; // A container for storing data
protected int elementCount; // Data storage capacity
/** * Add data */
public synchronized void addElement(E obj) {
modCount++; // Count the changed parameters of the container
ensureCapacityHelper(elementCount + 1); // Check the container size. If the container capacity exceeds, expand it
elementData[elementCount++] = obj; // Store the data in an array
}
/** * removes the element (by subscript) */
public synchronized void removeElementAt(int index) {
modCount++; // Count the changed parameters of the container
// Verify data correctness
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + "> =" +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) { // Delete not the last element
// Move all elements forward after the deleted element
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--; // The size of the array is -1
elementData[elementCount] = null; // Assign the trailing element to null (delete the trailing element)
}
/** * query elements (by subscript) */
public synchronized E elementAt(int index) {
// Security verification
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + "> =" + elementCount);
}
// Returns the element in the array based on the index
return elementData(index);
}
// Ignore other methods...
}
Copy the codeThe least understood of the above source code is the System#arraycopy method, which moves the subsequent elements of the deleted element (not the trailing element) forward, as in the following code:
Object[] elementData = {"Java"."Hello"."world"."JDK"."JRE"};
int index = 3;
int j = elementData.length - index - 1;
System.arraycopy(elementData, index + 1, elementData, index, j);
// System.arraycopy(elementData, 4, elementData, 3, 1);
System.out.println(Arrays.toString(elementData));
Copy the codeThe results are as follows:
[Java, Hello, world, JRE, JRE]
So when we delete an element with index 3, we move the element after 3 forward, So the array goes from {“Java”, “Hello”, “world”, “JDK”, “JRE”} to [Java, Hello, world, JRE, JRE], and then we just delete the tail element, You can remove non-trailing elements from the array.
summary
Through the above source code can be learned, the Stack (Stack) in the JDK is also achieved by the physical structure array, we operate the physical array to achieve the function of the logical structure Stack, on the physical structure and logical structure see “DYNAMIC diagram demo: two ways to achieve the Stack!” .
The application of the stack
After the previous study we have a certain understanding of the stack, the stack in our daily work what are the applications? Let’s take a look.
Browser Rollback
The stack feature is LIFO (Last In First Out, LIFO), so you can use this feature to implement the browser rollback function, as shown In the following figure:
Function call stack
One of the most classic applications of the stack in a program is the function call stack (or method call stack). For example, the operating system allocates a separate memory space for each thread. This memory is organized into a “stack” structure, which is used to store temporary variables during function calls. Each time a function is entered, a temporary variable is pushed onto the stack as a frame. When the called function completes execution and returns, the corresponding frame of the function is pushed off the stack. To give you a better understanding, let’s take a look at the execution of this code.
int main(a) {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3.5);
res = a + ret;
System.out.println(res);
reuturn 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}
Copy the codeAs we can see from the code,main()The function is calledadd()Function to get the result of the calculation, and with temporary variablesaAdd them up and print them outresThe value of the. To give you a clear picture of what happens when a function is pushed and out of the stack, I drew a diagram. As shown in the figure, after the execution toadd()Function, function call stack.
Stack complexity
Complexity is divided into two dimensions:
- Time dimension: refers to the time consumed by executing the current algorithm, which is usually described by “time complexity”.
- Spatial dimension: Refers to the amount of memory required to perform the current algorithm, which is usually described as “spatial complexity”.
Both of these complexities are expressed in big O notation, as in the following code:
int[] arr = {1.2.3.4};
for (int i = 0; i < arr.length; i++) {
System.out.println(i);
}
Copy the codeIn big O notation, the time complexity is O(n), while the following code is O(1) :
int[] arr = {1.2.3.4};
System.out.println(arr[0]); // Get the element by subscript
Copy the codeSo if we use the big O notation to represent the stack complexity, we get something like this:
Quotation & acknowledgement
Time.geekbang.org/column/arti…
Follow the public account “Java Chinese Community” to send “interview” to receive the latest interview information.
