Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "how to realize the stack of JDK". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Stack translated into Chinese means stack, but in order to distinguish it from Heap (heap), we generally call Stack simply stack. Therefore, when the "stack" is concatenated together, it is possible to indicate Stack, and when there is a semicolon between the "stack, stack", it means Heap (heap) and Stack (stack), as shown in the following figure:

Implementation of JDK Stack

To get to the point, let's take a look at how the stack is implemented in JDK.

In JDK, the implementation class of the stack is Stack, and its inheritance relationship is shown in the following figure:

The methods included in Stack are shown in the following figure:

The most important methods are:

Push: stack method (add data)

Pop: off the stack and return the current element (remove data)

Peek: query the top element of the stack.

The source code for Stack implementation is as follows:

Public class Stack extends Vector {/ * create an empty stack * / public Stack () {} / * stack method, calling the Vector#addElement add method * / public E push (E item) {addElement (item); return item } / * exit the stack and return the current element. Call Vector#removeElementAt 's remove element method * / public synchronized E pop () {E obj; / / return the current top element information int len = size (); obj = peek (); / / query the current top element removeElementAt (len-1) / / remove the top element return obj;} / * query the top element of the stack, and call the query method of Vector#elementAt * / public synchronized E peek () {int len = size (); / / query the length of the current stack if (len = = 0) / / if it is empty, throw an exception throw new EmptyStackException () Return elementAt (len-1); / / query the information of the elements at the top of the stack} / * determine whether the stack is empty * / public boolean empty () {return size () = = 0;} / / ignore other methods.}

From the above source code, you can see that all the core methods in Stack call the methods in the parent class Vector, and the core source code of the Vector class:

Public class Vector extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable {protected Object [] elementData; / / Container for storing data protected int elementCount; / / capacity value of stored data / * add data * / public synchronized void addElement (E obj) {modCount++; / / changed parameter of the statistical container ensureCapacityHelper (elementCount + 1) / / confirm the size of the container. If the capacity exceeds, expand elementData [elementCount++] = obj; / / store the data in the array} / * remove elements (remove according to the subscript) * / public synchronized void removeElementAt (int index) {modCount++ / / Statistics container parameters changed / / data correctness validation if (index > = elementCount) {throw new ArrayIndexOutOfBoundsException (index + "> =" + elementCount);} else if (index)

< 0) { throw new ArrayIndexOutOfBoundsException(index); } int j = elementCount - index - 1; if (j >

0) {/ / not the last element deleted / / move all elements after deletion forward System.arraycopy (elementData, index + 1, elementData, index, j);} elementCount--; / / Array capacity-1 elementData [elementCount] = null / / assign the trailing element to null (delete trailing element)} / * query element (based on subscript) * / public synchronized E elementAt (int index) {/ / Security validation if (index > = elementCount) {throw new ArrayIndexOutOfBoundsException (index + "> =" + elementCount) } / / returns the element return elementData (index) in the array according to the subscript;} / / ignores other methods.}

For the above source code, the most difficult to understand is the System#arraycopy method, which actually moves the subsequent elements of the deleted elements (not the last elements) forward in turn, such as 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))

The result of its operation is:

[Java, Hello, world, JRE, JRE]

That is to say, when we want to delete the element with subscript 3, we need to move the element after 3 forward, so the value of the array has changed from {"Java", "Hello", "world", "JDK", "JRE"} to [Java, Hello, world, JRE, JRE]. Finally, we only need to delete the trailing element to delete the non-ending element in the array.

Summary

From the above source code, we can see that the Stack in JDK is also realized through the physical structure array, and we realize the function of the logical structure stack by operating the physical array.

Application of stack

After the previous study, we already have a certain understanding of the stack, what are the applications of the stack in our daily work? Let's take a look at it next.

Browser fallback

The stack feature is LIFO (Last In First Out,LIFO) LIFO, so you can use this feature to implement the fallback function of the browser, as shown in the following figure:

Function call stack

One of the most classic applications of stack in a program is the function call stack (or method call stack). For example, the operating system allocates an independent memory space to each thread, which is organized into a "stack" structure. used to store temporary variables when a function is called. Each time you enter a function, the temporary variable is put on the stack as a stack frame, and when the called function is completed and returned, the corresponding stack frame of the function is removed from the stack. To give you a better understanding, let's take a look at the execution of this code.

Int main () {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;}

We can see from the code that the main () function calls the add () function, gets the calculation result, adds it to the temporary variable a, and finally prints the value of res. In order to give you a clear view of the operation of the function stack corresponding to this process, I have drawn a diagram. The figure shows what happens when the function call stack is executed to the add () function.

Complexity of the stack

Complexity is divided into two dimensions:

Time dimension: refers to the time it takes to execute the current algorithm, which is usually described as "time complexity"

Spatial dimension: refers to how much memory is required to implement the current algorithm, which is usually described as "space complexity".

Both of these complexities are expressed in large O notation, such as the following code:

Int [] arr = {1,2,3,4}; for (int I = 0; I

< arr.length; i++) { System.out.println(i); } 用大 O 表示法来表示的话，它的时间复杂度就是 O(n)，而如下代码的时间复杂度却为 O(1)： int[] arr = {1, 2, 3, 4}; System.out.println(arr[0]); // 通过下标获取元素 因此如果使用大 O 表示法来表示栈的复杂度的话，结果如下所示：

This is the end of the content of "how JDK implements the stack". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.