Stack and queue data structure implementation process (Java implementation)
These reviews
- Detailed analysis of dynamic array data structure implementation process (Java implementation)
Stack of data structure implementation
Stack basics review
-
A stack is a linear structure.
-
Stack operations are subsets of arrays, as opposed to arrays.
- That is, stacks can be implemented based on arrays, and you can think of stacks as a special kind of array.
-
Elements can only be added and taken from one end of the stack, called the top.
-
A stack is a LIFO (Last In First Out) data structure.
Common use of stack
-
Undo operation
-
The system stack for program calls
Array-based stack implementation
Stack this data structure, implementation is very simple, here to achieve the following operations:
-
Void push(E Element)
-
Unstack: E pop()
-
Look at the top element: E peek()
-
Int getSize()
-
Check whether stack isEmpty: Boolean: isEmpty()
Specific implementations of code can be made to support polymorphism. So you can design an interface called Stack to define the operations supported by these five stacks, and a class called ArrayStack to implement this interface.
The ArrayStack class is essentially an Array stack based on the dynamic Array class Array that was implemented earlier. Because in the case of the stack, the operations on the stack are subsets of the array. You can think of a stack as an array.
For a detailed implementation of the Array class, check out another article I wrote earlierDetailed analysis of dynamic array data structure implementation process (Java implementation) 。
Specific code design
Before writing the code for the stack, import the dynamic Array class implemented earlier into the project. The code for the Array class can be seen in the previous article, because it is based on this class to implement the Array stack.
ArrayStack class implementation:
The Array class already implements many methods to manipulate arrays. So for the ArrayStack class to implement the methods in the interface, you just need to reuse the methods in the Array class.
Implementing the ArrayStack class based on the Array class also has some benefits:
Like Array, we have the ability to scale up and down dynamically, so we don’t need to worry about whether the stack is full or not, because it will grow and shrink dynamically.
The determination of some illegal variables is directly reused in the Array class code, does not need to be written repeatedly.
You can also add a method called getCapacity to the ArrayStack class that does not exist in the interface to provide the user with the capacity to get the stack. This method is unique to this class.
Prior to implementing peek, two new methods can be extended to the Array class to fetch elements at the end and head of an Array for direct reuse in the ArrayStack class and subsequent queue implementations.
/** * gets the last element of the array **@returnReturns the last element of the array */
public E getLast(a) {
return get(size - 1);
}
/** * gets the first element of the array **@returnReturns the first element of the array */
public E getFirst(a) {
return get(0);
}
Copy the codeThe Stack interface class code is as follows:
/** * The interface that defines the basic operation of the stack ** supports generics **@authorSnow in search of plum *@date2020/1/8 - the word * /
public interface Stack<E> {
/** * the number of elements in the stack **@returnIf there are elements in the stack, return the current number of elements in the stack. Returns 0 */ if there are no elements in the stack
int getSize(a);
/** * Checks whether the stack is empty **@returnIf the stack is empty, return true; The stack is not empty and returns false */
boolean isEmpty(a);
/** * push the element element to the top of the stack **@paramElement The pushed element */
void push(E element);
/** * pushes the current top element off the stack and returns **@returnReturns the current top stack element */
E pop(a);
/** * view the current top element **@returnReturns the current top of the stack element */
E peek(a);
}
Copy the codeThe ArrayStack class code is implemented as follows:
/** * The ArrayStack class, based on the dynamic Array class Array implemented earlier, also supports generics@authorSnow in search of plum *@date 2020/1/8 - 19:26
*/
public class ArrayStack<E> implements Stack<E> {
/** * dynamic array array * stack based operations */
private Array<E> array;
The /** * constructor creates an array stack of capacity **@paramCapacity Capacity of the stack to be created, specified by the user */
public ArrayStack(int capacity) {
array = new Array<>(capacity);
}
/** * The default constructor creates an array stack of the default size */
public ArrayStack(a) {
array = new Array<>();
}
@Override
public int getSize(a) {
// Reuse the array getSize() method
return array.getSize();
}
@Override
public boolean isEmpty(a) {
// Just reuse the array isEmpty() method
return array.isEmpty();
}
/** * Get stack capacity * ArrayStack-specific methods **@returnReturns the stack size */
public int getCapacity(a) {
// Reuse the array getCapacity() method
return array.getCapacity();
}
@Override
public void push(E element) {
// Use the addLast() method of array as the top of the stack
array.addLast(element);
}
@Override
public E pop(a) {
Using the end of the array as the top of the stack, reuse array's removeLast() method to remove the top element from the stack and return it
return array.removeLast();
}
@Override
public E peek(a) {
// Use the end of the array as the top of the stack, multiplexing array's getLast() method to get the top element
return array.getLast();
}
/** * Overrides the toString method to return stack information **@returnReturns the current information of the array stack */
@Override
public String toString(a) {
StringBuilder result = new StringBuilder();
result.append("ArrayStack: ");
result.append("size: ").append(array.getSize()).append("");
result.append("capacity: ").append(array.getCapacity()).append("");
result.append("bottom -> [ ");
for (int i = 0; i < array.getSize(); i++) {
result.append(array.get(i));
// If not the last element
if(i ! = array.getSize() -1) {
result.append(",");
}
}
result.append(" ] <- top");
returnresult.toString(); }}Copy the codeIn toString, we iterate over the stack elements just to see if the stack adds the elements correctly as we designed.
For the user, except for the top of the stack, other elements need not be known, and the user can only operate on the top of the stack element, not other elements, which is also the characteristics of the stack data structure.
Testing:
/** * Test ArrayStack **@authorSnow in search of plum *@date2020/1/8 - now * /
public class Main {
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<>();
for (int i = 0; i < 10; i++) {
/ / into the stack
stack.push(i);
// Print the loading process
System.out.println(stack);
}
// Perform a stack exit
stack.pop();
// Check the status of the stack
System.out.println(stack);
// View the current top element of the stack
Integer topElement = stack.peek();
System.out.println("Current top stack element:" + topElement);
// Check whether the stack is empty
System.out.println("Is the current stack empty:"+ stack.isEmpty()); }}Copy the codeTest results:
Array-based stack simple time complexity analysis
For the five operations implemented, their time complexity can be quickly derived from the Array class analysis in the previous article, as follows:
-
Void push(E element) : O(1) amortize
- Because the array method is reused, the resize method may be triggered to scale the capacity, so the time complexity is amortized.
-
E pop() : O(1) amortized
- Because the array method is reused, the resize method may be triggered to scale the capacity, so the time complexity is amortized.
-
E peek () : O (1)
-
Int getSize () : O (1)
-
Boolean isEmpty () : O (1)
An algorithmic application of the stack: bracket matching
Title description:
Given a string containing only '(', ')', '{', '}', '[', ']', check whether the string is valid. A valid string must meet the following requirements: The left parenthesis must be closed with the same type of the right parenthesis. The left parentheses must be closed in the correct order. Note that an empty string can be considered a valid string. Example 1: input: "()" output: true example 2: input: "() [] {}" output: true example 3: input: "[]" output: false example 4: input: "([]" output: false example 5: input: "{[]}" output: true Source: LeetCode Link: https://leetcode-cn.com/problems/valid-parentheses Copyright belongs to The Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the codeSubject analysis
This can be done using a stack
Ideas:
- The parentheses in a given string are traversed one by one.
-
If the parenthesis is an open parenthesis, it is pushed onto the stack.
-
If a close parenthesis is encountered, push the left parenthesis at the top of the stack to see if it matches the close parenthesis.
- If a match can be made, the remaining judgment continues.
- If all parentheses match, then the stack should be empty, indicating that the given string is valid.
- If no match can be made, the string is invalid.
- If a match can be made, the remaining judgment continues.
-
From the above analysis, it can be concluded that the top of the stack element reflects the closest element to be matched in the nested hierarchy.
Idea diagram:
-
A valid bracketed string icon
-
Invalid parenthesis string icon
Solution code:
-
Method 1: Use the Stack class built into the Util package.
import java.util.Stack; /** * parenthesis matching solution * Method 1: Use the Stack class built into Java's Util package to solve **@authorSnow in search of plum *@date2020/1/8-21:52 * / public class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); // Iterate over the given string for (int i = 0; i < s.length(); i++) { // Check the parentheses char c = s.charAt(i); // If the parenthesis is left parenthesis, push it to the stack if (c == '(' || c == '[' || c == '{') { stack.push(c); } else { // The parenthesis is the right parenthesis to see if it matches the top parenthesis if (stack.isEmpty()) { // If the stack is empty, there is no open parenthesis before it, the string begins with a close parenthesis, the match fails, and the string is invalid return false; } // The stack is not empty, the top bracket of the current stack is saved to the variable for matching judgment char topBracket = stack.pop(); // If the following conditions occur, the next cycle will be used to judge in turn if (c == ') '&& topBracket ! ='(') { return false; } if (c == '] '&& topBracket ! ='[') { return false; } if (c == '} '&& topBracket ! ='{') { return false; }}}// After the for loop ends, if there are characters in the stack, the remaining open brackets are not matched, and the string is invalid, otherwise the string is valid // isEmpty() returns true to indicate a successful match; If false is returned, the match fails returnstack.isEmpty(); }}Copy the code-
Submit the results
-
-
Method 2: use your own ArrayStack class
Note that you need to add your own Array class, Stack interface, and ArrayStack class as internal classes in Solution to use your own ArrayStack.
/** * parenthesis matching solution * Method 2: use your own ArrayStack class to solve **@authorSnow in search of plum *@date2020/1/8 - when the * / public class Solution { public boolean isValid(String s) { Stack<Character> stack = new ArrayStack<>(); // Iterate over the given string for (int i = 0; i < s.length(); i++) { // Check the parentheses char c = s.charAt(i); // If the parenthesis is left parenthesis, push it to the stack if (c == '(' || c == '[' || c == '{') { stack.push(c); } else { // The parenthesis is the right parenthesis to see if it matches the top parenthesis if (stack.isEmpty()) { // If the stack is empty, there is no open parenthesis before it, the string begins with a close parenthesis, the match fails, and the string is invalid return false; } // The stack is not empty, the top bracket of the current stack is saved to the variable for matching judgment char topBracket = stack.pop(); // If the following conditions occur, the next cycle will be used to judge in turn if (c == ') '&& topBracket ! ='(') { return false; } if (c == '] '&& topBracket ! ='[') { return false; } if (c == '} '&& topBracket ! ='{') { return false; }}}// After the for loop ends, if there are characters in the stack, the remaining open brackets are not matched, and the string is invalid, otherwise the string is valid // isEmpty() returns true to indicate a successful match; If false is returned, the match fails return stack.isEmpty(); } private class Array<E> {... (Code for this class omitted here)}private interface Stack<E> {... (Code for this class omitted here)}private class ArrayStack<E> implements Stack<E> {... (Code in this class omitted here)}}Copy the code-
Submit the results
-
Implementation of queue data structure
A review of the basics of queues
-
A queue is also a linear structure.
-
In contrast to arrays, the operations on queues are subsets of arrays.
- That is, a queue can be implemented based on an array and can be treated as a special array.
-
Queues can only add elements from one end (the end of the queue) and take elements from the other end (the head of the queue).
- In fact, it’s similar to a real life line. The first person in line leaves and the new person goes to the back of the line.
-
A queue is a FIFO (First In First Out) data structure.
Array-based queue implementation
For the queue data structure, implementation is very simple, here to achieve the following operations:
-
Void enqueue(E element)
-
Queue: E dequeue()
-
Check the queue head element: E getFront()
-
Int getSize()
-
Check whether the queue isEmpty: Boolean isEmpty()
For specific implementations of code, the same stack as the one implemented above can be implemented to support polymorphism in the queue. So design an interface Queue to define the operations supported by these five queues, and a class ArrayQueue to implement this interface.
The ArrayQueue class is essentially based on the dynamic Array class Array that was implemented earlier.
Specific code design
Before writing the Array queue code, import the Array class from the project, because it is based on the Array queue, but it was imported when we implemented the stack.
Queue interface class implementation:
/** * The interface that defines the basic operations of queues * supports generics **@authorSnow in search of plum *@date2020/1/9 - hast judged * /
public interface Queue<E> {
/** * get the number of elements in the queue **@returnIf there are elements in the queue, return the current number of elements in the queue. Returns 0 */ if there are no elements in the queue
int getSize(a);
/** * Check whether the queue is empty **@returnQueue empty, return true; The queue is not empty, return false */
boolean isEmpty(a);
/** * add element to the end of the queue **@paramElement A team element */
void enqueue(E element);
/** * the first element is removed from the queue and returns **@returnReturns the element */ of the current queue leader
E dequeue(a);
/** * view the current queue header element **@returnReturns the current queue head element */
E getFront(a);
}
Copy the codeArrayQueue implementation:
The Array class already implements many methods to manipulate arrays. So when implementing the methods in the interface of the ArrayQueue class, you just need to reuse the methods in the Array class.
Similarly, implementing the ArrayQueue class based on the Array class has corresponding benefits:
Like Array, we have the ability to scale dynamically, so we don’t need to worry about whether the queue is full or not, because the capacity will grow and shrink dynamically.
The determination of some illegal variables is directly reused in the Array class code, does not need to be written repeatedly.
You can also add a method called getCapacity to the ArrayQueue class that does not exist in the interface to provide the user with the capacity to get the queue. This method is unique to this class.
The ArrayQueue class is implemented as follows:
/** * The ArrayQueue class, based on the dynamic Array class Array implemented earlier, also supports generics@authorSnow in search of plum *@date2020/1/10 - that is * /
public class ArrayQueue<E> implements Queue<E> {
/** * dynamic array array * array-based queue operations */
private Array<E> array;
/** * constructor * creates an array queue of capacity **@paramCapacity Specifies the capacity of the queue to be created. */
public ArrayQueue(int capacity) {
array = new Array<>(capacity);
}
/** * The default constructor creates an array queue of the default size */
public ArrayQueue(a) {
array = new Array<>();
}
/** * Get queue capacity * ArrayQueue specific methods **@returnReturns the size of the queue */
public int getCapacity(a) {
// Reuse the array getCapacity() method
return array.getCapacity();
}
@Override
public int getSize(a) {
// Reuse the array getSize() method
return array.getSize();
}
@Override
public boolean isEmpty(a) {
// Just reuse the array isEmpty() method
return array.isEmpty();
}
@Override
public void enqueue(E element) {
// Use the addLast() method of array as the end of the queue
array.addLast(element);
}
@Override
public E dequeue(a) {
// Reuse array's removeFirst() method to remove the first element from the queue and return it
return array.removeFirst();
}
@Override
public E getFront(a) {
// Reuse array's getFirst() method to get the first element of the queue
return array.getFirst();
}
/** * Overrides the toString method to return information on an array queue **@returnReturns the current information of the array queue */
@Override
public String toString(a) {
StringBuilder result = new StringBuilder();
result.append("ArrayQueue: ");
result.append("size: ").append(array.getSize()).append("");
result.append("capacity: ").append(array.getCapacity()).append("");
result.append("front -> [ ");
for (int i = 0; i < array.getSize(); i++) {
result.append(array.get(i));
// If not the last element
if(i ! = array.getSize() -1) {
result.append(",");
}
}
result.append(" ] <- tail");
returnresult.toString(); }}Copy the codeFor the elements in the traversal queue in toString, just to make it easier to see if the queue adds the elements correctly as we designed.
For the user, there is no need to know other elements except for the first element, because normally business operations are directed to the first element and the rest of the elements are queued. In addition, the user can only operate the first and last elements of the queue, enter the new data from the last and leave the old data from the first, and cannot operate other elements except the first and last elements of the queue, which is also the characteristic of the data structure of the queue.
Testing:
/**
* 测试 ArrayQueue
*/
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<>();
// Check whether the queue is empty
System.out.println("Is the current queue empty:" + queue.isEmpty());
for (int i = 0; i < 10; i++) {
/ / team
queue.enqueue(i);
// display the joining process
System.out.println(queue);
// Every 4 elements in the team will leave the team once
if (i % 4= =3) {
/ / out of the team
queue.dequeue();
// Display the queue process
System.out.println("\n" + queue + "\n"); }}// Check whether the queue is empty
System.out.println("Is the current queue empty:" + queue.isEmpty());
// Get the first element
Integer front = queue.getFront();
System.out.println("The first element of the current team formation is:" + front);
}
Copy the codeTest results:
Simple time complexity analysis of array-based queues
For the five operations implemented, their time complexity can be quickly calculated from the previous Array class analysis as follows:
-
Void enqueue(E element) : O(1
- Because the array method is reused, the resize method may be triggered to scale the capacity, so the time complexity is amortized.
-
E to dequeue () : O (n)
-
When the leader element is removed from a team, the remaining elements move forward one position.
-
Therefore, for the array-based queue currently implemented, if the amount of data to be placed is very large, such as 1 million or 10 million data, the time and performance of the queue operation will be very high.
- In this case, circular queues can be used.
-
-
E getFront () : O (1)
-
Int getSize () : O (1)
-
Boolean isEmpty () : O (1)
The implementation of a circular queue
Analysis of defects when listing teams:
In the previous array-based implementation, the remaining elements of the queue were moved forward by one position when the queue was enqueued, and if the queue was enqueued with a large amount of data it would take a lot of time to move the elements. If you don’t move, there will be unused array space in front of you. So that’s a limitation of array queues.
To list teams:
Improved analysis:
To fix this defect, you can use two variables to record the position of the front and tail of the queue, respectively.
For front, we point to where the first element in the queue is, while tail points to where the new element should be placed when it joins the queue.
After this recording, when the element is out of the queue, just maintain the position to which the front points, so there is no need to move all the elements forward one position as before, so the time complexity is O(1) level. When an element is enqueued, you simply maintain tail to redirect it to where the next element should be enqueued.
Therefore, the implementation of the loop queue can be analyzed as follows:
-
Front == tail indicates that the queue is empty. Size indicates that the number of elements is 0.
-
When an element is enqueued, tail is maintained to point it to where the next element should be enqueued, which is the position after the last element in the current queue.
-
When an element is unqueued, maintain front to point it to the first element in the queue after it is unqueued.
-
When the element is enqueued until the value of tail cannot be increased by one and the queue space is full, maintain tail to point to the first position in the remaining space, causing the elements in the queue to loop as if they were in a loop.
-
For example:
-
We can change the value of tail when the element is enqueued.
(tail + 1) % capacity
-
When tail + 1 is equal to front, there is still one space left in the queue (the remaining space is designed not to be recorded in the queue capacity, so it means that the queue is full and cannot be added to the queue. That is, (tail + 1) % (Capacity + 1) == Front Indicates that the queue is full (Capacity + 1 == data.length).
-
If front == tail, the queue is empty. If front == tail, the queue is not empty. So an extra space is added to the loop queue to determine if the queue is full. The specific process is shown in the figure below:
-
To sum up, four formulas about circular queue can be summarized
-
Front == tail Indicates that the queue is empty.
-
(tail + 1) % data.length == front Indicates that the queue is full.
- Or (tail + 1) % (Capacity + 1) == front
-
Formula for changing the value of tail when the element is enqueued :(tail + 1) % data.length.
-
Because we have set up to add an extra space to the queue to determine whether the queue is full, changing tail requires the length of the underlying array of the queue, not the capacity of the queue. Please refer to the following figure for understanding:
-
-
Similarly, we can get the value formula of changing front when the element is queued out :(front + 1) % data.length.
-
-
Specific code design
Code implementation:
Based on the above analysis, the code of the LoopQueue class can be designed as follows:
/** * The LoopQueue class supports generics **@authorSnow in search of plum *@date2020/1/10 - "* /
public class LoopQueue<E> implements Queue<E> {
/** * The underlying array of loop queue elements */
private E[] data;
/** * the index that points to the first element of the queue */
private int front;
/** * the index at the end of the queue */ points to the index that should be placed when a new element joins the queue
private int tail;
/** * The number of current elements in the loop queue */
private int size;
/** * constructor * builds a loop queue of capacity **@paramCapacity Capacity of the circular queue to be created. This parameter is specified by the user. */
public LoopQueue(int capacity) {
// Because an extra space was added to the loop queue to determine whether the queue was full, an extra space was added to build data
data = (E[]) new Object[capacity + 1];
// The loop queue is initialized
front = 0;
tail = 0;
size = 0;
}
/** * The default constructor builds a circular queue of capacity 10 */
public LoopQueue(a) {
this(10);
}
/** * Gets the capacity of the loop queue **@returnReturns the capacity of the loop queue */
public int getCapacity(a) {
// Because an extra space is added to the loop queue to determine whether the queue is full, the array length is reduced by one on return
return data.length - 1;
}
@Override
public int getSize(a) {
return size;
}
@Override
public boolean isEmpty(a) {
// front == tail Indicates that the queue is empty and returns true; Otherwise return false
return front == tail;
}
/** * Change the capacity of the loop queue to newCapacity **@paramNewCapacity newCapacity of the circular queue */
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
// Move all elements of data to [0, size-1] of newData in order (front ~ tail)
for (int i = 0; i < size; i++) {
// The I values of the two arrays may not correspond when moving elements to the expanded space
// Set I offset to (I + front) % data.length
newData[i] = data[(i + front) % data.length];
}
// Point data to the expanded queue
data = newData;
// Change the index value of queue head and queue tail, because the top place moves all the elements of data in order (front ~ tail) to newData [0, size-1]
front = 0;
tail = size;
}
@Override
public void enqueue(E element) {
Data.length <==> getCapacity() + 1
if ((tail + 1) % data.length == front) {
// Expand the queue when the queue is full
resize(getCapacity() * 2);
}
/ / team
data[tail] = element;
Tail / / maintenance
tail = (tail + 1) % data.length;
Size / / maintenance
size++;
}
@Override
public E dequeue(a) {
// Check whether the queue is empty before exiting
if (isEmpty()) {
// If the queue is empty, an invalid parameter is thrown
throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
}
// Save the queue element to return to the user
E dequeueElement = data[front];
/ / out of the team
// Empty the first element of the original queue to prevent the object from drifting
data[front] = null;
The front / / maintenance
front = (front + 1) % data.length;
size--;
// When the number of elements in the queue is small enough, the size of the queue is reduced
if (size == getCapacity() / 4 && getCapacity() / 2! =0) {
resize(getCapacity() / 2);
}
// Return the queue element to the user
return dequeueElement;
}
@Override
public E getFront(a) {
// Check whether the queue is empty before viewing the first element
if (isEmpty()) {
// If the queue is empty, an invalid parameter is thrown
throw new IllegalArgumentException("Queue is empty.");
}
// return the first element to the user
return data[front];
}
/** * Overrides the toString method to return information about the loop queue **@returnReturns the current information for the loop queue */
@Override
public String toString(a) {
StringBuilder result = new StringBuilder();
result.append(String.format("LoopQueue: size = %d, capacity = %d\n", size, getCapacity()));
result.append("front -> [ ");
for (inti = front; i ! = tail; i = (i +1) % data.length) {
result.append(data[i]);
// If not the last element
if ((i + 1) % data.length ! = tail) { result.append(",");
}
}
result.append(" ] <- tail");
returnresult.toString(); }}Copy the codeTesting:
/**
* 测试 LoopQueue
*/
public static void main(String[] args) {
LoopQueue<Integer> queue = new LoopQueue<>();
// Check whether the queue is empty
System.out.println("Is the current queue empty:" + queue.isEmpty());
for (int i = 0; i < 10; i++) {
/ / team
queue.enqueue(i);
// display the joining process
System.out.println(queue);
// Every 3 elements in the team will leave the team once
if (i % 3= =2) {
/ / out of the team
queue.dequeue();
// Display the queue process
System.out.println("\n" + queue + "\n"); }}// Check whether the queue is empty
System.out.println("Is the current queue empty:" + queue.isEmpty());
// Get the first element
Integer front = queue.getFront();
System.out.println("The first element of the current team formation is:" + front);
}
Copy the codeTest results:
As for the loop queue code, it is difficult to reuse the Array class code because of the front and tail pointing to the front and tail of the queue, but the underlying implementation is still based on the generic Array, but using some of the loop queue formula to loop data. Like the Array, ArrayStack, and ArrayQueue classes previously implemented, it dynamically scales the capacity, so that users don’t have to worry about whether the capacity is enough.
Simple time complexity analysis of circular queues
For the circular queue, because front is used to point to the head of the queue, the time complexity at queue exit is O(1) quickly compared to the previous array queue.
In addition, automatic scaling capacity is also realized in the code implementation, so resize method may be triggered to expand and reduce capacity when joining and leaving the team. According to the analysis of Array class before, time complexity O(1) of joining and leaving the team can be equally divided. So for the five basic operations in the loop queue, the time complexity is as follows:
-
Void enqueue(E element) : O(1
-
E dequeue() : O(1)
-
E getFront () : O (1)
-
Int getSize () : O (1)
-
Boolean isEmpty () : O (1)
Comparison between array queues and circular queues
At this point, the basic data structures of stacks and queues are implemented, and I’ll write some code to actually test the efficiency difference between array queues and circular queues.
Test code:
import java.util.Random;
/** * Test the efficiency gap between ArrayQueue and LoopQueue **@authorSnow in search of plum *@date2020/1/8 - now * /
public class Main {
public static void main(String[] args) {
// Test data volume
int opCount = 100000;
// The time required to test the array queue
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double arrayQueueTime = testQueue(arrayQueue, opCount);
System.out.println("arrayQueueTime: " + arrayQueueTime + " s.");
// The time required to test the loop queue
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double loopQueueTime = testQueue(loopQueue, opCount);
System.out.println("loopQueueTime: " + loopQueueTime + " s.");
// Calculate the difference between the two
double multiple = arrayQueueTime / loopQueueTime;
System.out.println("On this machine, for" + opCount + "The amount of data that loopQueue takes is approximately faster than arrayQueue." + multiple + "Times.");
}
/** * The time required to run opCount enqueues and dequeues, in seconds **@paramQueue Specifies the test queue *@paramOpCount Indicates the amount of test data *@returnReturns the time required for the entire test, in seconds */
private static double testQueue(Queue<Integer> queue, int opCount) {
long startTime = System.nanoTime();
// Used to generate random numbers to join the queue
Random random = new Random();
/ / the enqueue opCount times
for (int i = 0; i < opCount; i++) {
/ / team
queue.enqueue(random.nextInt(Integer.MAX_VALUE));
}
/ / to dequeue opCount times
for (int i = 0; i < opCount; i++) {
/ / out of the team
queue.dequeue();
}
long endTime = System.nanoTime();
// Convert the time in nanoseconds to seconds
return (endTime - startTime) / 1000000000.0; }}Copy the codeIn the code above:
-
For array queues, the single operation is O(1) and opCount is O(n); Queue exit is O(n) for a single operation, and opCount is O(n^2^) for a single operation; So the time complexity of the array queue is O(n^2^) for the entire testQueue method.
-
For a circular queue, the time complexity of a single operation is O(1), so opCount and opCount are O(n), so the time complexity of a circular queue is O(n) for the entire testQueue method.
-
So you can expect that as n gets larger and larger, the array queue will consume much more time than the loop queue.
Test results:
Finally, from the results, you can see that the queuing and dequeuing times of the circular queue are significantly faster than the queuing times of the array queue. Of course, the test results may vary depending on the machine configuration, but it’s good to be able to verify that a circular queue is faster than an array queue.
If there is insufficient writing, please forgive me, please give more advice.
My personal blog website:www.xilikeli.cnWelcome to visit (#.#)
And welcome to mineMaking the home page, my personal blog has been open source, interested partners can dot star, thank you (#.#)