Why Stack is not recommended
Java no longer recommends the use of Stack, but instead recommends the use of the more efficient ArrayDeque
Why it is not recommended
-
Low performance: Stack inherits from Vector, which adds locks to every method. Because of the need for compatibility with older projects, it's hard to optimize on top of what's already there, so Vector is out, and using theArrayList respond in singingCopyOnWriteArrayList instead, if in a non-thread-safe situation you can use theArrayListThe thread-safe case can be used with theCopyOnWriteArrayList 。
-
Destroys the original data structure: a stack is defined to perform push and pop operations at one end, and should not contain any other methods for entering or exiting the stack, but Stack inherits from Vector, which makes it possible for Stack to use the methods that are public to its parent, Vector.
Why are you still using it?
But there are two main reasons why many people still use Stack.
-
Stacks are not officially recommended by the JDK, and many people still use them because the JDK doesn't annotate them with deprecation, it just states that they're not recommended in the documentation and comments, but very few people pay attention to the details of their implementation.
-
More for the written interview in the algorithmic questions, focus on the algorithmic logic to solve the problem on the idea, and will not be concerned about the implementation of the details of the Stack in different languages, but for the use of Java business developers, not only need to pay attention to the algorithmic logic itself, but also need to pay attention to the implementation of the details of it!
Why the Deque interface is recommended to replace the stack
If the JDK does not recommend the use of Stack, what collection class should be used to replace the stack, together with the official documentation.
As shown in the labeled portion of the diagram, stack-related operations should be provided by the Deque interface. It is recommended that you use the Deque data structure, as well as its subclasses, such as ArrayDeque.
val stack: Deque<Int> = ArrayDeque()
What are the benefits of using the Deque interface for stack functionality:
- Faster than Stack.
This class is probably faster than Stack when used as a stack, and probably faster than LinkedList when used as a queue. Because the original Java Stack inherited from Vector, which added locks to every method, ArrayDeque, a subclass of Deque, has no locking overhead.
- Blocking out irrelevant methods
The original Java Stack contained methods for adding or removing elements at any location, which is not the way a stack should be, so these extraneous methods needed to be blocked. Declaring the Deque interface solves this problem by declaring the methods needed for the stack in the interface, regardless of how the subclasses are implemented, and for the higher-level users, only the methods related to the stack can be called.
Difference between Stack and ArrayDeque
| Collection type | data structure | thread-safe or not |
|---|---|---|
| Stack | arrays | be |
| ArrayDeque | arrays | clogged |
The methods commonly used by Stack are shown below:
| manipulate | methodologies |
|---|---|
| push on | push(E item) |
| send a package to a warehouse | pop() |
| View the top of the stack | peek() returns null if null |
The methods commonly used by ArrayDeque are shown below:
| manipulate | methodologies |
|---|---|
| push on | push(E item) |
| send a package to a warehouse | poll() Returns if the stack is empty nullpop() Throws an exception if the stack is empty |
| View the top of the stack | peek() returns null if null |
Introduction to Queue
Java has a class called Stack, but not a class called Queue (it is an interface name). When the need to use the stack, Java has not recommended the use of Stack, but recommended the use of more efficient ArrayDeque; since Queue is just an interface, when the need to use the queue is also preferred ArrayDeque (the second choice is LinkedList).
Queue
Queue interface inherited from the Collection interface , in addition to the most basic methods of the Collection , it also supports additional insertion, extraction and inspection operations . Here are two groups of format, a total of six methods, one group is the implementation of throwing exceptions; another group is the implementation of the return value (no return null).
Deque
Deque is a "double ended queue", which means a two-way queue, pronounced as "deck" in English. Deque inherited from the Queue interface, in addition to supporting Queue methods, but also supports insert, remove and examine operations, because Deque is two-way, so you can operate on both the head and tail of the queue, which also supports two sets of formats, one set of exceptions; the other is the return value of the implementation (no return null). ). A total of 12 methods are as follows.
When using a deque as a FIFO queue, elements are added from the end of the deque and deleted from the head; so some of the deque's methods are equivalent to a queue. The details are as follows.
Deque means "double ended queue", that is, double ended queue, it can be used as a stack, can also be used as a queue. The following table lists the interfaces corresponding to Deque and Queue.
The following table lists the interfaces corresponding to Deque and Stack.
The above two tables define a total of 12 interfaces for Deque. There are two sets of interfaces for adding, deleting, and fetching values, which have the same functionality, but the difference is the handling of failure cases. One set of interfaces throws an exception if it fails, and the other returns a special value (false or null) if it fails. Unless an implementation has a capacity limitation, in most cases the add operation will not fail. Although there are as many as 12 interfaces to Deque, they are nothing more than operations on both ends of the container, either adding, removing, or viewing.
ArrayDeque and LinkedList are two common implementations of Deque, because the official more recommended to use AarryDeque as a stack and queue, coupled with the previous article has explained the LinkedList, this article will focus on explaining the specific implementation of ArrayDeque
ArrayDeque can be seen from the name of the bottom through the array implementation, in order to meet the needs of the array can be inserted at the same time at both ends of the elements or delete the array must also be circular, that is, circular array (circular array), that is to say, any point of the array may be regarded as the starting point or the end point . ArrayDeque is not thread-safe, requiring the programmer to manually synchronize it when multiple threads are using it at the same time; in addition, the container does not allow null elements.
Above, we see that head points to the first valid element at the beginning and tail points to the first empty space at the end where an element can be inserted. Since this is a circular array, head may not always be equal to 0, and tail may not always be larger than head.
methodological analysis
addFirst()
The effect of addFirst(E e) is to insert an element at the head of the Deque, i.e., in front of the head, and in the case where there is enough space and the subscript is not out of bounds, you just need to set elements[--head] = e.
Practical considerations.
- Is there enough space
- The question of whether subscripts are out of bounds
In the above figure, if you call addFirst() after head is 0, although there is still enough free space, head is -1 and the subscript is out of bounds.
//addFirst(E e)
public void addFirst(E e) {
if (e == null)//Not allowed to put innull
throw new NullPointerException();
elements[head = (head - 1) & ( - 1)] = e;//2.Whether the subscript is out of bounds
if (head == tail)//1.Is there enough space
doubleCapacity();//expansion
}
As you can see from the above code, the space problem is solved after the insertion;First of all, since tail always points to the next available empty space, which means that the elements array has at least one empty space, you don't have to think about space when inserting elements.
The handling of subscript out-of-bounds is very simple to solve, head = (head - 1) & ( - 1) is all that is needed, theThis code is equivalent to taking a remainder, and also solves the case where head is negativeBecause it must be an exponential multiple of 2. Because it must be an exponential multiple of 2, elements - 1 is the binary low all 1, with the head - 1 and after the role of modulo, if the head - 1 for the negative (in fact, only may be -1), it is equivalent to take the complement of its relative.
Numerical values in computers are expressed as complements, and if they are 8-bit, -1 is 1111 1111, and ( - 1) is also 1111 1111, so the sum of the two is also ( - 1);
head = (head - 1) & ( - 1) and finally let the calculated position be assigned to head, so this code actually lets head be assigned from back to front again
Expansion function doubleCapacity(), the logic is to apply for a larger array (twice the original array), and then copy the original array over. The process is shown in the following figure.
As you can see in the figure, the copying is done in two passes, the first time copying the elements to the right of HEAD and the second time copying the elements to the left of HEAD.
//doubleCapacity()
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = ;
int r = n - p; // headNumber of elements on the right
int newCapacity = n << 1;//raw space2times (multiplier)
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
(elements, p, a, 0, r);//Copy the right half，Corresponds to the green part of the figure above
(elements, 0, a, r, p);//Copy the left half，Corresponds to the gray portion of the chart above
elements = (E[])a;
head = 0;
tail = n;
}
addLast()
The addLast(E e) is used in theDequeInsert the element at the end of the tail, that is, insert the element at the position of tail. Since tail always points to the next empty space that can be inserted, it is only necessary that elements[tail] = e;. After the insertion is completed and then check the space, if the space has been used up, then call doubleCapacity() for expansion.
public void addLast(E e) {
if (e == null)//Not allowed to put innull
throw new NullPointerException();
elements[tail] = e;//assign a value to something
if ( (tail = (tail + 1) & ( - 1)) == head)//Subscript transboundary processing
doubleCapacity();//expansion
}
pollFirst()
The effect of pollFirst() is to remove and return theDequeThe first element, i.e. the element at the head position. If the container is not empty, just return elements[head] directly, but of course you need to deal with subscripts. Since null is not allowed in ArrayDeque, when elements[head] == null, it means the container is empty.
public E pollFirst() {
int h = head;
E result = elements[head];
if (result == null)//nullvaluedequeempty
return null;
elements[h] = null;//let GC work
head = (head + 1) & ( - 1);//Subscript transboundary processing
return result;
}
pollLast()
The function of pollLast() is to remove and return the element at the end of the Deque, i.e., the element in front of the tail position.
public E pollLast() {
int t = (tail - 1) & ( - 1);//tailThe previous position of the last element of the
E result = elements[t];
if (result == null)//nullvaluedequeempty
return null;
elements[t] = null;//let GC work
tail = t;
return result;
}
peekFirst()
The effect of peekFirst() is to return but not delete theDequeThe first element, i.e. the element at the head position, is returned directly as elements[head].
public E peekFirst() {
return elements[head]; // elements[head] is null if deque empty
}
peekLast()
The effect of peekLast() is to return but not remove theDequeThe tail element, i.e. the one in front of the tail position.
public E peekLast() {
return elements[(tail - 1) & ( - 1)];
}
About the Author.
From the front-line programmer Seven's exploration and practice, continuous learning iteration in the~
This article is included in my personal blog:https://
Public number: seven97, welcome to follow~