Initial confusion
When I first got the basic concept of stack, I was puzzled that the stack could only operate data from one end, and its function was not as rich as that of array and linked list, so it would be better to use array or linked list to implement it directly. Why should there be such a structure as stack?
After reading several related books, several video courses, and realizing the requirements of some scenes with stack structure, my cognition has changed significantly. I can express the following points:
- Each data structure is an abstract representation of a highly similar real-world scenario. As you get better at understanding data structures, you’ll understand this more and more, and the same goes for stacks. Consider the browser’s ability to move forward and back, to detect whether parentheses that should always exist in pairs in an expression are valid, and so on. !
- More features is not always the best. Array or list does provide more interface, operability is stronger, more flexible to use, but the probability of error is higher ah, unlike the stack, on the stack, out of this function, in the case of the need to achieve why don’t we use simple, low error rate? !
1. Basic concepts
- A stack is a special type of linear table in which insertions and deletions are allowed only at one end of the linear table. The end that allows operations is called the top of the stack, and the end that disallows operations is called the bottom.
- The operation of inserting an element on the stack is called push, and the operation of deleting an element is called pop.
- A stack with no elements becomes empty.
- Last in First Out (LIFO) : Since only one end of the stack can be inserted or deleted, each element pushed into the stack becomes the top element of the current stack, and each element out of the stack is always the last element pushed into the stack, also known as lifO table.
2. Two implementation methods: sequential stack + linked list stack
Storage is divided into two ways: open up a contiguous memory space sequential storage, chain space storage
The basic operations of the stack include creating the stack, pushing the stack, getting out of the stack, fetching the top element of the stack, judging whether the stack is empty, and so on. Fetching the top element of the stack only takes the element but does not delete the element.
public interface SStack<T> {
/** * check whether the current stack is empty **@returnBoolean True - is empty stack, false- is not empty stack */
boolean isEmpty(a);
/** * Push elements **@paramT Elements to be pushed *@return void
*/
void push(T t);
/** * Element out of the stack **@returnThe element of the stack from T */
T pop(a);
/** * remove the element from the top of the stack@param
* @returnT stack top element */
T get(a);
}
Copy the code2.1 Sequential stack
Brief introduction to concept:
The stack implemented by the sequential storage structure is called the sequential stack.
Core API overview
Concrete implementation:
/ * * *@ClassName SeqStack
* @Description: sequential stack class: using sequential storage structure to store data to achieve stack *@Author: myl
* @Create_time:2021/1/30 16:52
*/
public class SeqStack<T> implements SStack<T> {
/** * The underlying use of data storage elements */
private Object[] element;
/** * defines the subscript of the top element of the stack, initialized to -1 */
private int top;
/** * initializes a stack container **@paramSize * Specifies the size of the stack container */
public SeqStack(int size) {
this.element = new Object[Math.abs(size)];
this.top = -1;
}
/** * The default constructor is set to 64 */
public SeqStack(a) {
this(64);
}
/** * determine whether the current stack is empty * <p> * When initializing the container, specify the subscript of the top of the stack as -1, so directly determine whether the current stack is empty by the subscript of the top of the stack as -1. Therefore, it is required to maintain the bottom value of the top stack element * </p> * * when pushing and exiting the stack@returnBoolean True - is empty stack, false- is not empty stack */
@Override
public boolean isEmpty(a) {
return top == -1;
}
/** * Push elements **@paramT * Elements to be pushed *@return void
*/
@Override
public void push(T t) {
if (Objects.isNull(t)) {
return;
}
// Determine whether the current stack is full. If the stack is full, you need to apply for a larger space to store the stack elements. Therefore, when creating the stack, you can directly declare its size if you know the amount of data
if (top == element.length) {
Object[] temp = this.element;
this.element = new Object[temp.length * 2];
// Copy the original array
for (int i = 0; i < temp.length; i++) { element[i] = temp[i]; }}// Maintain the top element subscript and push the element
element[++top] = t;
}
/** * Element out of the stack **@returnThe element of the stack from T */
@Override
public T pop(a) {
// Check whether the stack is empty
if (top == -1) {throw new RuntimeException("No element on the current stack is out of the stack.");
}
// Top of the stack: take out the top element of the stack and maintain the top element of the stack
return (T)element[top--];
}
/** * remove the element from the top of the stack@returnT stack top element */
@Override
public T get(a) {
// Check whether the stack is empty
if (top == -1) {throw new RuntimeException("No elements are available on the current stack.");
}
// Fetch the top element of the stack
return (T)element[top];
}
public int size(a){
returnelement.length; }}Copy the code2.2. Chain stack
Concept introduction
The stack that uses the chain storage structure to store data is called the chain stack.
Core API overview
The specific implementation
/** * Node objects used in chained tables: points to the next address and stored element values **@param <T>
*/
class Node<T> {
/** * points to the next node */
Node<T> next;
/** * Store the actual data value */
T data;
public Node(Node<T> node, T data) {
this.next = node;
this.data = data;
}
public Node(a) {}}Copy the code/ * * *@ClassName LinkedStack
* @Description: list type stack: using chain storage structure to store data to achieve the stack *@Author: myl
* @Create_time:2021/1/30 16:52
*/
public class LinkedStack<T> implements SStack<T> {
/** * define the top element */
private Node<T> top;
public LinkedStack(Node<T> node) {
this.top = node;
}
public LinkedStack(a) {}
/** * check whether the current stack is empty **@returnBoolean True - is empty stack, false- is not empty stack */
@Override
public boolean isEmpty(a) {
return top == null;
}
/** * Element push: build a new node with next pointing to the original top object and then top pointing to the new node object **@paramT * Elements to be pushed *@return void
*/
@Override
public void push(T t) {
if (t == null) {
throw new RuntimeException("Push elements cannot be null");
}
this.top = new Node<>(top, t);
}
/** * Element out of the stack **@returnThe element of the stack from T */
@Override
public T pop(a) {
// Save the current top and set the node pointed to by the current top to top
if (top == null) {
throw new RuntimeException("There are no current elements to leave the stack.");
}
Node<T> temp = top;
top = top.next;
return temp.data;
}
/** * remove the element from the top of the stack@returnT stack top element */
@Override
public T get(a) {
return top == null ? null: top.data; }}Copy the code3, stack combat
Applicable situation:
Wherever last-in, first-out (LIFO) data structures are used, a stack structure is a good fit.
Examples of classic scenarios:
-
The implementation mechanism of nested calls is particularly suited to the stack structure
-
Judge the expression “{[(1 + 3) * 7 + (3 + 4) * 2] / 2-1} * 3”, “{[(1 + 3) * 7 + (3 + 4) * 2] / 2-1)} * 3” in parentheses is it legal?
Here the criterion for judging whether it is legal is: do not make the priority judgment between “()”, “{}”, “[]”, each pair of parentheses is in pairs, and each pair of parentheses is in pairs of natural numbers, the occurrence of odd parentheses is illegal.
Using the stack data structure:
/ * * * determine whether a given expression in parentheses legal * < p > identify kinds of brackets range: (*) [] {} * < / p > * *@param expression * @return* / public boolean judgeBracketInExpressionIsValid(String expression) { SeqStack<String> stringLinkedStack = new SeqStack<>(expression.length()); Map<String, String> afterBracketDataMap = new HashMap<String, String>() { { put(")"."("); put("]"."["); put("}"."{"); }}; Map<String, String> frontBracketDataMap =new HashMap<String, String>() { { put("("."placeholder"); put("["."placeholder"); put("{"."placeholder"); }};for (int i = 0; i < expression.length(); i++) { char ch = expression.charAt(i); if (frontBracketDataMap.get(ch+"") != null) {/ / into the stack stringLinkedStack.push(ch + ""); }else if (afterBracketDataMap.get(ch+"") != null) {/ / out of the stack if(stringLinkedStack.isEmpty() || (! stringLinkedStack.pop().equals(afterBracketDataMap.get(ch +"")))) { return false; }}}// If it reaches this point, check whether there are any remaining elements in the stack. If there are any remaining elements, prove that the parentheses in the expression are illegal return stringLinkedStack.isEmpty(); } Copy the codeUsing the idea of recursion:
/** * a recursive method to determine whether the parentheses in an expression are illegal@paramExpression * Specifies the expression *@return boolean */ public boolean judgeBracketInExpressionIsValidRecursion(String expression) { // Prepare for fetching data Map<String, String> afterBracketMap = new HashMap<String, String>(3) { { put(")"."("); put("]"."["); put("}"."{"); }}; Map<String, String> frontBracketMap =new HashMap<String, String>(3) { { put("("."placeholder"); put("["."placeholder"); put("{"."placeholder"); }};// Call the recursive method int handleResult = judgeBracket(expression, -1, afterBracketMap, frontBracketMap, null); return handleResult < 0 ? false : true; } /** * recursively detect characters * <p> ** </p> **@paramExpression Indicates the expression * to be detected@paramIndex The character index cursor value * in the detected expression@paramAfterBracketMap afterBracketMap data mapping set *@paramFrontBracketMap Front bracket data mapping collection *@paramTargetBracket Indicates the character * to be compared@returnInt return > 0; It is illegal to return a value < 0. * / public int judgeBracket(String expression, int index, Map<String, String> afterBracketMap, Map<String, String> frontBracketMap, String targetBracket) { for (int i = index + 1; i < expression.length(); i++) { char charAt = expression.charAt(i); if (frontBracketMap.get(charAt + "") != null) { // The new front bracket appears, which opens up new memory space detection directly int handle = judgeBracket(expression, i, afterBracketMap, frontBracketMap, charAt + ""); if (handle < 0) { return handle; } // Return the cursor at the checked position i = handle; } else if (afterBracketMap.get(charAt + "") != null) { // If the parenthesis is present, then the comparison symbol is invalid if it does not correspond or is null return afterBracketMap.get(charAt + "").equals(targetBracket) ? i : -1; }}return 1; } Copy the code