This is the fourth day of my participation in the August More text Challenge. For details, see:August is more challenging
This series of articles is a summary of personal learning, if there are mistakes or questions, welcome to comment!
This paper is the fourth article in the relearning data structure series. The series of articles are as follows: 1. Time complexity and space complexity of algorithm 2. 3. Relearn data structures — queues
1. Introduction
- Stack, English name
stackIt is a kind ofAfter the first in and out the otherThe ordered list of. - The stack is oneinsertanddeleteA special linear table that can only be executed on one end of the linear table. Allows insertions and deletions at one end, called the change end
The Top (Top)The other end is a fixed end, calledThe Bottom of the stack (Bottom). - The first element to be put on the stack is at the bottom, and the last element to be put on the stack is at the top. The opposite is true for deleting an element: the last element to be put is deleted first, and the first element to be put is deleted last.
The following is the schematic diagram of pushing and exiting the stack:
2. Quick start on the stack
Since the stack is an ordered list, we can use an array or a linked list to simulate the stack. Here we use an array to simulate the stack operation.
Array analog stack
Train of thought
- Define arrays to store data
- Define a top to represent the top of the stack, initialized to -1(indicating that there is no data in the stack)
- Push operation, when data is added to the stack,
top++; stack[top] = data; - Stack out operation,
int value = stack[top]; top--; return value;
The specific implementation
/ class ArrayStack{private Integer maxSize; private Integer stack[]; private Integer top = -1; public ArrayStack(Integer maxSize) { this.maxSize = maxSize; stack = new Integer[maxSize]; Public Boolean isFull(){return top == maxSize-1; Public Boolean isEmpty(){return top == -1; Public void push(Integer data){// Determine whether the stack is full if(! isFull()){ top++; stack[top] = data; }} public Integer pop(){// check whether the stack isEmpty if(isEmpty()){throw new RuntimeException(" the stack isEmpty, there is no data to be left "); } int value = stack[top--]; return value; Public void list(){if(isEmpty()){system.out.println (" the stack isEmpty, there is no data ~~~~"); return; } for (int i = top; i >-1 ; i--) { System.out.printf("stack[%d]=%d\n",i,stack[i]); }}}Copy the codeTesting:
public static void main(String[] args) { ArrayStack stack = new ArrayStack(5); stack.push(2); stack.push(3); stack.push(4); stack.push(6); stack.push(7); stack.list(); System.out.println(); System.out.println(" stack data is: "+stack.pop())); System.out.println(); stack.list(); }}Copy the code3. Queues in Java
Java Queue top-level interface, source as follows:
Public interface Queue<E> extends Collection<E> {/** * extends Collection<E> IllegalStateException * Inserts the specified elements into this queue if it is possible to do so * immediately without violating capacity restrictions, returning * {@code true} upon success and throwing an {@code IllegalStateException} * if no space is currently available. * * @param e the element to add * @return {@code true} (as specified by {@link Collection#add}) * @throws IllegalStateException if the element cannot be added at this * time due to capacity restrictions * @throws ClassCastException if the class of the specified element * prevents it from being added to this queue * @throws NullPointerException if the specified element is null and * this queue does not permit null elements * @throws IllegalArgumentException if some property of this element * prevents it from being added to this queue */ boolean add(E e); /** * add an element to the queue, return true on success, Inserts the specified elements into this queue if it is possible to do * so immediately without violating money capacity restrictions. * When using a capacity-restricted queue, this method is generally * preferable to {@link #add}, which can fail to insert an element only * by throwing an exception. * * @param e the element to add * @return {@code true} if the element was added to this queue, else * {@code false} * @throws ClassCastException if the class of the specified element * prevents it from being added to this queue * @throws NullPointerException if the specified element is null and * this queue does not permit null elements * @throws IllegalArgumentException if some property of this element * prevents it from being added to this queue */ boolean offer(E e); /** * remove and return the queue header element, Retrieves and removals the head of this queue. This method addressed * from {@link #poll poll} only in that it throws an exception if this * queue is empty. * * @return the head of this queue * @throws NoSuchElementException if this queue is empty */ E remove(); /** * remove and return the queue header element, Return null * Retrieves and removals the head of this queue if the queue is empty, * or returns {@code null} if this queue is empty. * * @return the head of this queue, or {@code null} if this queue is empty */ E poll(); /** * return the queue header element, Retrieves, but does not remove, the head of this queue. This method * differs from {@link #peek peek} only in that it throws an exception * if this queue is empty. * * @return the head of this queue * @throws NoSuchElementException if this queue is empty */ E element(); /** return the column header element, If the queue is empty null * Retrieves, but does not remove, the head of this queue, * or returns {@code null} if this queue is empty. * * @return the head of this queue, or {@code null} if this queue is empty */ E peek(); }Copy the codeThe underlying implementation tree is shown below
Examples:
Queue<Integer> queue = new LinkedList<>(); / / the team queue. The add (1); Queue. Offer (2); False queue. Add (3); System.out.println(queue.peek()); System.out.println(queue.element()); Null system.out.println (queue.remove()); System.out.println(queue.poll()); // Dequeue and delete the header element. Null system.out.println (queue.poll());Copy the code4. In Java stack
There is no Stack interface in Java, but there is a Stack class, which is based on Vector. In Java, it is more recommended to use the implementation class of Deque to complete the stack operation, because the Vector related methods are implemented by locking, which is relatively inefficient. Deque related stack source code is as follows:
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | other * words, at the head of this deque) if it is possible to do so * immediately without violating capacity restrictions, throwing an * {@code IllegalStateException} if no space is currently available. * * <p>This method is equivalent to {@link #addFirst}. * * @param e the element to push * @throws IllegalStateException if the element cannot be added at this * time due to capacity restrictions * @throws ClassCastException if the class of the specified element * prevents it from being added to this deque * @throws NullPointerException if the specified element is null and this * deque does not permit null elements * @throws IllegalArgumentException if some property of the specified * element prevents it from being added to this deque */ void push(E e); /** * performers represented by this deque. In other * words, removes and returns the first element of this deque. * * <p>This method is equivalent to {@link #removeFirst()}. * * @return the element at the front of this deque (which is the top * of the stack represented by this deque) * @throws NoSuchElementException if this deque is empty */ E pop(); }Copy the codeDeque inherits from Queue, and its underlying implementation tree looks like this:
Examples are as follows:
public static void main(String[] args) { Deque<Integer> stack = new LinkedList<>(); For (int I = 0; i < 10; i++) { stack.push(i); } // leave the stack while (! stack.isEmpty()){ System.out.println(stack.pop()); }}Copy the code