Data Structure-Linear Table-In-depth explanation

/**
* Array implementation
*/
public class ArrayStack {<!-- -->
private int[] nums; // array
private int count; //The number of elements in the stack
// Initialize the array and apply for an array space of size n
public ArrayStack(int n) {<!-- -->
this.nums = new int[n];
this.count = 0;
}
// push operation
public boolean push(int n) {<!-- -->
// The array space is not enough, so it returns false directly and the push to the stack fails. No expansion
//nums.len*2 arraycopy
if (count >= nums.length) return false;
//Put the item at the position whose subscript is count, and add one to count
nums[count] = n;
count + + ;
return true;
}
// Pop operation
public int pop() {<!-- -->
// If the stack is empty, return 0 directly.
if (count == 0) return 0;
//Return the array element with index count-1, and the number of elements in the stack, count, is reduced by one.
int n = nums[count-1];
count--;
Linked list implementation
return n;
}
public static void main(String[] args) {<!-- -->
ArrayStack as=new ArrayStack(8);
as.push(3);
as.push(5);
as.push(1);
as.push(4);
System.out.println(as.pop());
System.out.println(as.pop());
System.out.println(as.pop());
System.out.println(as.pop());
}
}

/**
* Linked list node
*/
public class Node {<!-- -->
int value;
Node next;
public Node(int value) {<!-- -->
this.value = value;
}
}
/**
* Linked list implementation
*/
public class LinedStack {<!-- -->
int size;
Node head; //head node
/**
* initialization
*/
public LinedStack() {<!-- -->
head = null;
size = 0;
}
/**
time complexity
* push to stack
*
* @param node
*/
public void push(Node node) {<!-- -->
//head
if (size == 0) {<!-- -->
head = node;
}
//Non-head
else {<!-- -->
node.next = head;
head = node;
}
size + + ;
}
/**
* pop
*
* @return Node
*/
public Node pop() {<!-- -->
if (size > 0) {<!-- -->
Node oldHead = head;
head = head.next;
size--;
return oldHead;
} else {<!-- -->
return null;
}
}
public static void main(String[] args) {<!-- -->
Node n1=new Node(3);
Node n2=new Node(5);
Node n3=new Node(1);
Node n4=new Node(4);
LinedStack ls=new LinedStack();
ls.push(n1);
ls.push(n2);
ls.push(n3);
ls.push(n4);
System.out.println(ls.pop().value);
System.out.println(ls.pop().value);
System.out.println(ls.pop().value);
System.out.println(ls.pop().value);
}
}

4. Queue
   1. Concept: A queue is a linear data structure. The elements in the queue can only be First In First Out (FIFO). The exit end of the queue is called the front, and the entry end of the queue is called the rear.
   2. Time complexity: Both enqueueing and dequeuing are O(1)
   3. Code

/**
* Queue implemented with array
*/
public class ArrayQueue {<!-- -->
//Array: items, array size: n
int[] nums;
// head represents the subscript of the head of the team, and tail represents the subscript of the tail of the team.
int head = 0;
int tail = 0;
//Apply for an array of size capacity
public ArrayQueue(int size) {<!-- -->
nums = new int[size];
}
//Enqueue
public boolean enqueue(int n) {<!-- -->
Linked list implementation
// If tail == n it means the queue is full
if (tail == nums.length) return false;
nums[tail] = n;
 + + tail;
return true;
}
// Dequeue
public int dequeue() {<!-- -->
// If head == tail means the queue is empty
if (head == tail) return 0;
int ret = nums[head];
 + + head;
return ret;
}
public static void main(String[] args) {<!-- -->
ArrayQueue aq=new ArrayQueue(8);
aq.enqueue(3);
aq.enqueue(5);
aq.enqueue(1);
aq.enqueue(4);
System.out.println(aq.dequeue());
System.out.println(aq.dequeue());
System.out.println(aq.dequeue());
System.out.println(aq.dequeue());
}
}

import com.lagou.line.queue.Node;
/**
* Linked list implementation
*/
public class LinkedQueue {<!-- -->
Node head;
Node tail;
int size;
public void enqueue(Node node){<!-- -->
if (tail == null){<!-- -->
head = node;
tail=node;
}else {<!-- -->
tail.next = node;
tail = node;
}
size + + ;
time complexity
Enqueue and dequeue are both O(1)
application
Resource pool, message queue, command queue, etc.
Section 2 Hash Table
concept
A hash table is also called a hash table. This data structure provides a mapping relationship between keys and values. if only
Given a Key, you can efficiently find the Value it matches, and the time complexity is close to O(1).
}
public Node dequeue (){<!-- -->
if (head == null) return null;
Node h = head;
//Change the next node of the pulled node into the new header
head = head.next;
//Set the next node pointer of the old table header to null and let gc recycle it.
h.next = null;
//Queue is empty
if (head == null)
tail = null;
size--;
return h;
}
public static void main(String[] args) {<!-- -->
Node n1=new Node(3);
Node n2=new Node(5);
Node n3=new Node(1);
Node n4=new Node(4);
LinkedQueue lq=new LinkedQueue();
lq.enqueue(n1);
lq.enqueue(n2);
lq.enqueue(n3);
lq.enqueue(n4);
System.out.println(lq.dequeue().value);
System.out.println(lq.dequeue().value);
System.out.println(lq.dequeue().value);
System.out.println(lq.dequeue().value);
}
}

5. Hash table
   1. Concept: A hash table is also called a hash table. This data structure provides a mapping relationship between keys and values. As long as a Key is given, the matching Value can be found efficiently, and the time complexity is close to O(1).
   2. Storage principle: A hash table is essentially an array. The key of the hash table is mainly of string type. Convert Key and array subscript through hash function. Its function is to convert input of any length into a fixed type and fixed length hash value through a hash algorithm.
   3. Hash conflict (collision): Since the length of the array is limited, when more and more entries are inserted, the subscripts obtained by different keys through the hash function may be the same. In this case , is called a hash conflict.
   4. Open addressing method: The principle of open addressing method is that when a Key obtains the corresponding array subscript through the hash function and is occupied, it looks for the next gap.
      Location
   5. Linked list method: Each element of the array is not only an Entry object, but also the head node of a linked list. Each Entry object points to its next Entry node through the next pointer. When a new Entry is mapped to a conflicting array position, it only needs to be inserted into the corresponding linked list. By default, next points to null.
   6. Application: HashMap, Bloom filter.