In depth analysis of the specific usage of Java vector and stack

We have already touched several data structures, including array, linked list, hash table and red black tree (binary query tree). Today, let's look at another data structure: stack.

What is a stack? Let's take a look at an example first: a stack is equivalent to a very narrow barrel. When we put things in the barrel and take things out, we will find that the things we first put in are at the bottom, and the first ones we take out are just put in. Therefore, stack is such a first in last out (or last in first out) container. It has only one port. It puts elements in this port and takes out elements in this port. Next, let's learn about stack in JDK.

1、 Basic introduction and use of vector & Stack

Let's first look at the definition of JDK:

As can be seen from the above, stack inherits from vector, so we should also have a certain understanding of vector.

Vector: thread safe dynamic array

Stack: a thread safe stack inherited from vector and implemented based on dynamic array;

1. Characteristics of vector and stack:

Vector is basically the same as ArrayList. The difference is that vector is thread safe. The synchronized keyword will be added in front of thread safe methods;

Vector: fast random access speed, poor insertion and removal performance (characteristics of array); Support null elements; In order; Elements can be repeated; Thread safety;

Stack: last in first out, which implements some basic stack operations (in fact, it is not only last in first out, because it inherits from vector and can have many operations. In a sense, it is not a stack);

2. Vector and stack structure:

Vector class

It is basically the same as ArrayList. The remaining main differences are as follows:

1. Vector is thread safe

2. The growth of ArrayList is inconsistent with that of vector

In addition, if the construction methods are inconsistent, vector can initialize capacityincrement through the construction method. In addition, there are other methods, such as indexof method. Vector supports searching from the specified location; In addition, vector has some redundant methods with repeated functions, such as addelement and setelementat methods. This is because of historical reasons. For example, addelement method is a legacy of the past. When the collection framework was introduced, vector joined the collection family and implemented the list interface instead. Some methods defined in the list interface need to be implemented, but for compatibility reasons, The old methods cannot be deleted, so there are some old methods with redundant functions; Now it has been replaced by ArrayList. It is rarely used. Just understand it.

Stack class

The basic operation of stack is realized. The method is as follows:

Create empty stack

Returns the value at the top of the stack;

Stack operation;

Stack out operation;

Judge whether the stack is empty;

Returns the position of the object in the stack;

For the above stack, we basically only use the above methods frequently. Although it inherits vector and has many methods, it will not be used, but just treated as a stack.

3. Basic use

Some methods in vector are used as follows. In addition, the traversal mode of vector is the same as that of ArrayList, which can be traversed by foreach, iterator and for loop;

Some methods in stack are used as follows. Because stack inherits vector, the methods that can be used by vector can also be used by stack. The following are some examples of unique methods of stack, which are very simple, that is, some basic operations of stack. In addition to several pass through methods of vector, It also has its own unique way of traversing elements (using empty method and pop method to traverse from top to bottom of the stack):

Subsection:

Vector is thread safe, but its performance is poor. Generally, ArrayList is used unless special requirements are met;

If you plan to use stack as a stack, you should use it honestly and strictly according to several operations of the stack. Otherwise, you have lost the meaning of using stack and might as well use vector;

2、 Structure and underlying storage of vector & Stack

Vector is an implementation class of list. In fact, vector is also a list container based on array. Its function and implementation code are basically the same as ArrayList. What's different? One is when the array is expanded, the vector is * 2 and the ArrayList is * 1.5 + 1; The other is that vector is thread safe, while ArrayList is not. Vector thread safe is guaranteed by adding a synchronized keyword to each method. But let's say here that vector is unofficial (generally recognized) and not recommended, because its implementation of thread safety is to lock the whole method, resulting in low efficiency. Is there a better scheme? In fact, it can't be said that there is, but there is really one, collections. Synchronizedlist()

Since stack is inherited and based on vector, let's take a brief look at some definitions and method source codes of vector:

Vector simply see here. If other methods stack are not called, they will not be analyzed. If you don't understand, you can see the source code analysis of ArrayList.

3、 Analysis of main methods

1. Peek() -- get the object at the top of the stack

2. Pop () -- pop the stack (out of the stack), get the object at the top of the stack, and delete the object from the container

3. Push (e item) - push (stack), add the object to the container and return

4. Search (object o) -- returns the position of the object in the container. The top of the stack is 1

5. Empty() -- whether the container is empty

Subsection:

Here, the analysis of stack method is completed. Since stack is finally based on array, it is easy to understand (because of the foundation of ArrayList).

Although the source code analysis of stack in JDK is finished, it is necessary to discuss here. I don't know if I find a strange phenomenon of stack here,

(1) Why is stack implemented based on array?

We all know the characteristics of the array: it is convenient to query according to the subscript (random access), but the memory is fixed and the expansion efficiency is low. It is easy to think that stack is the most suitable to implement with a linked list.

