网站前缀带wap的怎么做,义乌外发加工网是正规的吗,wordpress 更换主题,自助建站的优势前言 大家好#xff0c;我目前在学习java。之前也学了一段时间#xff0c;但是没有发布博客。时间过的真的很快。我会利用好这个暑假#xff0c;来复习之前学过的内容#xff0c;并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区…前言 大家好我目前在学习java。之前也学了一段时间但是没有发布博客。时间过的真的很快。我会利用好这个暑假来复习之前学过的内容并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区进行讨论 喜欢我文章的兄弟姐妹们可以点赞收藏和评论我的文章。喜欢我的兄弟姐妹们以及也想复习一遍java知识的兄弟姐妹们可以关注我呦我会持续更新滴 望支持一起加油呀 语言只是工具不能决定你好不好找工作决定你好不好找工作的是你的能力
学历本科及以上就够用了 本篇博客主要讲解Java基础语法中的 一、栈 1. 栈的概念 2. 栈的使用 3. 栈的模拟实现 4. 栈的常见编程题 二、队列 1. 队列的概念 2. 队列的使用 3.队列的模拟实现 4.队列的循环设计 三、双端队列 一、栈stack
1.1 栈的概念 栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。 栈中的数据元素遵守后进先出LIFOLast In First Out的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。
出栈栈的删除操作叫做出栈。出数据在栈顶。 Stack继承了VectorVector和ArrayList类似都是动态的顺序表不同的是Vector是线程安 全的。 1.2 栈的使用 代码示例
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()); // 获取栈中有效元素个数--- 4System.out.println(s.peek()); // 获取栈顶元素--- 4s.pop(); // 4出栈栈中剩余1 2 3栈顶元素为3System.out.println(s.pop()); // 3出栈栈中剩余1 2 栈顶元素为3if(s.empty()){System.out.println(栈空);}else{System.out.println(s.size());}
}
1.3 栈的模拟实现 变量的定义、包含定义一个数组存储栈、记录栈中元素个数、 定义一个静态常量便于初始化栈 private int[] elem;//定义一个数组来存储栈中元素private int useSize;//记录栈中元素private static final int DEFAULT_CAPACITY 10;//定义一个静态常量 获取栈的长度的方法 public int getUseSize() {return useSize;} 栈的有参构造方法。构造一个容量为DEFAULT_CAPACITY的栈 //构造一个容量为DEFAULT_CAPACITY的栈public MyStack(){this.elem new int[DEFAULT_CAPACITY];} 检测栈是否满了 //检测栈是否满了private boolean isFull(){return this.useSize this.elem.length;} 入栈将val放入栈 //将val放入栈public void push(int val){if (isFull()){this.elem Arrays.copyOf(this.elem,2*this.elem.length);}this.elem[useSize] val;} 出栈 将栈顶元素取出并返回 //将栈顶元素取出并返回public int pop(){if (isEmpty()){throw new EmptyException(Stack为空);}return elem[--useSize];}获取栈顶元素 //获取栈顶元素public int peek(){if (isEmpty()){throw new EmptyException(Stack为空);}return elem[useSize-1];} 检测栈是否为空 //检测栈是否为空private boolean isEmpty(){return this.useSize 0;}
1.4 栈的常见编程题
1.有效的括号 public boolean isValid(String s) {StackCharacter stack new Stack();
//判断是否为有效的括号具有先进后匹配的特点因此我们用栈。首先创建一个栈int len s.length(); //首先得到字符串长度if (len 0) { //如果字符串为空则返回truereturn true;}if (len % 2 1) { //括号成双成对因此如果字符串为奇数那么直接返回falsereturn false; } else { //如果为偶数符合预期则将字符串转字符数组。遍历这个字符数组char[] chars s.toCharArray();for (char ch : chars) { if (ch ( || ch [ || ch {) { //如果为左括号则入栈。stack.push(ch);}if (!stack.empty()) { //如果有左括号到这里栈一定不为空。如果栈为空则返回false因为先得有左括号才会是有效括号//接下来判断右括号如果遍历到右括号那么必有栈顶元素与之配对才会是有效括号并出栈栈顶元素。否则返回false。if (ch }) {if (stack.pop() ! {) {return false;}}if (ch ]) {if (stack.pop() ! [) {return false;}}if (ch )) {if (stack.pop() ! () {return false;}}} else { return false;}}} //最终判断栈是否为空若全是左括号那么就没有出栈。因此如果栈内有元素则为false。若匹配成功//栈为空返回truereturn stack.empty();}
2.逆波兰表达式求值
import java.util.Stack;
//运算方法是将数字入栈如果碰到运算符号。则出栈将第一个出栈元素放在运算符右边第二个出栈元素放入运算符左边
//计算这个结果并将这个计算结果入栈。重复以上操作。即可计算出逆波兰表达式的值。
public class Solution {public int evalRPN(String[] tokens) {StackInteger stack new Stack();int right;int left; for (String token:tokens) {switch (token){case :stack.push(stack.pop()stack.pop());break;case -:right stack.pop();left stack.pop();stack.push(left-right);break;case *:stack.push(stack.pop()*stack.pop());break;case /:right stack.pop();left stack.pop();stack.push(left/right);break;default:stack.push(Integer.parseInt(token)); //注意这里放入栈的时候要将字符串转整型类型}}return stack.peek();}
} 1.运算方法是将数字入栈如果碰到运算符号。则出栈将第一个出栈元素放在运算符右边第二个出栈元素放入运算符左边 2.计算这个结果并将这个计算结果入栈。重复以上操作。即可计算出逆波兰表达式的值。 3.栈的压入、弹出序列
import java.util.Stack;
public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA) {int n pushA.length;//辅助栈StackInteger s new Stack();//遍历入栈的下标int j 0;//遍历出栈的数组for(int i 0; i n; i){//入栈栈为空或者栈顶不等于出栈数组while(j n (s.isEmpty() || s.peek() ! popA[i])){s.push(pushA[j]);j;}//栈顶等于出栈数组if(s.peek() popA[i])s.pop();//不匹配序列elsereturn false;}return true;}
}4.最小栈
class MinStack {DequeInteger xStack;DequeInteger minStack;public MinStack() {xStack new LinkedListInteger();minStack new LinkedListInteger();minStack.push(Integer.MAX_VALUE);}public void push(int x) {xStack.push(x);minStack.push(Math.min(minStack.peek(), x));}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}
}1.5栈的应用场景
将递归转化为循环
比如逆序打印链表 递归方式 // 递归方式
void printList(Node head){if(null ! head){printList(head.next);System.out.print(head.val );}
} 循环方式 // 循环方式
void printList(Node head){if(null head){return;}StackNode s new Stack();// 将链表中的结点保存在栈中Node cur head;while(null ! cur){s.push(cur);cur cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val );}
} 二、队列
2.1队列的概念 队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out)。 入队列进行插入操作的一端称为队尾Tail/Rear 出队列进行删除操作的一端称为队头 Head/Front 在Java中Queue是个接口底层是通过链表实现的。 2.2 队列的使用 注意Queue是个接口在实例化时必须实例化LinkedList的对象因为LinkedList实现了Queue接口。 public static void main(String[] args) {QueueInteger q new LinkedList();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5); // 从队尾入队列System.out.println(q.size());System.out.println(q.peek()); // 获取队头元素q.poll();System.out.println(q.poll()); // 从队头出队列并将删除的元素返回if(q.isEmpty()){System.out.println(队列空);}else{System.out.println(q.size());}
}
2.3 队列模拟实现 队列中既然可以存储元素那底层肯定要有能够保存元素的空间通过前面线性表的学习了解到常见的空间类型有 两种顺序结构 和 链式结构。思考下队列的实现使用顺序结构还是链式结构好 定义变量、用内部类定义队列的的节点、队头、队尾、队员数 static class ListNode{private int val;private ListNode prev;private ListNode next;public ListNode(int val){this.val val;}private ListNode front;//队头private ListNode rear;//队尾private int useSize;//队员数} 得到队员数 public int getUseSize() {return useSize;} 入队 //入队操作相当于头插法public void offer(int x){ListNode node new ListNode(x);if(front null){front rear node;}else {node.next front;front.prev node;front node;}useSize;} 出队 //出队操作相当于删除尾节点public int poll(){if(rear null){return -1;}int ret rear.val;if(front rear){front null;rear null;return ret;}rear rear.prev;rear.next null;useSize--;return ret;} 获取队头元素 //获取队头元素public int peek(){if(front null){return -1;}return front.val;} 检测队列是否为空 //检测队列是否为空public boolean isEmpty(){return this.useSize 0;}
2.4 循环队列 实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解的生产者消费者模型就可以就会使用循环队列。 环形队列通常使用数组实现。 数组下标循环的小技巧 1. 下标最后再往后(offset 小于 array.length): index (index offset) % array.length 2. 下标最前再往前(offset 小于 array.length): index (index array.length - offset) % array.length 如何区分空与满 1. 通过添加 size 属性记录 2. 保留一个位置 3. 使用标记 三、双端队列 (Deque) 双端队列deque是指允许两端都可以进行入队和出队操作的队列deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队也可以从队尾出队和入队。 Deque是一个接口使用时必须创建LinkedList的对象。 在实际工程中使用Deque接口是比较多的栈和队列均可以使用该接口。 DequeInteger stack new ArrayDeque();//双端队列的线性实现
DequeInteger queue new LinkedList();//双端队列的链式实现 2.5设计循环队列
class MyCircularQueue {private int front;private int rear;private int capacity;private int[] elements;public MyCircularQueue(int k) {capacity k 1;elements new int[capacity];rear front 0;}public boolean enQueue(int value) {if (isFull()) {return false;}elements[rear] value;rear (rear 1) % capacity;return true;}public boolean deQueue() {if (isEmpty()) {return false;}front (front 1) % capacity;return true;}public int Front() {if (isEmpty()) {return -1;}return elements[front];}public int Rear() {if (isEmpty()) {return -1;}return elements[(rear - 1 capacity) % capacity];}public boolean isEmpty() {return rear front;}public boolean isFull() {return ((rear 1) % capacity) front;}
}
四、面试题
1.用队列实现栈
class MyStack {QueueInteger queue1;QueueInteger queue2;/** Initialize your data structure here. */public MyStack() {queue1 new LinkedListInteger();queue2 new LinkedListInteger();}/** Push element x onto stack. */public void push(int x) {queue2.offer(x);while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}QueueInteger temp queue1;queue1 queue2;queue2 temp;}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll();}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}
2.用栈实现队列 class MyQueue {DequeInteger inStack;DequeInteger outStack;public MyQueue() {inStack new ArrayDequeInteger();outStack new ArrayDequeInteger();}public void push(int x) {inStack.push(x);}public int pop() {if (outStack.isEmpty()) {in2out();}return outStack.pop();}public int peek() {if (outStack.isEmpty()) {in2out();}return outStack.peek();}public boolean empty() {return inStack.isEmpty() outStack.isEmpty();}private void in2out() {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}
}
