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

This article will explain in detail how to implement the stack in JDK. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.

Implementation of JDK Stack

In JDK, the implementation class of the stack is Stack.

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) {/ / 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 = 3poliint j = elementData.length-index-1 index 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 property of the stack is LIFO (Last In First Out,LIFO) LIFO, so the fallback function of the browser can be realized with this feature.

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; iTunes +) {System.out.println (I);}

In large O notation, its time complexity is O (n), while the time complexity of the following code is O (1):

Int [] arr = {1, 2, 3, 4}; System.out.println (arr [0]); / / get the elements through the subscript on "how to implement the stack of JDK" this article is shared here, I hope the above content can be of some help to you, so that you can learn more knowledge, if you think the article is good, please share it for more people to see.

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.