(2) Why does stack inherit vector?

Inheritance means that stack inherits the method of vector, which makes stack feel a bit nondescript. It is both a list and a stack. If you have to inherit a vector, what should be the reasonable way: stack does not inherit a vector, but only has a reference to the vector itself. Aggregation, right?

The only explanation is that stack is jdk1 0 came out. At that time, there were no ArrayList, LinkedList and other containers in the JDK, only vector. Now that you have vector and can realize the function of stack, let's do it... Since it is ideal to implement stack with linked list, let's try it:

The LinkedList used here implements the stack. Remember to say in LinkedList that LinkedList implements the deque interface so that it can be used as both a stack (first in, last out) and a queue (first in, first out).

4、 The difference between vector & ArrayList

The list interface has three implementation classes: ArrayList, vector and LinkedList. List is used to store multiple elements, maintain the order of elements, and allow the repetition of elements.

The relevant differences between the three implementation classes are as follows:

1. ArrayList is the most commonly used list implementation class, which is internally implemented through array. It allows fast random access to elements. The disadvantage of the array is that there can be no interval between each element. When the size of the array is not enough, the storage capacity needs to be increased. It is necessary to copy the data of the existing array to the new storage space. When inserting or deleting elements from the middle of the ArrayList, the array needs to be copied, moved and expensive. Therefore, it is suitable for random search and traversal, not for insertion and deletion.

2. Like ArrayList, vector is also implemented through array. The difference is that it supports thread synchronization, that is, only one thread can write vector at a certain time, so as to avoid inconsistency caused by multiple threads writing at the same time. However, realizing synchronization requires a high cost. Therefore, accessing it is slower than accessing ArrayList.

3. LinkedList stores data in a linked list structure, which is very suitable for dynamic insertion and deletion of data. The speed of random access and traversal is relatively slow. In addition, it also provides methods not defined in the list interface, which are specially used to operate header and footer elements, and can be used as stacks, queues and two-way queues.

5、 Simple understanding of queue and deque

1、Queue

Java. Net has been added in Java 5 util. Queue interface to support common operations of queues. This interface extends Java util. Collection interface.

In addition to the basic collection operations, queues also provide other insert, extract, and check operations.

Each method has two forms: one throws an exception (when the operation fails) and the other returns a special value (null or false, depending on the operation).

Queues usually (but not necessarily) sort elements in a FIFO (first in, first out) manner. However, priority queues and LIFO queues (or stacks) are exceptions. The former sorts elements according to the natural order of the provided comparators or elements, and the latter sorts elements in a LIFO (last in, first out) manner.

In the FIFO queue, all new elements are inserted at the end of the queue, and the removed elements are removed from the queue head.

When using the queue, try to avoid the add () and remove () methods of the collection. Instead, use offer () to add elements and poll () to get and remove elements. Their advantage is that the success can be judged by the return value, and the add () and remove () methods will throw exceptions when they fail. If you want to use the front end without removing the element, use the element () or Peek () methods.

The offer method can insert an element, otherwise it returns false. This is the same as collection Unlike the add method, this method can only fail to add elements by throwing unchecked exceptions.

The remove () and poll () methods remove and return the header of the queue. Which element to remove from the queue is the function of the queue sorting policy, which is different in various implementations. The remove () and poll () methods behave differently only when the queue is empty: the remove () method throws an exception, while the poll () method returns null.

Element () and Peek () return, but do not remove, the header of the queue.

Queue implementations usually do not allow the insertion of null elements, although some implementations (such as LinkedList) do not prohibit the insertion of null. Even in implementations that allow null, null should not be inserted into the queue, because null is also used as a special return value of the poll method, indicating that the queue does not contain elements.

It is worth noting that the LinkedList class implements the queue interface, so we can use LinkedList as a queue.

2、Deque

A linear collection that supports inserting and removing elements at both ends.

The name deque is an abbreviation for "double ended queue", which is usually read as "deck".

Most deque implementations have no fixed limit on the number of elements they can contain, but this interface supports both double ended queues with capacity limit and double ended queues without fixed size limit.

This interface defines methods to access elements at both ends of a two ended queue. Provides methods for inserting, removing, and checking elements. Because this interface inherits the queue interface queue, each method also has two forms: one is to throw an exception when the operation fails, and the other is to return a special value (null or false, depending on the operation).

a. When a double ended queue is used as a queue, the FIFO (first in first out) behavior will be obtained. Add the element to the end of the double ended queue and remove the element from the beginning of the double ended queue. The method inherited from the queue interface is completely equivalent to the deque method, as shown in the following table:

b. Used as a LIFO (last in, first out) stack. This interface should be used in preference to the legacy stack class. When a two ended queue is used as a stack, elements are pushed to and ejected from the beginning of the two ended queue. The stack method is completely equivalent to the deque method, as shown in the following table:

@H_ 216_ 301@