当前位置：首页 > news >正文

网站制作软件安卓版做专业搜索引擎优化

news 2025/8/15 12:11:53

网站制作软件安卓版,做专业搜索引擎优化,品牌策划论文,企业网站哪家公司好栈简介栈就像我们生活中堆叠的盘子一样后进先出，只能从栈顶插入或者删除元素，O(1)push(x)、pop()、Top()指向栈顶元素、IsEmpty()应用：执行函数，编辑器的撤回操作，编译器使用栈可以验证代码中的括号是否匹配{[()]} 栈…

栈简介

请添加图片描述

栈就像我们生活中堆叠的盘子一样
后进先出，只能从栈顶插入或者删除元素，O(1)
push(x)、pop()、Top()指向栈顶元素、IsEmpty()
应用：执行函数，编辑器的撤回操作，编译器使用栈可以验证代码中的括号是否匹配{[()]}

栈的实现方式

使用数组实现栈

请添加图片描述

空栈top值-1，top大小不能超过数组大小，否则会栈溢出。
时间复杂度：best–O(1) 、worst–O(n)栈溢出情况需要将数组扩大，原来的数据复制到新的上面。

public class DataStruct {static final int MAX_SIZE = 10;int[] A = new int[MAX_SIZE];int top = -1;public void push(int x){if (top==MAX_SIZE-1){System.out.println("栈溢出");return;}A[++top]=x;}public void pop(){if (top==-1){System.out.println("空栈");return;}top--;}public int top(){return A[top];}public static void main(String[] args) {DataStruct ds = new DataStruct();ds.push(1);ds.print();ds.push(4);ds.print();ds.push(5);ds.print();ds.pop();ds.print();ds.push(90);ds.print();System.out.println(ds.top());}void print(){for (int i = 0; i <=top; i++) {System.out.print(A[i]);}System.out.println();}
}

使用链表实现栈

链表尾部插入或删除需要O(n)，所以我们从头部插入或删除。栈顶=表头

class Node {int data;Node next;public Node(int data){this.data = data;this.next = null;}
}
public class DataStruct {public Node push (Node head,int data){Node temp = new Node(data);temp.next = head;head = temp;return head;}public Node pop(Node head){if (head == null) return head;head = head.next;return head;}public int top(Node head){return head.data;}public static void main(String[] args) {DataStruct ds = new DataStruct();Node node = null;node = ds.push(node,1);node = ds.push(node,8);node = ds.push(node,9);node = ds.pop(node);System.out.println("栈顶："+ ds.top(node));while (node != null){System.out.println(node.data);node = node.next;}}
}

栈的使用场景

反转字符串/链表

请添加图片描述

因为栈是后入先出，所以很适合反转。java中栈是封装好的可以拿来即用（java.util.Stack）。由代码可以得到反转字符串时间/空间复杂度=O(n)，有更好的反转方法就是双指针s(n)=O(1)

import java.util.Stack;
public class DataStruct {public void reverse(char[] s){Stack<Character> stack = new Stack<>();for (int i=0;i<s.length;i++){stack.push(s[i]);}for (int i=0;i<s.length;i++){s[i]=stack.pop();}}public static void main(String[] args) {DataStruct ds = new DataStruct();char[] s = {'h','e','l','l','o'};ds.reverse(s);System.out.println(new String(s));}
}

反转链表用不了双指针，可以采用如下方法：

迭代法（上篇文章）
递归法（上篇文章）
栈，时间/空间复杂度=O(n)

