Shulou(Shulou.com)06/03 Report--

In this issue, the editor will bring you about how to use the inner stack of Java programming. The article is rich in content and analyzes and narrates it from a professional point of view. I hope you can get something after reading this article.

Basic introduction

1. The stack is an ordered list of FILO First In Last Out

two。 Stack is a special linear table that restricts the insertion and deletion of elements in a linear table to the same end of the linear table. One end that allows insertion and deletion is the changing end, called Top, and the other end is fixed end, called Bottom.

3. According to the definition of the stack, the first element in the stack is at the bottom of the stack, and the last element is at the top of the stack, while the deleted element is just the opposite. The last element is deleted first, and the element that is put first is deleted.

Application scenario of stack

1. The call of the subroutine: before calling to the subroutine, the address of the next instruction will be stored in the stack until the subroutine is executed, and then the address will be taken out to return to the original program.

two。 Handle recursive calls: similar to subroutine calls, except that parameters\ region variables and other data are stored in the stack in addition to the address of the next instruction.

3. Expression conversion (infix expression to suffix expression) and evaluation (actual solution).

4. The traversal of a binary tree.

5. Depth first (depth-first) search algorithm for graphics.

Stack structure implementation case package com.structures.stack; import java.util.Scanner; public class ArrayStackDemo {public static void main (String [] args) {ArrayStack stack = new ArrayStack (4); String key = ""; boolean loop = true; Scanner scanner = new Scanner (System.in); while (loop) {System.out.println ("show: display stack") System.out.println ("exit: exit the program"); System.out.println ("push: add data to the stack (stack)"); System.out.println ("pop: fetch data from the stack (out of the stack)"); key = scanner.next () Switch (key) {case "show": stack.list (); break; case "push": System.out.println ("Please enter a number"); int value = scanner.nextInt (); stack.push (value) Break; case "pop": try {int res = stack.pop (); System.out.println ("data% d\ n" + res) } catch (Exception e) {System.out.println (e.getMessage ());} break; case "exit": scanner.close (); loop = false; break }} System.out.println ("program exit");}} / / define a class to represent the stack structure class ArrayStack {the size of the private int maxSize;// stack private int [] stack;// array simulation stack, the data is put into the array private int top =-1 this.maxSize top represents the top of the stack, initialize-1 stack (int maxSize) {this.maxSize = stack Stack = new int [this.maxSize];} / / determine whether the stack is full public boolean isFull () {return top = = maxSize-1;} / / determine whether the stack is empty public boolean isEmpty () {return top = =-1 } / / public void push (int value) {if (isFull ()) {System.out.println ("stack full"); return;} top++; stack [top] = value;} / / out stack public int pop () {if (isEmpty ()) {throw new RuntimeException ("stack empty") } int value = stack [top]; top--; return value;} / / display stack situation [traversing stack] public void list () {if (isEmpty ()) {System.out.println ("empty stack, no data ~"); return;} for (int I = top; I > = 0 IMel -) {System.out.printf ("stack [% d] =% d\ n", I, stack [I]);}} use the stack to complete the evaluation of the expression (infix expression)

Prepare two stacks, the number stack and the symbol stack.

1. Traverse the expression through an index value (index).

two。 If it is found to be a number, it goes directly into the number stack.

3. If it is a symbol, consider that if the current symbol stack is empty, enter directly. If the symbol stack has an operator, make a comparison.

If the priority of the current operator is less than or equal to the operator in the stack, it is necessary to pop two numbers from the stack, and then pop a character from the symbol stack. After the operation, the result is put into the number stack, and then the current operator is put into the symbol stack.

If the current operator takes precedence over the operator in the stack, it goes directly into the stack.

4. When the expression is scanned, the corresponding numbers and symbols are sequentially pop from the number stack and symbol stack, and run.

5. Finally, there is only one number in the number stack, which is the result of the expression.

Package com.structures.stack; public class Calculator {public static void main (String [] args) {/ / the expression String expression = "700 seconds 2 cycles 6-2"; / / Stack ArrayStack2 numStack = new ArrayStack2 (10); / / symbol Stack ArrayStack2 operStack = new ArrayStack2 (10); int index = 0 int index / used for scanning int num1 = 0; int num2 = 0 Int oper = 0; int res = 0; char ch =''; / / Save the char obtained from each scan to ch String keepNum = ""; / / for splicing multi-digit while (true) {ch = expression.substring (index, index + 1) .charat (0) / / if the operator if (operStack.isOper (ch)) {/ / if it is empty if (operStack.isEmpty ()) {operStack.push (ch);} else {if (operStack.priority (ch) = expression.length ()) {break } while (true) {if (operStack.isEmpty ()) {break;} num1 = numStack.pop (); num2 = numStack.pop (); oper = operStack.pop (); res = numStack.cal (num1, num2, oper); numStack.push (res) } System.out.printf ("expression% slots% d\ n", expression, numStack.pop ());}} class ArrayStack2 {the size of the private int maxSize;// stack private int [] stack;// array simulation stack, the data is put into the array private int top =-1 int maxSize top represents the top of the stack, initialize-1 public ArrayStack2 (int maxSize) {this.maxSize = maxSize Stack = new int [this.maxSize];} / returns the value at the top of the current stack, not pop public int peek () {return stack [top];} / / determines whether the stack is full public boolean isFull () {return top = = maxSize-1;} / / determines whether the stack is empty public boolean isEmpty () {return top = =-1 } / / public void push (int value) {if (isFull ()) {System.out.println ("stack full"); return;} top++; stack [top] = value;} / / out stack public int pop () {if (isEmpty ()) {throw new RuntimeException ("stack empty") } int value = stack [top]; top--; return value;} / / display stack situation [traversing stack] public void list () {if (isEmpty ()) {System.out.println ("empty stack, no data ~"); return;} for (int I = top; I > = 0 ) {System.out.printf ("stack [% d] =% d\ n", I, stack [I]);}} / / returns the priority of the operator. The higher the number, the higher the priority. / / assume that the current operator has only +-* / public int priority (int oper) {if (oper = ='*'| | oper = ='/') {return 1;} else if (oper = ='+'| | oper = ='-') {return 0;} else {return-1 }} / / determine whether it is an operator public boolean isOper (char val) {return val = ='+'| | val = ='-'| | val = ='*'| | val = ='/';} / / calculation method public int cal (int num1, int num2, int oper) {int res = 0 Switch (oper) {case'+': res = num1 + num2; break; case'-': res = num2-num1;// Note the order break; case'*': res = num1 * num2; break Case'/': res = num2 / num1;// pay attention to the order break;} return res;}} the above is shared by Xiaobian on how to use Java programming internal power stack. If you happen to have similar doubts, please refer to the above analysis to understand. If you want to know more about it, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.