安阳网站建设哪家便宜,设计方案构思和设计过程,公司网站数据分析,域名和服务器多少钱文章目录 一、栈#xff08;Stack#xff09;1.概念2.栈的使用3.栈的模拟实现1、定义接口2、定义栈3、成员4、构造方法5、判断空间是否满 full6、入栈 push7、出栈 pop8、获取栈顶元素 peek9、获取栈中有效元素个数 size10、检测栈是否为空 empty完整代码 4.练习1、有效括号2… 文章目录 一、栈Stack1.概念2.栈的使用3.栈的模拟实现1、定义接口2、定义栈3、成员4、构造方法5、判断空间是否满 full6、入栈 push7、出栈 pop8、获取栈顶元素 peek9、获取栈中有效元素个数 size10、检测栈是否为空 empty完整代码 4.练习1、有效括号2、逆波兰表达式求值3、栈的压入弹出序列4、最小栈 5. 概念区分 二、队列1.概念2.队列的使用3.模拟实现1、成员2、入队列 offer3、出队列 poll4、获取队头元素 peek5、获取队列中有效元素个数 size6、检查队列是否为空 isEmpty完整代码 三、其他队列1.循环队列设计循环队列 2.双端队列3.练习 一、栈Stack
1.概念
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据在栈顶。
2.栈的使用
方法功能Stack()构造一个空的栈E push(E e)将e入栈E pop()将栈顶元素出栈E peek()获取栈顶元素int size()获取栈中有效元素个数boolean empty()检查栈是否为空 public static void main(String[] args) {StackInteger s new Stack();s.push(1);s.push(2);s.push(3);s.push(4);System.out.println(s.size());System.out.println(s.peek());s.pop();System.out.println(s.pop());if(s.empty()){System.out.println(栈空);}else{System.out.println(s.size());}}3.栈的模拟实现 从上图中可以看到Stack继承了VectorVector和ArrayList类似都是动态的顺序表不同的是Vector是线程安全的。
1、定义接口
public interface IStack {void push(int x);int pop();int peek();int size();boolean empty();//判断是否满boolean full();
}2、定义栈
public class MyStack implements IStack{Overridepublic void push(int x) {}Overridepublic int pop() {return 0;}Overridepublic int peek() {return 0;}Overridepublic int size() {return 0;}Overridepublic boolean empty() {return false;}Overridepublic boolean full() {return false;}
}
3、成员
存储数据的数组 private int usedSize;有效数据的个数 private int usedSize;默认大小 private static final int DEFAULT_CAPACITY 10;4、构造方法 public MyStack(){elem new int[DEFAULT_CAPACITY];}5、判断空间是否满 full Overridepublic boolean full() {if(usedSize elem.length){return true;}return false;}6、入栈 push Overridepublic void push(int x) {if(full()){elem Arrays.copyOf(elem,elem.length*2);}elem[usedSize] x;}7、出栈 pop
public class EmptyException extends RuntimeException{public EmptyException(String msg){super(msg);}}
-------------------------------------Overridepublic int pop() {if(empty()){//抛异常throw new EmptyException(栈空出栈异常);}int old elem[usedSize--];//如果是引用就需要置空return old;}
8、获取栈顶元素 peek Overridepublic int peek() {if(empty()){//抛异常throw new EmptyException(栈空);}return elem[usedSize-1];}9、获取栈中有效元素个数 size Overridepublic int size() {return usedSize;}10、检测栈是否为空 empty Overridepublic boolean empty() {return usedSize0;}完整代码
public class EmptyException extends RuntimeException{public EmptyException(String msg){super(msg);}}----------------------------
public interface IStack {void push(int x);int pop();int peek();int size();boolean empty();//判断是否满boolean full();
}----------------------------------
import java.util.Arrays;public class MyStack implements IStack{private int [] elem;private int usedSize;private static final int DEFAULT_CAPACITY 10;public MyStack(){elem new int[DEFAULT_CAPACITY];}Overridepublic boolean full() {if(usedSize elem.length){return true;}return false;}Overridepublic void push(int x) {if(full()){elem Arrays.copyOf(elem,elem.length*2);}elem[usedSize] x;}Overridepublic int pop() {if(empty()){//抛异常throw new EmptyException(栈空出栈异常);}int old elem[usedSize--];return old;}Overridepublic int peek() {if(empty()){//抛异常throw new EmptyException(栈空);}return elem[usedSize-1];}Overridepublic int size() {return usedSize;}Overridepublic boolean empty() {return usedSize0;}
}
4.练习
1、有效括号
有效括号 开一个栈遇到左括号进栈遇到右括号检查栈顶和遇到右括号是否匹配。
class Solution {public boolean isValid(String s) {StackCharacter st new Stack();for(int i 0;is.length();i){char c s.charAt(i);if(c(||c{||c[){st.push(c);}else{if(c)!st.empty()){if(st.peek()!(){return false;}st.pop();}else if(c}!st.empty()){if(st.peek()!{){return false;}st.pop();}else if(c]!st.empty()){if(st.peek()![){return false;}st.pop();}else {return false;}}}if(st.empty()){return true;}return false;}
}2、逆波兰表达式求值
逆波兰表达式 判断是操作数还是算符如果是操作数转Int存在栈不是就按算符进行运算。
class Solution {boolean isOperation(String s){if(s.equals()||s.equals(-)||s.equals(*)||s.equals(/)){return true;}return false;}public int evalRPN(String[] tokens) {StackInteger st new Stack();for(int i 0;itokens.length;i){String s tokens[i];if(isOperation(s)){int right 0;int left0 ;if(st.size()2){right st.pop();left st.pop();}if(s.equals()){st.push(leftright);}else if(s.equals(-)){st.push(left-right);}else if(s.equals(*)){st.push(left*right);}else if(s.equals(/)){st.push(left/right);}}else{int temp Integer.parseInt(s);st.push(temp);}}return st.peek();}
}3、栈的压入弹出序列
栈的压入弹出序列 先创建一个栈模拟压入循环检查是否可以出栈如果符合就出栈不符合继续压入直到全部压入但不能出栈即为不符合弹出序列。
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可*** param pushV int整型一维数组* param popV int整型一维数组* return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {StackInteger st new Stack();int cur1 0;int cur2 0;int len pushV.length;while(cur1len||cur2len){if(cur1len){st.push(pushV[cur1]);}while(cur2len){if(!st.empty()st.peek()popV[cur2]){st.pop();cur2;}else {if(cur1len){break;}else{return false;}}}cur1;}return st.empty();}
}4、最小栈
最小栈 开两个栈一个存最小值的栈一个就是普通的栈。在入栈的时候判断存最小值的栈是否为空,空就同时入这两个栈不为空就要比较存最小值的栈上面的值和新入的值如果比最小栈的值还小或等于就同时入两栈否则只入普通栈。
class MinStack {private StackInteger stack;private StackInteger minStack;public MinStack() {stack new Stack();minStack new Stack();}public void push(int val) {stack.push(val);if(minStack.empty()){minStack.push(val);}else{if(minStack.peek()val){minStack.push(val);}}}public void pop() {if(minStack.peek().equals(stack.peek())){minStack.pop();}stack.pop();}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}5. 概念区分
栈、虚拟机栈、栈帧有什么区别 栈数据结构 虚拟机栈JVM划分的一款内存而已 栈帧调用方法的时候会在虚拟机当中给这个方法开辟一块内存
二、队列
1.概念
队列只允许在一端进行插入数据操作在另一端就进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一端称为队头Head/Front
2.队列的使用
在Java中Queue是个接口底层是通过链表实现的。
方法功能boolean offer(E e)入队列E poll()出队列peek()获取队头元素int size()获取队列中有效元素个数boolean isEmpty()检查队列是否为空
注意Queue是个接口在实例化时必须实例化LinkedList的对象因为LinkedList实现了Queue接口。 public static void main(String[] args) {QueueInteger queue new LinkedList();queue.offer(1);queue.offer(2);queue.offer(3);System.out.println(queue.size());System.out.println(queue.peek());queue.poll();System.out.println(queue.isEmpty());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.isEmpty());}3.模拟实现
1、成员
双向链表节点 static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val val;}}头尾引用 public ListNode head;public ListNode last;节点个数 public int size;2、入队列 offer boolean offer(int val){ListNode node new ListNode(val);if(headnull){head node;last node;}else{last.next node;node.prev last;last node;}size;return true;}3、出队列 poll
public int poll(){if(headnull){return -1;}int ret head.val;if(head.nextnull){head null;last null;return ret;}head.next.prev null;head head.next;return ret;}4、获取队头元素 peek public int peek(){if(headnull){return -1;}return head.val;}5、获取队列中有效元素个数 size public int size(){return size;}6、检查队列是否为空 isEmpty public boolean isEmpty(){return size0;}完整代码
package queuedemo;import java.util.List;public class MyLinkQueue {static class ListNode{public int val;public ListNode next;public ListNode prev;public ListNode(int val){this.val val;}}public ListNode head;public ListNode last;public int size;boolean offer(int val){ListNode node new ListNode(val);if(headnull){head node;last node;}else{last.next node;node.prev last;last node;}size;return true;}public int poll(){if(headnull){return -1;}size--;int ret head.val;if(head.nextnull){head null;last null;return ret;}head.next.prev null;head head.next;return ret;}public int peek(){if(headnull){return -1;}return head.val;}public int size(){return size;}public boolean isEmpty(){return size0;}}三、其他队列
1.循环队列
实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。 问题 如何判断是空还是满 解决空还是满有很多种方案 1.使用usedSize进行记录 2.浪费一个空间来表示满 3.使用标记 如何从7下标来到0下标? 队尾指针1%len
设计循环队列
设计循环队列 class MyCircularQueue {public int [] elem;int front 0;int rear 0;public MyCircularQueue(int k) {elem new int[k1];}public boolean enQueue(int value) {if(isFull()){return false; }elem[rear] value;rear (rear1)%elem.length;return true;}public boolean deQueue() {if(isEmpty()){return false;}front (front1)%elem.length;return true;}public int Front() {if(isEmpty()){return-1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int temp (rear-1elem.length)%elem.length;return elem[temp];}public boolean isEmpty() {return frontrear;}public boolean isFull() {return (rear1)%elem.lengthfront;}
}2.双端队列
双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队也可以从队尾出队和入队。 Deque是一个接口使用时必须创建LinkedList的对象。
DequeInteger stack new ArrayDeque();//双端队列的线性实现
DequeInteger queue new LinkedList();//双端队列的链式实现
3.练习
队列实现栈
class MyStack {QueueInteger que1;QueueInteger que2;public MyStack() {que1 new LinkedList();que2 new LinkedList();}public void push(int x) {if(que1.isEmpty()que2.isEmpty()){que1.offer(x);}else{if(que1.isEmpty()){que2.offer(x);}else{que1.offer(x);}}}public int pop() {int size ;if(que1.isEmpty()){size que2.size();for(int i 0;isize-1;i){que1.offer(que2.poll());}return que2.poll();}else{size que1.size();for(int i 0;isize-1;i){que2.offer(que1.poll());}return que1.poll();}}public int top() {if(que1.isEmpty()){int size que2.size();for(int i 0;isize-1;i){que1.offer(que2.poll());}int ret que2.poll();que1.offer(ret);return ret;}else{int size que1.size();for(int i 0;isize-1;i){que2.offer(que1.poll());}int ret que1.poll();que2.offer(ret);return ret;}}public boolean empty() {return que2.isEmpty()que1.isEmpty();}
}栈实现队列
class MyQueue {StackInteger stack1;StackInteger stack2;public MyQueue() {stack1 new Stack();//入队列stack2 new Stack();//出列}public void push(int x) {stack1.push(x);}public int pop() {if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack2.isEmpty()stack1.isEmpty();}
}
