目录

栈

实现一个MyStack

1. push

2.pop

3.empty

4.peek

栈和链表的结合

括号匹配 

栈的压入、弹出序列

最小栈

MinStack

push ​编辑

 pop

 top

getMin

概念区分及思考：

队列

 offer（入队列）

poll（出队列）

peek（获取队头元素）

empty（判断是否为空）

 设计一个循环队列库

栈

栈(Stack) ：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈 顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据在栈顶。

 Stack的方法都很简单，用代码写一下就懂了

public static void main(String[] args) {Stack 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());}
}

但是我们仅仅了解这一些还不够，我们还需要了解到Stack的源码。

 但是很奇怪，为什么这个里面没有方法呢？栈到底是顺序表还是链表呢？

extends Vector 这个里面暗藏玄机。

 点进来，发现Stack没有成员变量，其实全部都是继承过来的。

所以可以知道：Stack是一个数组。

实现一个MyStack

栈的功能并不多，我们一个一个来。先创建一个栈：

public class MyStack {public int[] elem;public int usedSize;public static final int DEFAULT_SIZE = 10;public MyStack() {this.elem = new int[DEFAULT_SIZE];}
}

创建一个栈比较简单，创建一个数组就是创建一个栈，把栈的大小初始化为10，usedSize为使用的栈空间，同时也当做当前栈顶的元素的下标

 1. push

    public int push(int val) {if(isFull()) {                   如果栈已经满了，那么对栈空间扩容两倍elem = Arrays.copyOf(elem,2*elem.length);}this.elem[usedSize] = val;       下标为usedSize的元素为push的值usedSize++;return val;}public boolean isFull() {return usedSize == elem.length;   看看usedSize是否等于数组的长度}

2.pop

    public int pop() {if(empty()) {throw new MyEmptyStackException("栈为空！");}/*int ret = elem[usedSize-1];usedSize--;return ret;*/return elem[--usedSize];}

usedSize减一，这样就让原来的elem[usedSize]元素没有被指向，也就是弹出来了

public class MyEmptyStackException extends RuntimeException{public MyEmptyStackException() {}public MyEmptyStackException(String message) {super(message);}
}

3.empty

    public boolean empty() {return usedSize == 0;}

4.peek

    public int peek() {if(empty()) {throw new MyEmptyStackException("栈为空！");}return elem[usedSize-1];}

peek只获取栈顶的元素，并不会删除元素

同时在这里简单介绍一下中缀表达式转后缀表达式，了解即可

栈和链表的结合

逆序打印链表：

                 递归方式
