《Java初阶数据结构》----4.＜线性表---Stack栈和Queue队列＞

前言

      大家好，我目前在学习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());   // 获取栈中有效元素个数---> 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) {Stack<Character> 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) {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();//不匹配序列elsereturn 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());}}
}