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

This article mainly explains "how to achieve the Stack stack". The content in the article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn how to achieve the Stack stack.

First, Stack source code analysis

Stack, stack, is also a kind of data structure. For java application developers, I use stack less. Generally, it is used to do algorithmic questions. For actual application scenarios, I think stack is still a powerful data structure. The characteristics of stack are first in, first out, first in, first out.

Second, method analysis

In fact, how to say, I have analyzed the source code analysis of the Vector collection, but the stack inherits the Vector class, so, you know, the stack is a special case of the Vector collection, so this article will be very brief, but I will analyze it anyway.

The most comprehensive source code analysis of the Vector collection

2.1.Stack structure inheritance structure / / remember and understand the characteristics of "single inheritance, multiple implementation" of java class.

Public class Stack extends Vector {} 2.2, constructor / / a no-argument constructor

Public Stack () {

} 2.3 push () method

In fact, the stack is also regarded as a collection, and the collection is used to load the data elements, so the next step is to analyze the various methods of the stack, how to load the data elements, of course, we need to take a look at the push () method.

Public E push (E item) {

/ / check the second step.

AddElement (item)

Return item

}

/ / step 2

Public synchronized void addElement (E obj) {

/ / the following explanation is already very vivid in the meaning of modCount

/ / The number of times this list has been modified

ModCount++

/ / this step is to expand the capacity. Instead of analyzing it here, you can take a look at the article on vector source code analysis.

EnsureCapacityHelper (elementCount + 1)

/ / load elements in an array

ElementData [elementCount++] = obj

} 2.4 public synchronized E pop pop () method {

E obj

/ / the second step is to get the stack size

Int len = size ()

/ / the third step is to call the peek () method to get the location of the elements at the top of the stack.

Obj = peek ()

/ / the fourth step is to delete the elements at the top of the stack to achieve the function of pop ().

/ / analyze the peek () method later.

RemoveElementAt (len-1)

Return obj

}

/ / step 2

Public synchronized int size () {

/ / this is a thread-safe method that returns the number of collection elements and the member variable elementCount

Return elementCount

}

/ / step 4

Public synchronized void removeElementAt (int index) {

/ / actually, you don't have to care too much about this.

ModCount++

/ / first of all, when we delete an element, we will first determine whether the element exists.

/ / here index=len-1 is the last element of the array space.

If (index > = elementCount) {

Throw new ArrayIndexOutOfBoundsException (index + "> =" +

ElementCount)

}

/ / the starting position of the array space starts at 0, so if it is less than 0, the problem of index out of bounds needs to be thrown.

Else if (index

< 0) { throw new ArrayIndexOutOfBoundsException(index); } //确定j的位置，便于数组元素的移动 int j = elementCount - index - 1; if (j >

0) {

System.arraycopy (elementData, index + 1, elementData, index, j)

}

/ / the number of set elements minus one

ElementCount--

/ / set the removed element to null, as indicated in the comments below, in order to trigger gc to reclaim the unreachable object's

/ / in order to integrate memory space

ElementData [elementCount] = null; / * to let gc do its work * /

} 2.5 public synchronized E peek peek () method {

/ / get the number of collection elements

Int len = size ()

/ / when the number of collections is 0, an exception with an empty stack should be thrown when you get the element

If (len = = 0)

Throw new EmptyStackException ()

Return elementAt (len-1)

}

/ / step 2

Public synchronized E elementAt (int index) {

/ / verify whether the index is out of bounds

If (index > = elementCount) {

Throw new ArrayIndexOutOfBoundsException (index + "> =" + elementCount)

}

/ / get the elements at the specified location according to the index subscript location

Return elementData (index)

}

/ / step 3

E elementData (int index) {

Return (E) elementData [index]

} 2.6 public boolean empty isEmpty () method

/ / determine whether the set size is equal to 0

Return size () = = 0

} 2.7 public synchronized int search search () method (Object o) {

Int I = lastIndexOf (o)

If (I > = 0) {

Return size ()-I

}

Return-1

}

/ / step 2

Public synchronized int lastIndexOf (Object o) {

Return lastIndexOf (o, elementCount-1)

}

/ / step 3

Public synchronized int lastIndexOf (Object o, int index) {

/ / pre-inspection mechanism

If (index > = elementCount)

Throw new IndexOutOfBoundsException (index + "> =" + elementCount)

/ / in fact, collections can be loaded with null elements, so we need to distinguish here that the time complexity is O (n).

If (o = = null) {

For (int I = index; I > = 0; iMury -)

If (elementdata [I] = = null)

Return i

} else {

For (int I = index; I > = 0; iMury -)

If (o.equals (elementdata [I]))

Return i

}

Return-1

} Thank you for your reading, the above is the content of "how to implement Stack Stack". After the study of this article, I believe you have a deeper understanding of how to implement Stack Stack, and the specific usage needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.