前言

      大家好，我目前在学习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 栈的使用 

代码示例：

<code>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接口。 

<code>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 队列模拟实现

队列中既然可以存储元素，那底层肯定要有能够保存元素的空间，通过前面线性表的学习了解到常见的空间类型有 两种：顺序结构 和 链式结构。思考下：队列的实现使用顺序结构还是链式结构好？ 

 

 定义变量、用内部类定义队列的的节点、队头、队尾、队员数

<code> 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接口是比较多的，栈和队列均可以使用该接口。 

<code>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());

}

}

}