阅读量:0
前言
大家好，我目前在学习java。之前也学了一段时间，但是没有发布博客。时间过的真的很快。我会利用好这个暑假，来复习之前学过的内容，并整理好之前写过的博客进行发布。如果博客中有错误或者没有读懂的地方。热烈欢迎大家在评论区进行讨论！！！
喜欢我文章的兄弟姐妹们可以点赞，收藏和评论我的文章。喜欢我的兄弟姐妹们以及也想复习一遍java知识的兄弟姐妹们可以关注我呦，我会持续更新滴，
望支持！！！！！！一起加油呀！！！！
语言只是工具，不能决定你好不好找工作，决定你好不好找工作的是你的能力！！！！！
学历本科及以上就够用了！！！！！！！！！！！！！！！！！！！！！！
本篇博客主要讲解Java基础语法中的
一、栈
1. 栈的概念
2. 栈的使用
3. 栈的模拟实现
4. 栈的常见编程题
二、队列
1. 队列的概念
2. 队列的使用
3.队列的模拟实现
4.队列的循环设计
三、双端队列
一、栈（stack）
1.1 栈的概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安 全的。
1.2 栈的使用
代码示例：
public static void main(String[] args) { Stack<Integer> s = new Stack(); s.push(1); s.push(2); s.push(3); s.push(4); System.out.println(s.size()); // 获取栈中有效元素个数---> 4 System.out.println(s.peek()); // 获取栈顶元素---> 4 s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3 System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3 if(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) { Stack<Character> stack = new Stack<>(); //判断是否为有效的括号，具有先进后匹配的特点，因此我们用栈。首先创建一个栈 int len = s.length(); //首先得到字符串长度 if (len == 0) { //如果字符串为空，则返回true return true; } if (len % 2 == 1) { //括号成双成对，因此如果字符串为奇数，那么直接返回false return 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。若匹配成功 //栈为空，返回true return stack.empty(); }2.逆波兰表达式求值
import java.util.Stack; //运算方法是将数字入栈，如果碰到运算符号。则出栈将第一个出栈元素放在运算符右边，第二个出栈元素放入运算符左边 //计算这个结果，并将这个计算结果入栈。重复以上操作。即可计算出逆波兰表达式的值。 public class Solution { public int evalRPN(String[] tokens) { Stack<Integer> 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; //辅助栈 Stack<Integer> 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(); //不匹配序列 else return false; } return true; } } 4.最小栈
class MinStack { Deque<Integer> xStack; Deque<Integer> minStack; public MinStack() { xStack = new LinkedList<Integer>(); minStack = new LinkedList<Integer>(); 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; } Stack<Node> 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) { Queue<Integer> 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接口是比较多的，栈和队列均可以使用该接口。
Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现 Deque<Integer> 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 { Queue<Integer> queue1; Queue<Integer> queue2; /** Initialize your data structure here. */ public MyStack() { queue1 = new LinkedList<Integer>(); queue2 = new LinkedList<Integer>(); } /** Push element x onto stack. */ public void push(int x) { queue2.offer(x); while (!queue1.isEmpty()) { queue2.offer(queue1.poll()); } Queue<Integer> 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 { Deque<Integer> inStack; Deque<Integer> outStack; public MyQueue() { inStack = new ArrayDeque<Integer>(); outStack = new ArrayDeque<Integer>(); } 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()); } } } 