We have been exposed to several data structures before, including arrays, linked lists, Hash tables, and red and black trees (binary query trees). Today, let’s look at another data structure: stack.
What is a stack? Let’s first look at an example: a stack is equivalent to a very narrow wooden barrel. When we put things into the wooden barrel and take things out, we will find that the thing we put at the bottom at the beginning, and the first thing we took out was the one we just put in. Therefore, the stack is such a container that first in and out (FirstInLastOut, or later in and first out). It has only one mouth, put elements in this mouth, and also take elements out in this mouth. Then let's learn the stack in JDK next.
1. Basic introduction and use of Vector&Stack
Let's first look at the definition of JDK:
public class Stack<E> extends Vector<E> {From the above, we can see that Stack is inherited from Vector, so we must also have a certain understanding of Vector.
Vector: Thread-safe dynamic arrays
Stack: Inheriting Vector, a thread-safe stack implemented based on dynamic arrays;
1. Features of Vector and Stack:
Vector and ArrayList are basically the same. The difference is that Vector is thread-safe and will add the synchronized keyword before the possible thread-safe methods;
Vector: fast random access speed, poor insertion and removal performance (characteristics of array); supports null elements; has order; elements can be repeated; thread-safe;
Stack: After-in, first-out, implements some basic stack operations methods (in fact, it is not only after-in, first-out, because inherited from Vector, there can be many operations, and in a sense, it is not a stack);
2.Vector and Stack structure:
Vector class
It is basically the same as ArrayList, and the remaining main differences are as follows:
1. Vector is thread-safe
2. ArrayList growth is inconsistent with Vector growth
Others, if the construction methods are inconsistent, Vector can initialize capacityIncrement through the construction method, and there are other methods, such as the indexOf method. Vector supports search and search from the specified location; in addition, Vector also has some redundant methods with duplicate functions, such as the addElement and setElementAt method. The reason for this is due to historical reasons. For example, the addElement method is left behind before. When the collection framework was introduced, Vector joined the collection family and changed to implement the List interface. Some methods defined in the List interface need to be implemented. However, for compatibility reasons, the old methods cannot be deleted, so some old methods with redundancy appeared. Now it has been replaced by ArrayList and is basically rarely used, so just understand.
Stack class
The basic operation of the stack is realized. The method is as follows:
public Stack();
Create an empty stack
public synchronized E peek();
Returns the value at the top of the stack;
public E push(E item);
Stack operation;
public synchronized E pop();
Out-stack operation;
public boolean empty();
Determine whether the stack is empty;
public synchronized int search(Object o);
Returns the position of the object in the stack;
For the above stack, we will basically only use the above method frequently. Although it inherits Vector and has many methods, it basically won't be used, but it is just treated as a stack.
3. Basic use
Some methods in Vector are used as follows. In addition, the traversal method of Vector is the same as that of ArrayList. You can use foreach, iterator, and for loop traversal;
import java.util.Arrays;import java.util.Iterator;import java.util.List;import java.util.ListIterator;import java.util.Vector;public class Test { public static void main(String[] args) { Vector<Integer> vector = new Vector<Integer>(); for(int i = 0; i < 10; i++){ vector.add(i); } //Print System.out.println(vector.toString()); //size() System.out.println(vector.size()); //contains System.out.println(vector.contains(2)); //iterator Iterator<Integer> iterator = vector.iterator(); while(iterator.hasNext()){ System.out.print(iterator.next() + " "); } //toArray Object[] objArr = vector.toArray(); System.out.println("/nobjArr:" + Arrays.asList(objArr)); Integer[] intArr = vector.toArray(new Integer[vector.size()]); System.out.println("intArr:" + Arrays.asList(intArr)); //add vector.add(5); //remove vector.remove(5); System.out.println(vector); //containsAll System.out.println(vector.containsAll(Arrays.asList(5,6))); //addAll vector.addAll(Arrays.asList(555,666)); System.out.println(vector); //removeAll vector.removeAll(Arrays.asList(555,666)); System.out.println(vector); //addAll method vector.addAll(5, Arrays.asList(666,666, 6)); System.out.println(vector); //get method System.out.println(vector.get(5)); //set method vector.set(5, 55); System.out.println(vector.get(5)); //add method vector.add(0, 555); System.out.println(vector); //remove method vector.remove(0); System.out.println(vector); //indexof method System.out.println(vector.indexOf(6)); //lastIndexOf method System.out.println(vector.lastIndexOf(6)); //listIterator method ListIterator<Integer> listIterator = vector.listIterator(); System.out.println(listIterator.hasPrevious()); //listIterator(index) method ListIterator<Integer> iListIterator = vector.listIterator(5); System.out.println(iListIterator.previous()); //subList method System.out.println(vector.subList(5, 7)); //clear vector.clear(); System.out.println(vector); }}Some methods in Stack are used as follows. Because Stack inherits Vector, Stack can also use methods that Vector can use. The following lists some examples of Stack's unique methods. It is very simple, which are some basic operations of the stack. In addition to several traversal methods of Vector, stack also has its own unique traversal methods (using the empty method and the pop method to achieve traversal from the top to the bottom of the stack):
import java.util.Stack;public class Test { public static void main(String[] args) { Stack<Integer> stack = new Stack<Integer>(); for(int i = 0; i < 10; i++){ stack.add(i); } System.out.println(stack); System.out.println(stack.peek()); stack.push(555); System.out.println(stack); System.out.println(stack.pop()); System.out.println(stack); System.out.println(stack.empty()); System.out.println(stack.search(6)); System.out.println("stack traversal: "); while(!stack.empty()){ System.out.print(stack.pop() + " "); } }}Subsection:
Vector is thread-safe, but has poor performance. Generally, ArrayList is used unless there are special requirements;
If you plan to use Stack as the stack, you should honestly and strictly follow the several operations of the stack. Otherwise, it would be meaningful to use stack, and it would be better to use Vector;
2. Vector&Stacke's structure and underlying storage
public class Vector<E>extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
Vector is an implementation class of List. In fact, Vector is also a List container based on array implementation. Its functions and implementation code are basically the same as ArrayList. So what is different? One is that 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. The thread-safe approach of Vector is to add a synchronized keyword to each method to ensure it. But here, Vector is no longer officially (recognized by everyone) and is not recommended. It is officially because its thread safety method is to lock the entire method, which leads to low efficiency. So is there a better solution? In fact, it cannot be said that there is one, but there is really one, Collections.synchronizedList()
Since Stack is inherited and based on Vector, let’s take a look at some definitions and method source codes of Vector:
// The underlying layer uses an array to store data protected Object[] elementData; // The number of elements protected int elementCount ; // Customize the container expansion and increment size protected int capacityIncrement ; public Vector( int initialCapacity, int capacityIncrement) { super(); // Exit bounds check if (initialCapacity < 0) throw new IllegalArgumentException( "Illegal Capacity: " + initialCapacity); // Initialize the array this.elementData = new Object[initialCapacity]; this.capacityIncrement = capacityIncrement; } // Use the synchronized keyword lock method to ensure that only one thread can manipulate the method at the same time public synchronized boolean add(E e) { modCount++; // Enlargement check ensureCapacityHelper( elementCount + 1); elementData[elementCount ++] = e; return true; } private void ensureCapacityHelper(int minCapacity) { // Current number of elements int oldCapacity = elementData .length; // Is it necessary to expand capacity if (minCapacity > oldCapacity) { Object[] oldData = elementData; // If the container expansion is customized, expand capacity according to capacityIncrement, otherwise expand capacity by twice (*2) int newCapacity = (capacityIncrement > 0) ? (oldCapacity + capacityIncrement) : (oldCapacity * 2); if (newCapacity < minCapacity) { newCapacity = minCapacity; } // Array copy elementData = Arrays.copyOf( elementData, newCapacity); } }Vector simply see this. If the other Stack method is not called, it will not be analyzed. If you don’t understand, you can check the ArrayList source code analysis.
3. Analysis of main methods
1.peek() - Get the object at the top of the stack
/** * Get the object at the top of the stack, but do not delete */ public synchronized E peek() { // The current number of container elements int len = size(); // If there is no element, throw an exception directly if (len == 0) throw new EmptyStackException(); // Call elementAt method to retrieve the last element of the array (the last element is at the top of the stack) return elementAt(len - 1); } /** * Get the element at this position according to the index index, this method is in Vector*/ public synchronized E elementAt(int index) { // Exit the bounds if (index >= elementCount ) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } // Get the element return (E)elementData [index]; }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
/** * Bumble the stack, get and delete the object at the top of the stack*/ public synchronized E pop() { // Record the object at the top of the stack E obj; // The current number of container elements int len = size(); // Get the object at the top of the stack obj through peek() method obj = peek(); // Call the removeElement method to delete the object at the top of the stack removeElementAt(len - 1); // Return to the object at the top of the stack return obj; } /** * Delete the element according to the index index*/ public synchronized void removeElementAt(int index) { modCount++; // Exit bounds if (index >= elementCount ) { throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount); } else if (index < 0) { throw new ArrayIndexOutOfBoundsException(index); } // Calculate the number of array elements to be moved int j = elementCount - index - 1; if (j > 0) { // Move the array, delete one in the middle, so move the subsequent element forward (moving here directly overwrites the index position element, which is equivalent to deletion) System. arraycopy(elementData, index + 1, elementData, index, j); } // minus 1 elementCount--; // Set the last element of the container to empty (because an element was deleted, and the elements behind the index were moved forward, so the last one was useless) elementData[elementCount ] = null; /* to let gc do its work */ }3.push(E item) - push (into the stack), add the object into the container and return it
/** * Add the object into the container and return */ public E push(E item) { // Call addElement to addElement(item); // Return the element return item; } /** * Add the element into the container. This method is in Vector*/ public synchronized void addElement(E obj) { modCount++; // Enlargement check ensureCapacityHelper( elementCount + 1); // Put the object into the array, the number of elements +1 elementData[elementCount ++] = obj; }4.search(Object o) - Returns the position of the object in the container, the top of the stack is 1
/** * Return the position of the object in the container, the top of the stack is 1 */ public synchronized int search(Object o) { // Find the element from the array, from the last occurrence of int i = lastIndexOf(o); // Because the top of the stack counts 1, you need to use size()-i to calculate if (i >= 0) { return size() - i; } return -1; }5.empty() - Is the container empty
/** * Check whether the container is empty*/ public boolean empty() { return size() == 0; }Subsection:
At this point, the Stack method is analyzed. Since Stack is ultimately based on arrays, it is still easy to understand (because it is based on ArrayList).
Although the source code of Stack in jdk has been analyzed, it is necessary to discuss it here. I don’t know if I found that Stack here is very strange.
(1) Why is Stack implemented based on arrays?
We all know the characteristics of arrays: they are convenient for querying based on subscripts (random access), but the memory is fixed and the capacity expansion efficiency is low. It is easy to think of the most suitable thing for Stack to use linked lists.
(2) Why does Stack inherit Vector?
Inheritance means that Stack inherits the Vector method, which makes Stack feel a bit inappropriate, both a List and a Stack. What should be a reasonable approach if you have to inherit Vector: Stack does not inherit Vector, but only has a reference to Vector itself, is the aggregation right?
The only explanation is that Stack was created by jdk1.0. At that time, the containers in jdk did not have only Vectors, such as ArrayList, LinkedList, etc., and since they already have Vector and can implement Stack functions, then do it. . . Since it is ideal to implement Stack with linked lists, let's try it:
import java.util.LinkedList; public class LinkedStack<E> { private LinkedList<E> linked ; public LinkedStack() { this.linked = new LinkedList<E>(); } public E push(E item) { this.linked .addFirst(item); return item; } public E pop() { if (this.linked.isEmpty()) { return null; } return this.linked.removeFirst(); } public E peek() { if (this.linked.isEmpty()) { return null; } return this.linked.getFirst(); } public int search(E item) { int i = this.linked.indexOf(item); return i + 1; } public boolean empty() { return this.linked.isEmpty(); }}The Stack implemented by LinkedList is used here. Remember as mentioned in LinkedList, LinkedList implements the Deque interface so that it can be used as a stack (first in and out) and a queue (first in and out).
4. The difference between Vector&ArrayList
There are three implementation classes in the List interface, namely ArrayList, Vector and LinkedList. List is used to store multiple elements, can maintain the order of elements, and allows repetition of elements.
The relevant differences between the three specific implementation classes are as follows:
1. ArrayList is the most commonly used List implementation class, internally implemented through arrays, which allows fast random access to elements. The disadvantage of arrays is that there cannot be spaced between each element. When the array size is not satisfied, the storage capacity needs to be increased. It is necessary to say that the data of the already-array is copied to the new storage space. When inserting or deleting elements from the middle position of the ArrayList, the array needs to be copied, moved, and the cost is relatively high. Therefore, it is suitable for random lookups and traversals, not for insertion and deletion.
2.Vector is also implemented through arrays, the difference is that it supports thread synchronization, that is, at a certain moment, only one thread can write a Vector to avoid inconsistency caused by multiple threads writing at the same time, but it costs a lot to implement synchronization, so accessing it is slower than accessing ArrayList.
3. LinkedList uses a linked list structure to store data, which is very suitable for dynamic insertion and deletion of data, and the random access and traversal speeds are relatively slow. In addition, it also provides methods that are not defined in the List interface, which are specifically used to operate table header and tail elements, and can be used as stacks, queues and bidirectional queues.
5. A brief understanding of queue queue, double-ended queue Deque
1. Queue
A new java.util.Queue interface has been added to java5 to support common queue operations. This interface extends the java.util.Collection interface.
public interface Queue<E> extends Collection<E>
In addition to basic Collection operations, queues provide other insert, extract, and check operations.
Each method has two forms: one throws an exception (when an operation fails), and the other returns a special value (null or false, depending on the operation).
Queues usually (but not necessarily) sort individual elements in a FIFO (first in first out). However, the priority queue and LIFO queue (or stack) are exceptions. The former sorts the elements according to the natural order of the provided comparator or elements, and the latter sorts the elements in LIFO (latest in first out).
In the FIFO queue, all new elements are inserted at the end of the queue, and the removal element is removed from the queue header.
When using Queue, try to avoid the add() and remove() methods of Collection, but use offer() to add elements and use poll() to get and remove elements. Their advantage is that they can determine whether the success is achieved by returning the 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() method.
The offer method can insert an element, otherwise it returns false. This is different from the Collection.add method, which can only fail to add elements by throwing an unchecked exception.
The remove() and poll() methods remove and return the queue's header. Which element is removed 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 queue header.
Queue implementations generally do not allow insertion of null elements, although some implementations (such as LinkedList) do not prohibit insertion of nulls. Even in implementations that allow null, null should not be inserted into the Queue, because null is also used as a special return value for 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.
import java.util.Queue; import java.util.LinkedList; public class TestQueue { public static void main(String[] args) { Queue<String> queue = new LinkedList<String>(); queue.offer("Hello"); queue.offer("World!"); queue.offer("Hello!"); System.out.println(queue.size()); String str; while((str=queue.poll())!=null){ System.out.print(str); } System.out.println(); System.out.println(queue.size()); } }2. Deque
public interface Deque<E> extends Queue<E>
A linear collection that supports insertion and removal of elements at both ends.
The name deque is the abbreviation of "double ended queue" and 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 capacity-limited queues and dual-ended queues without fixed size limits.
This interface defines a method to access elements on both ends of a double-ended queue. Provides methods to insert, remove and inspect elements. Because this interface inherits the queue interface Queue, there are two forms for each of its methods: one throws an exception when the operation fails, and the other returns a special value (null or false, depending on the operation).
a. When using a double-ended queue as a queue, you will get FIFO (first-in, first-out) behavior. Add an element to the end of the double-ended queue and remove the element from the beginning of the double-ended queue. Methods inherited from the Queue interface are completely equivalent to the Deque method, as shown in the following table:
b. Used as LIFO (Last In First Out) stack. This interface should be used first rather than legacy Stack classes. When using a double-ended queue as a stack, the element is pushed into the beginning of the double-ended queue and pops up from the beginning of the double-ended queue. The stack method is completely equivalent to the Deque method, as shown in the following table: