Learning is endless, and you are encouraged.
Related series
- Data structure series (1) – Arrays
- Data structure series (2) – Linked lists
- Data structure series (4) – Queues
- Data structure series (5) – Binary query tree
- Data structure series (6) – Heap
introduce
A stack is a data structure that limits insertion and deletion to only one position, which is the end of the stack, called the top of the stack. It is a LIFO data structure. The basic operations on the stack are push, which involves inserting data at the end of the stack, and pop, which involves deleting the last inserted data. Stacks are usually small in size and can be used for temporary data structures. Usually we implement a stack with an array.
Side of the stack
Every time we call to a method in JAVA is stack operation, the method of the return address (internal methods running after know where) return (parameters) of isolated individual methods and parameters into the stack method after the call stack, get into the method return values, to the external methods, and release the stack space. E.printstacktrace () essentially prints the stack of exception calls.
operation
Push (stack)
Top refers to the top of the stack. If it’s empty, top = -1; When new data is pushed, perform two steps:
- Start by pointing top to the next position: top++;
- Then place the newly inserted data in the position of top;
Note that if the order is reversed, the newly inserted data replaces the data at the top of the stack, and the data pointed to by top is empty
Pop (out of the stack)
Remove and return data at the top of the stack; There are also 2 steps:
- Get the top data;
- Top -;
If top is subtracted by 1, the data obtained is the data at the top of the stack after removal.
Implement stacks through arrays
public class StackUseArray<E>{
// Maximum capacity
private int maxSize;
// Data array
private Object[] array;
// execute top of stack
private int top;
public StackUseArray(int maxSize) {
this.maxSize = maxSize;
this.array = new Object[maxSize];
this.top = -1;
}
/ * *
* Insert data at the top
*
* @paramThe data of data
* /
public void push(E data) {
if (isFull()) {
System.out.println("Stack full, no more to add!!");
return;
}
this.array[++this.top] = data;
}
/ * *
* Remove the top data and return the removed data
*
* @return data
* /
@SuppressWarnings("unchecked")
public E pop(a) {
if (isEmpty()) {
System.out.println("The stack is empty and cannot be deleted again!!");
return null;
}
return (E) this.array[this.top--];
}
/ * *
* Query the top data
*
* @return data
* /
@SuppressWarnings("unchecked")
public E peek(a) {
if (isEmpty()) {
System.out.println("This is an empty stack!!");
return null;
}
return (E) this.array[this.top];
}
/ * *
* Check whether it is null
*
* @return boolean
* /
public boolean isEmpty(a) {
return this.top == -1;
}
/ * *
* Check to see if it's full
*
* @return boolean
* /
public boolean isFull(a) {
return this.top == (this.maxSize - 1);
}
}
Copy the codeApplication scenarios
When we write code through the IDE, we sometimes omit or overwrite a parenthesis for a lot of nested code, which displays an error message. Here we use a stack to verify the formatting of parentheses in the text.
: read the text, at every turn left parenthesis is into the stack, at every turn right parenthesis will pop up from the stack and left parenthesis to the current right parenthesis matching, check whether legal. When all text has been read, check to see if the stack is empty. If it is not empty, the text is missing the close bracket
- implementation
public class BracketChecker {
/ * *
* Open parenthesis, need to push
* /
private static final String LEFT_BRACKET = "([{";
/ * *
* Close parenthesis, used to verify that the left parenthesis of the sum out of the stack matches each time encountered
* /
private static final String RIGHT_BRACKET = ")]}";
/ * *
* for match check, each close parenthesis corresponds to its open parenthesis
* /
private static final Map<Character, Character> MATCH_MAP = new HashMap<Character, Character>() {{
put(') '.'(');
put('] '.'[');
put('} '.'{');
}};
/ * *
* The text to verify
* /
private String text;
public BracketChecker(String text) {
this.text = text;
}
/ * *
* Perform verification
*
* @return boolean
* /
public boolean check(a) {
int stackSize = this.text.length();
StackUseArray<Character> stack = new StackUseArray<>(stackSize);
// Current character
char curChar;
for (int i = 0; i < stackSize; i++) {
curChar = this.text.charAt(i);
if (LEFT_BRACKET.indexOf(curChar) > -1) {
// open parenthesis on the stack
stack.push(curChar);
System.out.println("push:" + curChar);
} else if (RIGHT_BRACKET.indexOf(curChar) > -1) {
// Close parenthesis, out stack match
System.out.println("curChar:" + curChar + ", match:" + stack.peek());
if(! stack.pop().equals(MATCH_MAP.get(curChar))) {
System.out.println("Error:" + curChar + " at " + i);
return false;
}
}
}
// Check whether the stack is empty
if(! stack.isEmpty()) {
System.out.println("Error: mission " + MATCH_MAP.get(stack.peek()));
return false;
}
return true;
}
public static void main(String[] args) {
BracketChecker bracketChecker = new BracketChecker("(a{b[c]d}e)");
System.out.println("Verification format:" + bracketChecker.check());
}
}
Copy the code- The results
push: (
push: {
push: [
curChar:], match:[
curChar:}, match: {
curChar:), match:(
Verification format: true
Copy the codeExtension, using linked lists to implement stacks
See the previous article for an introduction to portal: Linked lists
contrast
- In the implementation stack by array,
pushandpopThis is done through array operations.
array[++top] = data;
data = array[top--];
Copy the code- In the case of data storage in linked list, we create a single linked list through the method of header insertion to achieve the stack and stack
linkList.insertFirst(data);
linkList.deleteFirst;
Copy the code- Because there is no size limit to the linked list, there is no size limit to the stack implemented by the linked list
implementation
public class StackUseLink<E> {
private LinkList<E> linkList;
public StackUseLink(a) {
this.linkList = new LinkList<>();
}
/ * *
* Insert data at the top
*
* @paramThe data of data
* /
public void push(E data) {
linkList.insertFirst(data);
}
/ * *
* Remove the top data and return the removed data
*
* @return data
* /
public E pop(a) {
return linkList.deleteFirst();
}
/ * *
* Check whether it is null
*
* @return boolean
* /
public boolean isEmpty(a) {
return false;
}
/ * *
* Inner class implements a single linked list with a header method
*
* @param <E>
* /
private static class LinkList<E> {
Node<E> first;
void insertFirst(E data) {
first = new Node<>(data, first);
}
E deleteFirst(a) {
if (isEmpty()) {
System.out.println("Delete failed. It's empty.");
return null;
}
Node<E> delNode = first;
first = first.next;
delNode.next = null;
return delNode.data;
}
boolean isEmpty(a) {
return first == null;
}
/ * *
* Linked list nodes
*
* @param <E>
* /
private static class Node<E> {
/ * *
* data
* /
E data;
/ * *
* points to the next node
* /
Node<E> next;
Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
}
}
Copy the codeconclusion
- Only one item is allowed to be accessed, the last inserted item, called the top of the stack.
- Last in, first out (LIFO)
- Usually small and temporary data institutions
- Push (push)
- Pop (out of stack)
- This can be implemented as an array or linked list
Access to the source code
All the code in this series is uploaded to Github for easy access
>>>>>> data structure – stack <<<<<<
Daily for praise
Creation is not easy, if you feel helpful, please support
Please focus on
