This is the 14th day of my participation in the August More Text Challenge. For details, see:August is more challenging”

 The stack

1.The introduction of the stack

A stack is a linear table that restricts inserts and deletes to only one place. The end of the table where insertions and deletions are allowed is called the top, and the end where insertions and deletions are not allowed is called the bottom. The basic operations on the stack are PUSH (pushing an element onto the top of the stack) and POP (removing an element from the top of the stack). A stack is a last in, first out (LIFO) data structure, where the most recently pressed element is removed first.

Pop down:

Play the stack:

 

The stack to achieve

Since a stack is a table, any method that implements a table can be used to implement a stack. There are two main ways, linked list implementation and array implementation.

 

Linked list implementation stack

Stacks can be implemented using single linked lists. PUSH is implemented by inserting an element at the top of the table, and POP is implemented by deleting the top element of the table. The stack implemented using the linked list is also called dynamic stack. Dynamic stack has some characteristics of linked list, that is, elements and elements in physical storage can be discontinuous, but some functions are limited, dynamic stack can only be inserted and deleted at the top of the stack, can not be inserted and deleted at the end of the stack or the middle of the stack

 

Array implementation stack

Stacks can also be implemented as arrays. A stack implemented using an array is called a static stack.

2. Application scenarios of stacks

3. Quick start on stacks

Exercise 1: Use arrays to simulate the use of stacks

 

/** * file: version:1.0 */ public class ArrayStack {/** stack size */ private int maxStack; */ private int[] stack; Private int top = -1; private int top = -1; private int top = -1; /** ** @param */ public ArrayStack(int maxStack){this.maxStack = maxStack; this.stack = new int[this.maxStack]; } /** * check whether the stack isFull * @return */ public Boolean isFull(){return this.top== maxstack-1; Public Boolean isEmpty(){return this.top==-1; Public void push(int value){if (isFull()){throw new RuntimeException(" stack isFull...") ); } top++; stack[top] = value; } /** * stack */ public int pop(){if (isEmpty()){throw new RuntimeException(" empty stack, no data "); } int value = stack[top]; top--; return value; Public void list(){if (isEmpty()){throw new RuntimeException(" empty stack, no data "); } for (int i=0; i<stack.length; i++){ System.out.printf("stack[%d]=%d\n",i,stack[i]); }}}Copy the code

Problem 2: palindrome number

Palindrome: A word, phrase, or number written backwards is the same as written backwards. For example, the words “dad” and “racecar” are palindromes; If you ignore Spaces and punctuation, the following sentence is also palindrome: “A man, A plan, A canal: Panama,” as is the number 1001.

Using the stack, you can easily determine whether a string is a palindrome. We push each character of the string on the stack from left to right. When all the characters in the string are pushed onto the stack, a reversed string is stored on the stack, with the last character at the top and the first character at the bottom

ArrayStack arrayStack = new ArrayStack(10); int length = words.length(); for (int i=0; i<length; i++){ arrayStack.push(words.charAt(i)); } String newValue = ""; for (int i=0; i<arrayStack.length(); i++){ if (! arrayStack.isEmpty()){ Object value = arrayStack.pop(); newValue = newValue+value; } } if (words.equals(newValue)){ return true; } return false; }Copy the code

4. Stack implementation calculator

Thinking analysis result chart:

 

 Array S tack

*/ private int maxStack; */ private int[] stack; Private int top = -1; private int top = -1; private int top = -1; /** ** @param */ public ArrayStack(int maxStack){this.maxStack = maxStack; this.stack = new int[this.maxStack]; } /** * check whether the stack isFull * @return */ public Boolean isFull(){return this.top== maxstack-1; Public Boolean isEmpty(){return this.top==-1; Public void push(int value){if (isFull()){throw new RuntimeException(" stack isFull...") ); } top++; stack[top] = value; } /** * stack */ public int pop(){if (isEmpty()){throw new RuntimeException(" empty stack, no data "); } int value = stack[top]; top--; return value; Public void list(){if (isEmpty()){throw new RuntimeException(" empty stack, no data "); } for (int i=0; i<stack.length; i++){ System.out.printf("stack[%d]=%d\n",i,stack[i]); }} /** * Check stack size * @return */ public int length(){return stack.length; } @return */ public int peek(){return stack[top]; } / operator precedence * * * * the greater the number the higher priority * / public int priority (int oper) {if (oper = = '*' | | oper = = '/') {return 1; }else if (oper=='+' || oper=='-'){ return 0; }else { return -1; }} / * * * to judge whether an operator * / public Boolean isOper (char v) {return v = = '+' | | v = = '-' | | v = = '*' | | v = = '/'; } /** * calculate */ public int calculate(int num1,int num2,int oper){int res = 0; switch (oper){ case '+': res=num1+num2; break; case '-': res=num2-num1; break; case '*': res=num1*num2; break; case '/': res=num2/num1; break; default: break; } return res; }Copy the code

 main

String str = "3+2*3-1-1"; ArrayStack numStack = new ArrayStack(10); ArrayStack symbolStack = new ArrayStack(10); int length = str.length(); int temp1 = 0; int temp2 = 0; int symbolChar = 0; int result = 0; String values = ""; for (int i=0; i<length; I ++) {// get each character char c = str.charat (I); If (symbolstack.isoper (c)){// if (symbolstack.isoper (c)); Priority (c)<=symbolStack.priority(symbolStack.peek())){symbolStack.isempty ()){ /** * = numstack.pop (); /** * = numstack.pop (); /** * = numstack.pop (); temp2 = numStack.pop(); symbolChar = symbolStack.pop(); result = numStack.calculate(temp1,temp2,symbolChar); NumStack. Push (result); Push (c); // Put the current symbol on the stack. }else {// if the current symbol has a higher priority than the symbol in the symbolStack, put it directly in the symbolStack. }}else {// if the symbolStack is empty, push(c); // if the symbolStack is empty, push(c); }}else {// If the scan is numeric. Values +=c; values+=c; values+=c; values+=c; If (I ==length-1){numstack.push (integer.parseint (values)); }else { char data = str.substring(i+1, i + 2).charAt(0); If (symbolstack.isoper (data)){// If it's a symbol, store the number on the stack and clear values. numStack.push(Integer.parseInt(values)); values=""; } } } } while (true){ if (symbolStack.isEmpty()){ break; } temp1 = numStack.pop(); temp2 = numStack.pop(); symbolChar = symbolStack.pop(); result = numStack.calculate(temp1,temp2,symbolChar); numStack.push(result); } int res = numStack.pop(); System.out.println(" the result is :"+res); }Copy the code