void printList(Node head){if(null != head){printList(head.next);System.out.print(head.val + " ");}
}循环方式
void printList(Node head){if(null == head){return;}Stack s = new Stack<>();将链表中的结点保存在栈中Node cur = head;while(null != cur){s.push(cur);cur = cur.next;}

括号匹配 

 思路：把所有的左括号用栈存放，与又括号一一匹配：

if(ch2 == '[' && ch == ']' || ch2 == '(' && ch == ')' || ch2 == '{' && ch == '}') {stack.pop();
}else{return false;
}

但我们还要考虑到栈空了或者与右括号不匹配的情况，完整代码：

    public boolean isValid(String s) {Stack stack = new Stack<>();for(int i = 0; i < s.length();i++) {char ch = s.charAt(i);//1. 判断是不是左括号if(ch == '(' || ch == '[' || ch == '{') {stack.push(ch);}else {if(stack.empty()) {//2. 遇到了右括号 但是栈为空，此时不匹配！return false;}char ch2 = stack.peek();//3。 此时 如果满足 这里面的任何一个匹配逻辑 都是匹配的if(ch2 == '[' && ch == ']' || ch2 == '(' && ch == ')' || ch2 == '{' && ch == '}') {stack.pop();}else{return false;}}}//4. 当字符串遍历完成了，但是栈不为空，说明左括号还在栈当中没有匹配完成if(!stack.empty()) {return false;}return true;}

栈的压入、弹出序列

 思路：

运用栈来实现还是比较简单的，将pushA数组的元素按照下标入栈后，再依次与popA里面的元素相比较，只要是依次能够匹配上就说明这是匹配的出栈序列。

public class Solution {public boolean IsPopOrder(int [] pushA,int [] popA){Stack stack = new Stack<>();int j = 0;  j变量用来遍历popA数组for(int i = 0 ; i < pushA.length ; i++){stack.push(pushA[i]);while(j < popA.length && !stack.empty() && stack.peek() == popA[j]){stack.pop();j++;}}return stack.empty();}
}

最小栈

要实现minStack，仅仅用一个栈是不够的，需要两个栈：

第一个栈的元素正常进出，第二个栈仅仅进出比上一个元素小的元素。 

MinStack

class MinStack {Stack stack1;Stack minStack;public MinStack() {stack1 = new Stack<>();minStack = new Stack<>();}

新建两个栈，第一个栈存放所有元素，第二个栈仅存放最小的元素

push 

 先让需要push的元素进入到stack1里面去，如果minStack为空那么就push到minStack里面去，如果不为空就和minStack的顶端元素相比较，只有小于等于才push到里面去，代码的实现是很简单的：

    public void push(int val) {stack1.push(val);if(minStack.empty()){minStack.push(val);}else{if(minStack.peek()>=val){minStack.push(val);}}}

 pop

先让stack1pop一个元素出来，如果minStack的元素和这个元素相等，那么minStack的元素也就需要被pop

    public void pop() {if(!minStack.empty()){int x = stack1.pop();if(minStack.peek()==x){minStack.pop();}}}

 top

需要注意的是，该top返回的是stack1的元素

    public int top() {if(!stack1.empty()){return stack1.peek();}return -1;}

getMin

获取的是最小元素，但minStack中的元素就是最小元素，也即返回minStack中的顶元素

    public int getMin() {if(minStack.empty()){return -1;}return minStack.peek();}

概念区分及思考：

栈、虚拟机栈、栈帧有什么区别呢？

栈：是一种先进后出的数据结构。

虚拟机栈：是JVM的一块内存空间。

栈帧：是在调用函数的过程中，在java虚拟机栈上开辟的一块内存。

目前实现的栈，底层是数组实现，所以也可以叫做顺序栈。请问，由单链表来实现栈是否可以？（链式栈）

但是，双链表就可以完美的实现栈的所有功能，并且时间复杂度为O(1)。

但栈用数组来完成仍然是最优解。

队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾（Tail/Rear） 出队列：进行删除操作的一端称为队头 （Head/Front）。

java当中的队列基本上就是双向链表来实现的

 但是我们为了加大难度，我们通过单链表来实现一个队列，并且时间复杂度为O(1)。

 实现方法就是：通过给队尾加上一个tail，这样就可以让出入队时间复杂度都为O(1).

所以基础的构造就是：

    static class ListNode{public int val;public ListNode next;public ListNode(int val) {this.val = val;}}public ListNode head;public ListNode tail;public int Usedsize = 0;//记录队列的大小

 offer（入队列）

在这个我们自己实现的队列中，我们从尾入元素，从头出元素。也就类似于单链表里面的尾插法，从尾插入一个元素，Usedsize++。但我们仍需要注意链表如果为空需要分情况讨论。

    public void offer(int val){ListNode node = new ListNode(val);if(head == null){head = node;tail = node;}else{tail.next = node;tail = tail.next;}Usedsize++;}

poll（出队列）

只需要把head节点往后移，再返回之前的头结点的val值就能完成，但仍需要注意head为空的情况

    public int poll(){if(head == null){return -1;      这里抛异常会更好}int ret = head.val;head = head.next;if(head == null){   此时head已经是原head之后的节点了；如果head为空那么tail也需要置空tail = null;}Usedsize--;return ret;}

peek（获取队头元素）

返回队头的元素就行了

    public int peek(){if(head == null){return -1;}return head.val;}

empty（判断是否为空）

    public boolean empty(){return Usedsize == 0;}

 设计一个循环队列库

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。 环形队列通常使用数组实现。

在这个图中，内圈的是下标，外圈的是存放的元素。这就是一个数组，只不过不同的是首尾相连，变成了一个循环的数组。

我们采用rear表示队尾，front表示队头。

问题：rear怎么从7位置走到0位置？

   rear = (rear+1) % elem.length

我们先把基础的参数和构造方法写出来，构造数组来完成

    public int[] elem;public int front;public int rear;public MyCircularQueue(int k) {elem = new int[k];}

enQueue（入队）：

    public boolean deQueue() {if(isEmpty()){return false;}front = (front+1) % elem.length; 在没有循环的时候，front++就能满足要求，有循环的时候只有这样才能完成return true;}

isEmpty（判断是否为空）：

    public boolean isEmpty() {if(front == rear){    循环的时候，如果front和rear就代表这个循环队列为空return true;}return false;}

deQueue（出队）：

    public boolean deQueue() {if(isEmpty()){return false;}front = (front+1) % elem.length;  和入队是一样的逻辑return true;}

isFull（判断是否满了）：

    public boolean isFull() {if((rear+1) % elem.length == front){  如果front和当前的rear有这样的关系就说明满了return true;}return false;}

• Front: 从队首获取元素。如果队列为空，返回 -1 。
• Rear: 获取队尾元素。如果队列为空，返回 -1 。

      public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int index = rear == 0 ? elem.length-1 : rear-1;注意这里是一个三目操作符return index;}

完整代码：

class MyCircularQueue {public int[] elem;public int front;public int rear;public MyCircularQueue(int k) {elem = new int[k];}public boolean enQueue(int value) {if(isFull()){return false;}elem[rear] = value;rear = (rear+1) % elem.length;return true;}public boolean deQueue() {if(isEmpty()){return false;}front = (front+1) % elem.length;return true;}public int Front() {if(isEmpty()){return -1;}return elem[front];}public int Rear() {if(isEmpty()){return -1;}int index = rear == 0 ? elem.length-1 : rear-1;return index;}public boolean isEmpty() {if(front == rear){return true;}return false;}public boolean isFull() {if((rear+1) % elem.length == front){return true;}return false;}
}

栈和队列到此就结束了，总体来说比较简单，下一章就是二叉树哦！