c2c网站支付方式,平湖企业网站建设,wordpress 更换ip,怎么设立网站赚广告费栈简介 栈就像我们生活中堆叠的盘子一样后进先出#xff0c;只能从栈顶插入或者删除元素#xff0c;O(1)push(x)、pop()、Top()指向栈顶元素、IsEmpty()应用#xff1a;执行函数#xff0c;编辑器的撤回操作#xff0c;编译器使用栈可以验证代码中的括号是否匹配{[()]}
栈…栈简介 栈就像我们生活中堆叠的盘子一样后进先出只能从栈顶插入或者删除元素O(1)push(x)、pop()、Top()指向栈顶元素、IsEmpty()应用执行函数编辑器的撤回操作编译器使用栈可以验证代码中的括号是否匹配{[()]}
栈的实现方式
使用数组实现栈 空栈top值-1top大小不能超过数组大小否则会栈溢出。 时间复杂度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 (topMAX_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){StackCharacter stack new Stack();for (int i0;is.length;i){stack.push(s[i]);}for (int i0;is.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;StackNode s new Stack();Node temp head;while (temp!null){s.push(temp);temptemp.next;}temps.peek();//栈顶元素就是前面实现的TOP方法headtemp;s.pop();while(!s.isEmpty()){temp.nexts.pop();temp temp.next;}temp.nextnull;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){StackCharacter strings new Stack();for (int i0;iexp.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) {StackInteger 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) {StackInteger stack new Stack();String[] exp1 exp.split( );//根据空格进行分组//反转StackString stack1 new Stack();for (String s : exp1) {stack1.push(s);}for(int i0;iexp1.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) {StackString 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() p2p1 !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下一个位置使用 (i1)%N前一个位置为(iN-1)%N。当i是n-1时N/N0达到循环。
public class DataStruct {private int[] data;private int front;private int rear;private int capacity;public DataStruct(int capacity) {this.capacitycapacity;this.datanew int[capacity];this.front-1;this.rear-1;}public boolean IsEmpty(){if (front-1rear-1){return true;}return false;}public void enQueue(int x){if (rearcapacity-1) {System.out.println(数组已满);return;}if (rear-1front-1){front0;}rearrear1;data[rear]x;}public int deQueue(){if (front-1rear-1){System.out.println(没有需要删除的元素);return -1;}if (frontrear){front-1;rear-1;return data[0];}int x data[front];frontfront1;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.capacitycapacity;this.datanew int[capacity];this.front-1;this.rear-1;}public void enQueue(int x){if ((rear1)%capacityfront) {System.out.println(数组已满);return;}if (rear-1front-1){front0;}rear(rear1)%capacity;data[rear]x;}public int deQueue(){if (front-1rear-1){System.out.println(没有需要删除的元素);return -1;}if (frontrear){front-1;rear-1;return data[0];}int x data[front];front(front1)%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 frontnull;private Node rearnull;public void enQueue(int x){Node temp new Node(x);if (front null rear null){frontreartemp;return;}rear.nexttemp;reartemp;return;}public void deQueue(){if (front null){return;}frontfront.next;}public static void main(String[] args) {DataStruct ds new DataStruct();ds.enQueue(1);ds.enQueue(2);ds.enQueue(3);ds.deQueue();}
}练习
栈反转链表图书整理I
