The Stack (Stack)
- A stack is a linear structure. Stack operations are subsets of arrays compared to arrays, so we can implement them based on dynamic arrays
- Elements can only be added and taken from one end of the stack, called the top
- A stack is a LIFO data structure (Last In First Out for short).
The most common application scenarios of stack:
- Bracket matching – compiler
- The ubiquitous Undo operation, which puts every action on the stack, simply pushes the element off the stack
- The system stack called by the program, and the call hierarchy shown when the method is called, is the stack structure, as shown in the following figure:
Basic stack structure
We will implement a stack data structure based on the previously implemented dynamic array. Since there are many ways to implement the underlying stack (arrays, linked lists), to isolate the implementation, we define an interface to program against the interface that defines only the necessary methods for the stack data structure:
public interface Stack<E> {
/** * gets the number of elements in the stack **@returnNumber of elements */
int getSize(a);
/** * whether the stack is empty **@returnReturns true for null, false */ otherwise
boolean isEmpty(a);
/** * pushes an element **@paramE New element */
void push(E e);
/** * removes an element from the stack **@returnThe top element */
E pop(a);
/** * view the element ** at the top of the stack@returnThe top element */
E peek(a);
}
Copy the codeThen create an implementation class to implement the interface as follows:
/** * Stack data structure based on dynamic array implementation **/
public class ArrayStack<E> implements Stack<E> {
private Array<E> array;
public ArrayStack(a) {
this.array = new Array<>();
}
public ArrayStack(int capacity) {
this.array = new Array<>(capacity);
}
@Override
public int getSize(a) {
return array.getSize();
}
@Override
public boolean isEmpty(a) {
return array.isEmpty();
}
@Override
public void push(E e) {
array.addLast(e);
}
@Override
public E pop(a) {
return array.removeLast();
}
@Override
public E peek(a) {
return array.getLast();
}
/** * Get the stack capacity **@return capacity
*/
public int getCapacity(a){
return array.getCapacity();
}
@Override
public String toString(a) {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("Stack: size = %d, capacity = %d\n", getSize(), getCapacity()));
sb.append("[");
for (int i = 0; i < getSize(); i++) {
sb.append(array.get(i));
if(i ! = getSize() -1) {
sb.append(","); }}return sb.append("] top").toString(); }}Copy the codeAs you can see from the implementation code, it is very simple to implement a stack data structure based on the dynamic array we implemented in the previous chapter.
The time complexity of ArrayStack’s main methods:
Void push(E) // O(1) peek() // O(1) int getSize() // O(1) Boolean isEmpty() // O(1)
The stack implements bracket matching
Matching parentheses is a classic application of the stack, and many companies have asked this question in interviews. If it encounters an open parenthesis, it is pushed onto the stack. If it encounters a close parenthesis, it is pushed off the stack to match the top element. If it matches, the loop continues. After executing the loop normally, we need to verify that the stack is empty, because parentheses match the top element of the stack, so if the logic inside the loop is correct, all elements will be removed from the stack, and the stack must be empty.
/ * * *@authorLi. Pan * < p > * given a only include a '(',') ', '{','} ', '/', ' 'the string s, determine whether a string is effective. * A valid string must meet the following requirements: * 1. The left parentheses must be closed with the same type of right parentheses. * 2. The left parentheses must be closed in the correct order. * </p> */
public class Leetcode20 {
public boolean isValid(String s) {
Stack<Character> stack = new ArrayStack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{') {
// all parentheses on the left are pushed
stack.push(c);
} else {
// If there are no elements in the stack, there are no open parentheses
if (stack.isEmpty()) {
return false;
}
// Fetch elements at the top of the stack for matching, return false for any mismatches
char topChar = stack.pop();
if (c == ') '&& topChar ! ='(') {
return false;
}
if (c == '] '&& topChar ! ='[') {
return false;
}
if (c == '} '&& topChar ! ='{') {
return false; }}}// Finally, we need to verify that the stack is empty
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println((new Leetcode20()).isValid("[the] {} ()")); // true
System.out.println((new Leetcode20()).isValid("{[()]}")); // true
System.out.println((new Leetcode20()).isValid("([{}]")); // false}}Copy the codeQueue
- Queues are also linear structures that correspond to a subset of arrays compared to arrays
- Queues can only add elements from the end of the queue and can only take elements from the beginning of the queue
- A queue is a first-in, first-out data structure, and FIFO actually stands for First In First Out
The queue in the data structure is the same as the queue in our real life. For example, when we queue up to the counter for business, it is a queue structure. Those who queue up first apply for business first, and those who queue up later apply for business later, which conforms to the first-in, first-out feature.
The basic structure of a queue
Similarly, there are many ways to implement the Queue structure, such as array Queue, circular Queue and linked list Queue. Therefore, we need to define a Queue interface to program the interface. This interface defines only the necessary methods of the Queue data structure:
public interface Queue<E> {
/** * New element to team **@paramE New element */
void enqueue(E e);
/** * element out of the queue **@returnElements * /
E dequeue(a);
/** * gets the element ** at the head of the queue@returnTeam leader element */
E getFront(a);
/** * gets the number of elements in the queue **@returnNumber of elements */
int getSize(a);
/** * whether the queue is empty **@returnReturns true for null, false */ otherwise
boolean isEmpty(a);
}
Copy the codeAn array of the queue
Similarly, we implement an array queue based on the dynamic array we implemented earlier
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array;
public ArrayQueue(a) {
this.array = new Array<>();
}
public ArrayQueue(int capacity) {
this.array = new Array<>(capacity);
}
@Override
public void enqueue(E e) {
array.addLast(e);
}
@Override
public E dequeue(a) {
return array.removeFirst();
}
@Override
public E getFront(a) {
return array.getFirst();
}
@Override
public int getSize(a) {
return array.getSize();
}
@Override
public boolean isEmpty(a) {
return array.isEmpty();
}
public int getCapacity(a) {
return array.getCapacity();
}
@Override
public String toString(a) {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("Queue: size = %d, capacity = %d\n", getSize(), getCapacity()));
sb.append("front [");
for (int i = 0; i < getSize(); i++) {
sb.append(array.get(i));
if(i ! = getSize() -1) {
sb.append(","); }}return sb.append("] tail").toString(); }}Copy the codeThe time complexity of the main methods of ArrayQueue:
Void enqueue(E) // O(1) E dequeue() // O(n) E getFront() // O(1) int getSize() // O(1) Boolean isEmpty() // O(1)
The above has implemented a queue based on dynamic arrays, but there are some limitations. In the dequeuing operation, the complexity is O(n). If there are a large number of elements in the queue, it is time-consuming to dequeue even one element. For example, if there are 10W elements in the array, then each element in the queue moves 10W elements.
Circular queue
In view of the high complexity of queuing time, we adopt another way to realize the data structure of queue. We usually use circular queue or linked list queue. This section mainly introduces circular queue. In the loop queue, we set two variables, front and tail, where front always refers to the element at the top of the queue, and tail always refers to the element at the end of the queue +1. When front equals tail, the queue is empty:
First, we can see that there is available space in front of the array. We can move tail onto the available space. As mentioned above, the tail moves when a new element is enqueued. How do we calculate the number of moves? The actual number of moves by tail is passed(tail + 1) % capacitySo, for example, here it is(7 + 1) % 8 = 0, so tail points to index 0, and front does the same thing:
It’s probably better to think of it as a loop, which is why it’s called a loop queue, as shown below:
When the queue is full, it naturally needs to be expanded. How do you determine that the queue is full? The answer is judgment(tail + 1) % capacityIs the result equal to the value of front:
Front == Tail The queue is empty, (tail + 1) % capacity== The front queue is full, and (tail + 1) % capacity the queue moves
Implement a circular queue, and an Array of queue before implementation, we are no longer based on Array class, because of the specific implementation logic, there are many different places, let us go to the Array as a ring, so can’t reuse this data structure Array, we have to finish this circular queue from the underlying data structure.
/** * loop queue data structure **/
public class LoopQueue<E> implements Queue<E> {
/** * the array that actually stores the elements */
private E[] data;
/** * refers to the first element */
private int front;
/** * indicates the index position of the element +1 at the end of the queue */
private int tail;
/** * Number of elements */
private int size;
/** * Constructor with queue initial capacity parameter **@paramCapacity Initial queue capacity */
public LoopQueue(int capacity) {
// Since the structure of the loop queue wastes an index space, +1 is required
this.data = (E[]) new Object[capacity + 1];
this.front = 0;
this.tail = 0;
this.size = 0;
}
/** * no parameter constructor, default queue initial capacity is 10 */
public LoopQueue(a) {
this(10);
}
/** * Get the queue capacity **@returnQueue capacity */
public int getCapacity(a) {
// Since an index space is wasted, the actual capacity is the array length -1
return data.length - 1;
}
@Override
public int getSize(a) {
return size;
}
@Override
public boolean isEmpty(a) {
return front == tail;
}
@Override
public E getFront(a) {
checkIfEmpty();
return data[front];
}
@Override
public void enqueue(E e) {
// Whether the queue is full
if ((tail + 1) % data.length == front) {
/ / capacity
resize(getCapacity() * 2);
}
data[tail] = e;
tail = (tail + 1) % data.length;
size++;
}
@Override
public E dequeue(a) {
checkIfEmpty();
E ret = data[front];
// Release the team element
data[front] = null;
/ / move the front
front = (front + 1) % data.length;
size--;
// Determine whether the capacity needs to be reduced
if (size == getCapacity() / 4 && getCapacity() / 2 > 0) {
/ / capacity
resize(getCapacity() / 2);
}
return ret;
}
@Override
public String toString(a) {
if (isEmpty()) {
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append(String.format("Queue: size = %d, capacity = %d\n", size, getCapacity()));
sb.append("front [");
// The first way to traverse the loop queue
for (inti = front; i ! = tail; i = (i +1) % data.length) {
sb.append(data[i]);
if ((i + 1) % data.length ! = tail) { sb.append(","); }}return sb.append("] tail").toString();
}
/** * Queue capacity reset **@paramNewCapacity New queue capacity */
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
// The second way to traverse the loop queue
for (int i = 0; i < size; i++) {
// Because it is a circular queue, the position of the element needs to be computed in a specific way
newData[i] = data[(front + i) % data.length];
}
data = newData;
front = 0;
tail = size;
}
/** * check if an operation is performed on an empty queue */
private void checkIfEmpty(a) {
if (isEmpty()) {
throw new IllegalArgumentException("Can't operation an empty queue."); }}}Copy the codeThe time complexity of the main LoopQueue methods:
void enqueue(E) / / O (1)
E dequeue(a) / / O (1)
E getFront(a) // O(1)
int getSize(a) // O(1)
boolean isEmpty(a) // O(1)
Copy the codePerformance comparison of array queues and circular queues
Finally, let’s write a simple test case to test the performance of array and loop queues with 10W data volume as follows:
public class Main {
/** * Tests how long it takes to run opCount enqueues and dequeues using queue, in milliseconds **@param queue queue
* @param opCount opCount
* @returnTake * /
private static long testQueue(Queue<Integer> queue, int opCount) {
long startTime = System.currentTimeMillis();
Random random = new Random();
for (int i = 0; i < opCount; i++) {
queue.enqueue(random.nextInt(Integer.MAX_VALUE));
}
for (int i = 0; i < opCount; i++) {
queue.dequeue();
}
return System.currentTimeMillis() - startTime;
}
public static void main(String[] args) {
long time1 = testQueue(new ArrayQueue<>(), 100000);
System.out.println("ArrayQueue, time: " + time1 + "/ms");
long time2 = testQueue(new LoopQueue<>(), 100000);
System.out.println("LoopQueue, time: " + time2 + "/ms"); }}Copy the codeThe console output is as follows:
ArrayQueue, time: 16531/ms
LoopQueue, time: 15/ms
Copy the codeFor array queues, all elements need to be moved each time the queue exits, so the time consumption is large.
Source code address: github.com/perkinls/ja…