import java.util.Stack;class Node {int data;Node next;public Node(int data){this.data = data;this.next = null;}
}
public class DataStruct {public Node Reverse(Node head){if (head == null) return null;Stack<Node> s = new Stack<>();Node temp = head;while (temp!=null){s.push(temp);temp=temp.next;}temp=s.peek();//栈顶元素就是前面实现的TOP方法head=temp;s.pop();while(!s.isEmpty()){temp.next=s.pop();temp = temp.next;}temp.next=null;return head;}public static void main(String[] args) {DataStruct ds = new DataStruct();Node node = new Node(2);node.next = new Node(5);node.next.next = new Node(3);node.next.next.next = new Node(8);node = ds.Reverse(node);while (node != null){System.out.println(node.data);node = node.next;}}
}

检查括号的匹配性

匹配条件：
请添加图片描述
方案：将所有左未关闭括号放在一个list中，当出现右括号与list最后一个元素匹配，匹配上则list删除最后一个元素，直到最后列表为空，表达式也扫描完毕，则括号匹配！
这是后入先出，总从一端插入删除元素----使用栈来解决：

import java.util.Stack;
public class DataStruct {public boolean checkBalance(String exp){Stack<Character> strings = new Stack<>();for (int i=0;i<exp.length();i++){if (exp.charAt(i)=='(' || exp.charAt(i)=='[' || exp.charAt(i)=='{'){strings.push(exp.charAt(i));}if (exp.charAt(i)==')' || exp.charAt(i)==']' || exp.charAt(i)=='}'){if (strings.isEmpty()) return false;Character pop = strings.pop();if ((pop=='(' && exp.charAt(i)!=')') || (pop=='[' && exp.charAt(i)!=']') || (pop=='{' && exp.charAt(i)!='}')){return false;}}}if (!strings.isEmpty()) return false;return true;}public static void main(String[] args) {DataStruct ds = new DataStruct();String exp ="{([)}";System.out.println(ds.checkBalance(exp));String exp2 ="{()()}";System.out.println(ds.checkBalance(exp2));String exp3 ="[()}";System.out.println(ds.checkBalance(exp3));}
}

中缀/前缀/后缀

定义

请添加图片描述
从计算机角度，中缀表达式要转换为前/后缀表达式，来进行求值会更简单。括号是为了增加可读性，计算机不需要可读性，故去掉。

代码编写：后缀/前缀表达式求值

请添加图片描述

import java.util.Stack;
public class DataStruct {//后缀表达式求值:从左到右，pop2操作符pop1public int EvaluatePostfix(String exp) {Stack<Integer> stack = new Stack<>();String[] exp1 = exp.split(" ");//根据空格进行分组boolean flag = true;for(String s : exp1){try{Integer.parseInt(s);flag = true;}catch(Exception e){flag = false;}if (flag){stack.push(Integer.parseInt(s));}else {Integer pop1 = stack.pop();Integer pop2 = stack.pop();switch (s) {case "+":stack.push(pop2 + pop1);break;case "-":stack.push(pop2 - pop1);break;case "*":stack.push(pop2 * pop1);break;case "/":stack.push(pop2 / pop1);}}}return stack.peek();}//前缀表达式求值: 从右到左扫描，pop1操作符pop2public int EvaluatePrefix(String exp) {Stack<Integer> stack = new Stack<>();String[] exp1 = exp.split(" ");//根据空格进行分组//反转Stack<String> stack1 = new Stack<>();for (String s : exp1) {stack1.push(s);}for(int i=0;i<exp1.length;i++){exp1[i] = stack1.pop();}boolean flag = true;for(String s : exp1){try{Integer.parseInt(s);flag = true;}catch(Exception e){flag = false;}if (flag){stack.push(Integer.parseInt(s));}else {Integer pop1 = stack.pop();Integer pop2 = stack.pop();switch (s) {case "+":stack.push(pop1 + pop2);break;case "-":stack.push(pop1 - pop2);break;case "*":stack.push(pop1 * pop2);break;case "/":stack.push(pop1 / pop2);}}}return stack.peek();}public static void main(String[] args) {DataStruct ds = new DataStruct();String exp ="2 3 * 5 4 * + 9 -";System.out.println(ds.EvaluatePostfix(exp));}
}

中缀如何转换为后缀

操作数放在list，操作符放在栈。
请添加图片描述
遇到操作数直接放入list，遇到操作符当栈空直接放入，当遇到操作符更高的，持续放入栈中，操作符弹出栈的条件：

遇见优先级低的操作符，持续弹出。但不能弹出左括号，左括号只能遇到右括号才能弹出
遇见右括号
字符结束

括号的情况：遇见左括号持续放入，遇见右括号持续弹出，直到弹出一个左括号结束。

import java.util.Objects;
import java.util.Stack;
public class DataStruct {public String infixToPostfix(String exp) {Stack<String> stack = new Stack<>();String[] exp1 = exp.split(" ");StringBuilder postfix = new StringBuilder();boolean flag = true;for (String s : exp1) {try{Integer.parseInt(s);flag = true;}catch(Exception e){flag = false;}if (flag){postfix.append(s);}else if (Objects.equals(s, "+") || Objects.equals(s, "-") || Objects.equals(s, "*") || Objects.equals(s, "/")){if (stack.isEmpty()){stack.push(s);continue;}String peek = stack.peek();int p1 = priority(peek);int p2 = priority(s);while(!stack.empty() && p2<=p1 && !stack.peek().equals("(")){postfix.append(stack.pop());}stack.push(s);}else if (Objects.equals(s, "(") || Objects.equals(s,")")){if (s.equals("(")){stack.push(s);continue;}while (!stack.peek().equals("(")){postfix.append(stack.pop());}stack.pop();}}while (!stack.empty()){postfix.append(stack.pop());}return postfix.toString();}//判断操作符优先级public int priority(String s){switch (s){case "+":case "-":return 1;case "*":case "/":return 2;default:return -1;}}public static void main(String[] args) {DataStruct ds = new DataStruct();String exp ="( ( 2 + 3 ) * 4 - 5 ) * 6";System.out.println(ds.infixToPostfix(exp));}
}

队列

先进先出(first in first out—FIFO)
队尾插入EnQueue()、队头删除DeQueue()、查询队头Peek()、isEmpty()
应用场景：排队等待的场景，譬如打印机打印
在这里插入图片描述

数组实现队列

front到rear是队列部分。
普通数组会发现rear到了数组末尾后，数组就满了，会有空闲位置。
可以用循环数组（下图只是逻辑视图），数组位置i，下一个位置使用 (i+1)%N，前一个位置为(i+N-1)%N。当i是n-1时，N/N=0，达到循环。
在这里插入图片描述

public class DataStruct {private int[] data;private int front;private int rear;private int capacity;public DataStruct(int capacity) {this.capacity=capacity;this.data=new int[capacity];this.front=-1;this.rear=-1;}public boolean IsEmpty(){if (front==-1&&rear==-1){return true;}return false;}public void enQueue(int x){if (rear==capacity-1) {System.out.println("数组已满");return;}if (rear==-1&&front==-1){front=0;}rear=rear+1;data[rear]=x;}public int deQueue(){if (front==-1&&rear==-1){System.out.println("没有需要删除的元素");return -1;}if (front==rear){front=-1;rear=-1;return data[0];}int x = data[front];front=front+1;return x;}public static void main(String[] args) {DataStruct ds = new DataStruct(3);System.out.println(ds.IsEmpty());ds.enQueue(1);ds.enQueue(2);ds.deQueue();ds.enQueue(3);ds.enQueue(4);}
}

循环数组实现：

public class DataStruct {private int[] data;private int front;private int rear;private int capacity;public DataStruct(int capacity) {this.capacity=capacity;this.data=new int[capacity];this.front=-1;this.rear=-1;}public void enQueue(int x){if ((rear+1)%capacity==front) {System.out.println("数组已满");return;}if (rear==-1&&front==-1){front=0;}rear=(rear+1)%capacity;data[rear]=x;}public int deQueue(){if (front==-1&&rear==-1){System.out.println("没有需要删除的元素");return -1;}if (front==rear){front=-1;rear=-1;return data[0];}int x = data[front];front=(front+1)%capacity;return x;}public static void main(String[] args) {DataStruct ds = new DataStruct(3);ds.enQueue(1);ds.enQueue(2);ds.deQueue();ds.enQueue(3);ds.enQueue(4);ds.enQueue(5);System.out.println(ds.deQueue());}
}

链表实现队列

在这里插入图片描述

class Node {int data;Node next;public Node(int data){this.data = data;this.next = null;}
}
public class DataStruct {private Node front=null;private Node rear=null;public void enQueue(int x){Node temp = new Node(x);if (front == null && rear == null){front=rear=temp;return;}rear.next=temp;rear=temp;return;}public void deQueue(){if (front == null){return;}front=front.next;}public static void main(String[] args) {DataStruct ds = new DataStruct();ds.enQueue(1);ds.enQueue(2);ds.enQueue(3);ds.deQueue();}
}