Linear storage structure: array + linked list + string + queue and stack
Author: write Bug My Lago https://www.bilibili.com/read/cv8480862?spm_id_from=333.999.0.0 source: bilibilili
1. Array
1. How to define arrays in java
//Define static array; Specifies the element content of the number, but does not specify the length of the array
int[] a =new int[]{1,2,3,4,5};
//Define dynamic array: specify the length of the array without specifying the contents of the array
int[] a =new int[5];
//Other syntax for defining arrays is not recommended
int arrays[] = new int[]{1,2,3,4,5}
//When defining an array in java, the length and content of the array can only be specified
//When creating an array in a dynamic way, after the virtual machine opens up space for the array, the array is not vacuum. Instead, the default value of the element is used for placeholders:
//Shaping array: byte [], short [], int [], long [] = = > 0
//Floating point array: double [], float [] = = > 0.0
//Character array: char [] space 0(utf-8)
//Reference (class or object) array: String null
//Boolean array: boolean false
//Whether the element type stored in the array is an element of basic data type or an element of reference data type, the array type itself is a reference data type
//An array object is always stored in the array variable name
2. Length of array
a.length Returns the number and length of elements in an array //index 0 //Maximum value of array subscript a.length-1 //2. Memory characteristics of array //Memory characteristics of arrays: fixed length and continuous //Fixed length means that in java, once an array object is created in memory, its length cannot be modified; If you want to change the length of an array, you can only re new an array //Continuity means that in Java, the memory addresses of all elements in the same array are continuous and regular //3. Analysis of reading and writing efficiency of array //1. Fixed length leads to slow addition and deletion //Once a java array is created in memory, its length is immutable, that is, if you need to change the length of an array, you need to recreate an array //However, in java, creating objects is a very time-consuming and memory consuming operation, so if it involves the insertion and deletion of array elements, it must involve the re creation of array objects // Creates and copies of array elements.
It can be seen that when inserting elements into an array or deleting array elements, the creation of a new array and the copy of the original elements are involved, so this operation is very slow.
3. Continuous traversal leads to fast traversal
//The memory addresses between the elements in the same array are regular, that is, we can see that these memory addresses exist continuously
//As long as it is a continuous memory address, we can directly calculate the memory address of a bit element in some way, and then access the array element
//In other words, when accessing the elements in the array through subscripts, we do not need to start from the first element of the array and query backward one by one. We just need to calculate the memory address of the target element according to these laws
//Memory address of current element = size of element + memory address
int array = new int[]{1,2,3,4,5}
The array type variable stores the address of the first element of the array
array -> 0x0010
How to quickly query the memory address with subscript 2? Known condition: the first address of the array is 0 x0010 The size of a single element is 3 · Brute force solution traversal one by one · jvm Calculate memory address Summary: Java To access any array, the subscript is n Calculation formula of memory address of element: Fast random access formula Subscript in array is n The memory address of the element=The first address of the array with subscript 0+(Subscript of target element n*Size of a single element)
4. Typical algorithm problems of array
1. Array reverse order
Title Description: Re store all the elements in an array in an inverted order in the array. Title Case: Given array:[1,4,2,7,5,9,6] Reverse order storage:[6,9,5,7,2,4,1] Train of thought analysis: Use two variables i and j，Point to the starting point and the ending point of the array respectively, i Variables go back, j Variable forward; In the process of traversing the array array[i]and array[j]The element values in are interchanged using a temporary space, and the loop condition is i < j.
package com.uin.List;
import java.util.Arrays;
/**
* @author wanglufei
* Reverse order of array
* @description: TODO
* @date 2021/11/26/8:48 morning
*/
public class ArrayMerge {
public void arrayReverse(int[] a) {
int tmp = 0;
for (int i = 0, j = a.length - 1; i < j; i++, j--) {
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
public static void main(String[] args) {
int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};
System.out.println(Arrays.toString(a));
ArrayMerge merge = new ArrayMerge();
merge.arrayReverse(a);
System.out.println(Arrays.toString(a));
}
}
2. Ordered array merging
Title Description: Given two ascending ordered arrays, merge the two arrays into an ascending ordered array Title Case: Given two arrays in ascending order: arr1 = [1,2,4,4,6,8,9] arr2 = [0,1,3,6,7] The combined result is:[0,1,1,2,3,4,4,6,6,7,8,9] Train of thought analysis: Use two variables i and j Traverse the array separately arr1 And array arr2，Comparison during traversal arr1[i]and arr2[j]And drop a smaller element in the result array; Which array element falls in the result array, and which array subscript advances 1. Until one array is traversed first, all the remaining elements in the other array can be placed in the result array.
package com.uin.sort;
import java.util.Arrays;
/**
* @author wanglufei
* Sort and merge ordered arrays
* @description: TODO
* @date 2021/11/24/10:00 afternoon
*/
public class SortedArrayMerge {
public static void main(String[] args) {
int[] a = new int[]{1, 3, 4, 5, 7};
int[] b = new int[]{0, 1, 5, 7, 7, 8, 9};
SortedArrayMerge sam = new SortedArrayMerge();
int[] result = sam.sortedArrayMerge(a, b);
System.out.println(Arrays.toString(result));
}
public int[] sortedArrayMerge(int[] a, int[] b) {
//Create a result array whose length is the sum of the lengths of two ordered arrays
int m = a.length;
int n = b.length;
int[] meragee = new int[m + n];
//Create pointers i, j. Used to traverse A and B, respectively
int i = 0;
int j = 0;
//Create a pointer k to control the subscript of the element of the result array
int k = 0;
//Create circular variables to realize the operation of merging ordered arrays. In the process of merging, compare the sizes of A[i] and B[j]. Whoever is smaller will fall in the knot array
//And, after the element of which array falls in the result array, the pointer controlling the array will add + 1
while (i < m && j < n) {
if (a[i] <= b[j]) {
meragee[k] = a[i];
i++;
} else {
meragee[k] = b[j];
j++;
}
k++;
}
//To determine which array has remaining elements, copy these remaining elements directly into the result array
if (i < m) {
while (i < m) {
meragee[k] = a[i];
i++;
k++;
}
}
if (j < n) {
while (j < n) {
meragee[k] = b[j];
j++;
k++;
}
}
return meragee;
}
}
2. Linked list
//1. The node of the linked list is generally divided into two parts: the data field, which is used to store the data to be saved, such as a string, a User object, etc;
//The next pointer field is used to save the memory address of the next node and string the whole linked list
//2. In the linked list, the first node of the linked list usually does not store any data. It is only used to cause the whole linked list. We call this special node the head node of the array.
//3. In the whole linked list, as long as we know the memory address of the chain header node, we can find all subsequent nodes one by one down the next pointer field of each subsequent node
//4. The value of the subsequent pointer field of the last node in the linked list is null. This feature is often used to judge whether there are subsequent nodes when traversing the whole linked list
It's like a train
The locomotive is not a passenger
Passengers start from the next carriage of the locomotive
next The pointer field is like connecting the carriage🪝
If a car🪝There are no other cars attached at the back, which means this car is the last one
//In java
public class Node {
Object data;//Data domain
Node next;//The next pointer is the successor pointer field, which is used to save the memory address of the next node of the current node
}
1. Basic concept of linked list
//In java, the reference saves the memory address //The next subsequent pointer field is also a memory address
2. Basic operation of linked list
package com.uin.linked;
/**
* @author wanglufei
* @description: TODO
* @date 2021/11/27/9:04 morning
*/
public class MyLinked {
//Inner class
public static class Node {
Object data;
Node next;
}
//The head node does not store any data
private Node head = new Node();
//Append an element to the last position of the linked list
public void append(Object data) {
//1 create a variable to traverse the current linked list until the last node in the current linked list is found. This temporary variable points to the head node of the linked list at the beginning
Node cur = head;
//2. Find the last node in the current linked list through a loop. The loop condition is that the next pointer field of the temporary variable pointing to the node is not null
while (cur.next != null) {
cur = cur.next;
}
//3 encapsulate the additional elements in a Node of type Node
Node node = new Node();
node.data = data;
//4 add the new node to the last node of the linked list through the last node pointed to by the temporary variable in step 2
cur.next = node;
}
//Inserts an element at the specified subscript position in the linked list
public void insert(Object data, int index) {
//Create a pedometer with an initial value of 0. It is used to record the jump times of cur, a temporary variable, as a reference to find the loop of node insertion position
int step = 0;
//Create cur temporary variable to traverse the nodes in the linked list. The initial value is head
Node cur = head;
//Create a loop to find the insertion position of the new node. The loop condition is step < index
while (step < index) {
cur = cur.next;
step++;
}
//At the end of the loop, our cur points to the previous node of the location to be inserted
//Create a new node to save the inserted data. The name of the new node is defined as node
Node node = new Node();
node.data = data;
//Perform the insertion operation of the new node
//Now the next and cur of the new node node Next generation relationship
//Then cur and cur Next hook disconnected
node.next = cur.next;//The post pointer field of the new node points to the original node after the insertion position in the linked list
cur.next = node;//The node before the insertion position is separated from the original node, and points to the new node to complete the insertion of the new node
}
//Traversal linked list
public void iterate() {
Node cur = head;
while (cur.next != null) {
cur = cur.next;
System.out.println(cur.data);
}
}
//The specified index returns the elements in the linked list
public Object get(int index) {
//1. Create pedometer variables to record the number of jumps of cur variables in the linked list and control the conditions of the cycle
int step = 0;
//2. Create a cur variable with the initial value pointing to the head node, which is used to traverse each node of the linked list
Node cur = head;
//3. Create a loop, refer to the relationship between pedometer variable value and target node subscript value, and control the jump of cur variable
while (step - 1 < index) {
cur = cur.next;
step++;
}
//4. Return the value of the data field in the target subscript node pointed to by the cur variable
return cur.data;
}
//Specifies the subscript to delete the elements in the linked list
public void remove(int index) {
//1. Create pedometer variables to record the number of jumps of cur variables in the linked list and control the conditions of the cycle
int step = 0;
//2. Create a cur variable with the initial value pointing to the head node, which is used to traverse each node of the linked list
Node cur = head;
//3. Create a loop, refer to the relationship between pedometer variable value and target node subscript value, and control the jump of cur variable
while (step < index) {
cur = cur.next;
step++;
}
cur.next=cur.next.next;
}
public static void main(String[] args) {
MyLinked linked = new MyLinked();
linked.append("aaa");//0
linked.append("bbb");//1
linked.append("ccc");//2
linked.append("ddd");//3
linked.append("eee");//4
linked.append("fff");//5
linked.remove(2);
// linked.insert("222", 3);
linked.iterate();
// System.out.println(linked.get(2));//ccc
}
}
3. Memory characteristics of linked list
②Memory characteristics of linked list:Indefinite and discontinuous The memory characteristics of linked lists are just the opposite of arrays. In a word, it is summarized as follows:Indefinite and discontinuous Variable length means that the number of nodes in the linked list is dynamically allocated in memory,-How many nodes exist in a linked list structure, take It depends on how many elements we add to the list If we want to add an element or insert an element into the linked list, we just need to create a new node to save the element, And change several reference values to complete the operation There is no need to rebuild the whole linked list, let alone copy any elements in the original linked list Discontinuity means that every time a new element is added to the linked list, the nodes of the linked list are restarted new Come out As you know, every time new Even if the data types of the objects are the same, the memory addresses between them are also mutually exclusive It doesn't matter That is, even if it is stored in the same-The memory addresses of different nodes in a linked list are also irregular,Discontinuity of thus,If we want to traverse all the nodes in the linked list, or find a specific node in the linked list according to the subscript, then we don't Not every-Start from the head node of the linked list again Traverse the nodes one by one to find the desired elements Continuous linked list leads to slow random access
4. Other linked lists: double linked list and circular linked list
1. Look for each other before and after: double linked list
If we define two pointer fields in the nodes of the linked list, one pointing to the next node of the current node and the other pointing to the previous node of the current node, then we can traverse the linked list from the front and back directions, resulting in a double linked list structure.
2. End to end connection: circular linked list
If the subsequent pointer field of the last node of a linked list does not point to null, but directly points back to the first node storing data, then this structure forms a ring linked list structure, also known as a circular linked list. Circular linked list structure has a lot of applications in scenarios such as disk simulation algorithm and solving Joseph Ring problem.
5. Typical questions of linked list
1. Add a new element to the linked list
Title Description: Add a new element to the last side of a single linked list structure Title Case: Original linked list structure: abc -> bcd -> cde -> def Append new element: efg Get the linked list structure: abc -> bcd -> cde -> def -> efg Train of thought analysis: Define a in the package class of the linked list Node Variable of type lastNode，Used to always point to the last node. When adding elements to the linked list, it is used directly lastNode It is more convenient to operate.
2. Insert new elements into the linked list
Title Description: Inserts a new element into the specified subscript of the linked list Title Case: Original linked list structure: abc -> bcd -> cde -> def Insert a new element to the position with subscript 2 in the linked list efg Get the linked list structure: abc -> bcd -> efg -> cde -> def Train of thought analysis: First, traverse the linked list to find the position with subscript 2. Create a new node to save data, and add the new node to the specified location by modifying the subsequent pointer field.
3. Traversal of linked list
Title Description: Start from the first node in the linked list that stores data, and traverse all nodes in the linked list backward The data saved in the node data field is obtained and printed out Title Case: Linked list structure: abc -> bcd -> cde -> def Printout:[abc bcd cde def ] Train of thought analysis: Start from the next node of the chain header node, that is, the node that really stores elements in the chain list, traverse the nodes one by one, obtain the data in the node data field, and print out. The value of the subsequent pointer field of the last node in the linked list is null Control the traversal process of the linked list.
3. Typical applications of arrays and linked lists in Java
1.ArrayList - typical encapsulation of arrays
ArrayList Type uses a Object[] Type to store data. Structurally, this is a typical encapsulation of array structure, and in order to improve the efficiency of adding elements, ArrayList An object of type is initially given a length of 10 Object[]Array to store elements. It is worth saying that in jdk1.8 If used ArrayList If you create an object with an empty constructor, the default length of this array is 0, only the first time ArrayList It will be expanded to 10 only when the element is added in. If the length of this array is not enough, then ArrayList The array will be expanded, and the expansion method is not to simply add an element space. Instead, the length of the array is extended to the original 1.5 Times, that is, ArrayList The default extension method of internal array length is: 10->15->22->33->49->... Capacity expansion mechanism: 1.ArrayList() An array of length 0 will be used 2.ArrayList(int initialCapacity)An array of the specified capacity will be used 3.public ArrayLisy(Collection<? extends E > c)Can use c As the capacity of the array 4.add(Object 0)The first capacity expansion is 10, and the second capacity expansion is 1 of the last capacity.5 times 5.addAll(Collection c)When there are no elements, the expansion is Math.max(10,Number of actual elements)，When there are elements Math.max(Original capacity 1.5 Times, actual number of elements) 6.trimToSize() Prevent too much expansion from wasting space and shrinking capacity elementData=(size==0)? EMPTY_ELEMENTDATA:Arrays.copyOf(elementData,size); Interview questions: I'll give you an empty one ArrayList How many times can an object be expanded to accommodate 50 elements? elementData.length >= 50 0->10->15->22->33->49 Interpretation: 15->22 15*1.5 = 22.5 Just expand to 22
2.Iterator's fail fast fail safe mechanism
ArrayList yes fail-fast A typical representative of, traversal can not be modified at the same time, and fail as soon as possible Vector And thread safe CopyOnWriteArrayList yes fail-safe The typical representative of traversal can be modified at the same time because of read-write separation Iterators are used to prevent others from modifying while traversing fail-fast Once it is found that the traversal is modified by others, an exception is thrown immediately ConcurrentModificationException Concurrent modification exception ArrayList enhance for So is the bottom layer of the cycle Iterator Whether the number of modifications at the beginning of the loop is consistent with that in the middle of the loop to determine whether an exception is thrown fail-safe When the traversal is found and modified by others, there should be coping strategies, such as sacrificing consistency to complete the whole traversal. CopyOnWriteArrayList CowIterator To traverse Someone added elements in the middle, but they didn't really add them Adding an array is traversing another array
3.LinkedList -- typical encapsulation of linked list
LinkedList A double linked list is used internally to save data
The reason for using a double linked list is that, as mentioned earlier, you can traverse the linked list from the two directions of the chain header and the chain tail
In this way, whether it is to find the elements in the linked list or add new elements to the specified position of the linked list, it can improve a certain efficiency and save time.
High frequency interview questions:
1.LinkedList The internal is realized through linked list. What is the type of linked list used?===>Double linked list
2.Java What are the interfaces of single elements in?
Collection:
List:Ordered and repeatable
Set: Unordered and unrepeated
Queue: Queue interface
Deque:
LinkedList
4. Small case: efficiency comparison between ArrayList and LinkedList in element addition, deletion and traversal
package com.uin.List;
import java.util.ArrayList;
import java.util.LinkedList;
/**
* @author wanglufei
* @description: TODO
* @date 2021/12/1/6:50 afternoon
*/
public class TestSpeed {
public static void main(String[] args) {
long star = 0;
long end = 0;
ArrayList<Integer> l1 = new ArrayList<>();
LinkedList<Integer> l2 = new LinkedList<>();
System.out.println("-----Add efficiency test----");
System.out.println("towards ArrayList Insert 100000 elements");
star = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
l1.add(0, i);
}
end = System.currentTimeMillis();
System.out.println("Add completed, time" + (end - star) + "millisecond");
System.out.println("towards LinkedList Insert 100000 elements");
star = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
l2.add(0, i);
}
end = System.currentTimeMillis();
System.out.println("Add completed, time" + (end - star) + "millisecond");
System.out.println("-----Ergodic efficiency test----");
System.out.println("yes ArrayList Perform 100000 element lookups");
star=System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
l1.get(i);
}
end=System.currentTimeMillis();
System.out.println("yes LinkedList Perform 100000 element lookups");
star=System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
l2.get(i);
}
end=System.currentTimeMillis();
}
}
//test result
-----Add efficiency test----
towards ArrayList Insert 100000 elements
ArrayList Add complete, 496 MS
towards LinkedList Insert 100000 elements
LinkedList Add complete, 5 ms
-----Ergodic efficiency test----
yes ArrayList Perform 100000 element lookups
ArrayList，Time 1 ms
yes LinkedList Perform 100000 element lookups
LinkedList，Time 3980 MS
4. Stack and queue
Array stack and linked list stack
Array queue and linked list queue
boolean isEmpty() // Judge whether the current stack is empty
synchronized E peek() //Get current stack top element
synchronized E pop() //Get the current stack top element and delete it
E push(E object) //Add elements to the top of the stack
synchronized int search(Object o) //Find the position of the element in the stack, and count from the bottom of the stack to the top of the stack
1. Stack structure
Stack structure features: elements first in first out
The stack is characterized by first in, first out elements
That is, after we add elements to the stack structure, if we take the elements out of the stack structure, the order in which the elements come out and the order in which the elements are put into the stack structure are exactly the opposite
The operation of putting elements into the stack structure is called element stacking
The operation of taking elements out of the stack structure is called element out of the stack
The elements of the most advanced stack structure are called stack bottom elements, and this direction is also called stack bottom elements
The element that finally enters the stack structure is called the stack top element, and this method is also called the stack top element
stay Java Implementation in
Stack<String> stack = new Stack<>();
push(); Elements will be developed e Add to stack structure
pop(); Return the top element of the stack and delete this element from the stack structure; If this method is called again, the next top of the stack will be returned
peek(); Looking at the top of the stack returns the top of the stack element, but this element will not be deleted from the stack structure; If this method is called again, the stack top element will be returned twice.
2. Examples of stack structure
//Array reverse order of stack structure
package com.uin.stack;
import java.util.Arrays;
import java.util.Stack;
/**
* @author wanglufei
* Array reverse order is realized through stack structure
* @description: TODO
* @date 2021/12/1/10:10 afternoon
*/
public class ArrayReverseByStack {
public void reverse(int[] array) {
//1. Create a stack structure
Stack<Integer> stack = new Stack<>();
//2. Stack all the elements in the array
for (int i = 0; i < array.length; i++) {
stack.push(array[i]);
}
//3. Take all elements in the stack structure out of the stack and return them to the array
for (int i = 0; i < array.length; i++) {
array[i] = stack.pop();
}
}
public static void main(String[] args) {
int[] array = new int[]{1, 3, 5, 7, 9};
ArrayReverseByStack rsb = new ArrayReverseByStack();
rsb.reverse(array);
System.out.println(Arrays.toString(array));
}
}
//Stack structure decimal to binary
//Integer division to remainder
package com.uin.stack;
import java.util.Stack;
/**
* @author wanglufei
* Decimal to binary number
* @description: TODO
* @date 2021/12/2/8:44 morning
*/
public class DecimalToBinary {
public String toBinary(int num) {
//1. Create a stack structure to store the remainder generated in the process of integer division
Stack<Integer> stack = new Stack<>();
//2. Divide the remainder one by one by loop
int tmp = 0;
while (num > 0) {
tmp = num % 2;
stack.push(tmp);
num = num / 2;
}
//Out of stack
String result = "0b";
while (!stack.isEmpty()) {
result = result + stack.pop();
}
return result;
}
public static void main(String[] args) {
DecimalToBinary binary = new DecimalToBinary();
int num = 12;
String s = binary.toBinary(num);
System.out.println(s);
}
}
3. Queue
Definition of queue structure: element first in first out The characteristic of queue structure is the same as queuing in real life. First come, first come, first come, first come, first served. The elements are out of the queue according to the way they enter the queue The operation of typing elements into a queue is called putting elements into a queue The operation of taking elements out of the queue is called element out of the queue The end of the element out of the queue is called the queue head(front) The end of the queue where elements are put is called the end of the queue(rear) The queue is like a pipe. Then we block one end and put a glass ball into the pipe from the other end, and the thickness of the pipe is just enough to accommodate a glass ball. When we release the blocked end, the glass ball first put into the pipe will roll out first, and the glass ball last put into the pipe will roll out last.
4. Implementation of queue in java
Java Queue structure in: LinkedList stay Java There is also an implementation class of queue structure, which we are familiar with LinkeList type actually, Collection Under the interface, not only List and Set There are actually two sub interfaces named Queue Interface From the name, this interface itself means queue, and this interface also has a sub interface named Deque(Double ended queue) and LinkedList Class, on the one hand List Interface, on the one hand, it also implements Deque Interface, so we can think LinkedList It is a double ended queue structure realized through linked list. Note: double ended queue is a structure in which both ends can enter and exit the queue at the same time, that is, both ends are the head and tail of the queue Similarly, in LinkedList Types also provide some methods to support queue operations:
package com.uin.queue;
import java.util.LinkedList;
/**
* @author wanglufei
* @description: TODO
* @date 2021/12/2/10:05 morning
*/
public class Test {
public static void main(String[] args) {
LinkedList<String> queue = new LinkedList<>();
//Queue
queue.offer("aaa");
queue.offer("bbb");
queue.offer("ccc");
queue.offer("ddd");
queue.offer("eee");
//Look at the queue head
System.out.println(queue.peek());
System.out.println(queue.size());
System.out.println("============");
//Out of queue
queue.poll();
System.out.println(queue.peek());
System.out.println(queue.size());
//The operation of exiting an element from the end of a queue
System.out.println(queue.pollLast());
}
}
//Implement a queue with two stacks
package com.uin.queue;
import java.util.Stack;
/**
* @author wanglufei
* Implement a queue with two stacks
* @description: TODO
* @date 2021/12/2/11:33 morning
*/
public class StackQueue<E> {
private Stack<E> s1 = new Stack<E>();
private Stack<E> s2 = new Stack<E>();
public void offer(String e) {
//Directly add the elements entering the queue to the s1 stack structure
s1.push((E) e);
}
public E poll() {
//Create a variable to hold the return value
E result = null;
//1. Take the elements in s1 out of the stack except the elements at the bottom of the stack and directly put them into the stack
while (s1.size() > 1) {
s2.push(s1.pop());
}
//2. Stack the elements at the bottom of the stack exposed in s1, that is, the return value of the method
if (!s1.isEmpty()) {
result = s1.pop();
}
//3. Return all elements in s2 to s1 to ensure the order of elements added to the queue in the future
if (!s2.isEmpty()) {
while (s2.size() > 0) {
s1.push(s2.pop());
}
}
return result;
}
public static void main(String[] args) {
StackQueue<Character> sq = new StackQueue<>();
sq.offer("A");
sq.offer("B");
sq.offer("c");
sq.offer("d");
sq.offer("e");
sq.offer("f");
System.out.println(sq.poll());
System.out.println(sq.poll());
System.out.println(sq.poll());
sq.offer("f");
sq.offer("g");
sq.offer("h");
System.out.println(sq.poll());
System.out.println(sq.poll());
System.out.println(sq.poll());
System.out.println(sq.poll());
System.out.println(sq.poll());
}
}
//Stack structure with two queues
package com.uin.queue;
import java.util.LinkedList;
/**
* @author wanglufei
* Stack with two queues
* @description: TODO
* @date 2021/12/2/5:44 afternoon
*/
public class QueueStack<E> {
/**
* Implementation idea:
* 1.Add all elements to the structure's elements to the queue q1
* 2.When element e wants to exit, all elements except element E in q1 are out of the queue and added to queue q2 at the same time
* 3.The element e in queue q1 is out of the queue, and queue q1 is empty
* 4.All elements in queue q2 are sent out of the queue and back to empty queue q1
* . . . . . .
*/
private LinkedList<E> q1 = new LinkedList<>();
private LinkedList<E> q2 = new LinkedList<>();
/**
* Method of element stacking
*/
private void push(E e) {
//Queue elements directly
q1.offer(e);
}
/**
* Method of element out of stack
*/
private E pop() {
//Create a variable to hold the results
E result = null;
//1. All elements except the elements at the end of the queue are out of the queue and added to q2
while (q1.size() > 1) {
q2.offer(q1.poll());
}
//When the loop ends, the e element is left in q1
//2. The remaining queue tail elements in queue q1 are the out of stack elements, that is, the return value of the method
if (!q1.isEmpty()) {
result = q1.poll();
}
//3. Queue all elements in q2 and add them to q1 to ensure the correct order of subsequent elements out of the stack
if (!q2.isEmpty()) {
while (q2.size() > 0) {
q1.offer(q2.poll());
}
}
return result;
}
public static void main(String[] args) {
QueueStack<Object> queueStack = new QueueStack<>();
queueStack.push("A");
queueStack.push("B");
queueStack.push("C");
queueStack.push("D");
queueStack.push("E");
//Exit 3 elements of stack structure
System.out.println(queueStack.pop());
System.out.println(queueStack.pop());
System.out.println(queueStack.pop());
//Three elements are appended again
queueStack.push("F");
queueStack.push("G");
queueStack.push("H");
//All elements out of structure
System.out.println(queueStack.pop());
System.out.println(queueStack.pop());
System.out.println(queueStack.pop());
System.out.println(queueStack.pop());
System.out.println(queueStack.pop());
}
}
5. Summary of stacks and queues
frequently-used API Stack push() Element stack pop() Element out of stack peek() Look at the top of the stack queue add() Queue offfer() Queue poll() Outgoing queue
5. Summary of linear storage structure
ArrayList and LinkedList Comparison of 1.ArrayList Based on arrays, continuous memory is required Random access is fast (according to subscript access) The tail insertion and deletion performance is OK, and the insertion and deletion of other parts will move data, so the performance is reduced Can use cpu Cache, locality principle 2.LinkedList Based on bidirectional linked list, no continuous memory is required Random access is very slow (to traverse along the linked list) High head and tail insertion and deletion performance High memory consumption So in common development ArrayList More commonly used