方法	解释
Stack()	构造一个空的栈
E push(E e)	将 e 入栈，并返回e
E pop()	将栈顶元素出栈并返回
E peek()	获取栈顶元素
int size()	获取栈中有效元素个数
boolean empty()	检测栈是否为空

public static void main(String[] args) {    Stack stack = new Stack();    stack.push(1);    stack.push(2);    stack.push(3);    stack.push(4);    stack.push(5);    System.out.println(stack.size());//5    //获取栈顶元素    System.out.println(stack.peek());//5    System.out.println(stack);  //[1, 2, 3, 4, 5]    stack.pop();//出栈  5    System.out.println(stack.size());//4    System.out.println(stack);  //[1, 2, 3, 4]    System.out.println(stack.empty());//false}

1.3 栈的模拟实现

由图可知Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的。

public class MyStack {    int[] elem;    int usedSize;    public MyStack(){        elem = new int[3];    }    //判断栈是否满了    private boolean CapacityIsFull(){        return  usedSize == elem.length;    }    //确保容量充足    private  void  ensureCapacity(){        if(CapacityIsFull()){            elem = Arrays.copyOf(elem,elem.length*2);        }    }    //入栈    public int push(int data){        ensureCapacity();        elem[usedSize++] = data;        return  data;    }    //获取栈顶元素    public int peek(){        if(usedSize == 0){            throw new StackNullEception("栈为空，无法获取栈顶元素");        }        return  elem[usedSize-1];    }    //出栈    public int pop (){        int e = peek();        usedSize--;        return  e;    }    //获取栈的长度    public  int size(){        return  usedSize;    }    //判断栈是否为空    public boolean empty(){        return  usedSize == 0;    }}

1.4 栈的应用场景

1. 改变元素的序列

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（） A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1 2. 一个栈的初始状态为空。现将元素 1 、 2 、 3 、 4 、 5 、 A 、 B 、 C 、 D 、 E 依次入栈，然后再依次出栈，则元素出栈的顺序是（）。 A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA

2. 将递归转化为循环

//递归方式void printList(node head){    if(head == null){        return;    }    printList(head.next);    System.out.println(head.val+" ");}//循环方式void printList2(Node head){    if(head == null){        return;    }    Stack stack = new Stack<>();    //将链表中的元素(节点)放入栈中    Node cur = head;    while(cur !=null){        stack.push(cur);        cur = cur.next;    }    //栈中的元素出栈    while (!stack.empty()){        System.out.print(stack.pop().val+" ");    }}

3. 括号匹配

代码实现

public boolean isValid(String s) {

Stack stack = new Stack<>();

for(int i = 0; i< s.length(); i++){

char ch = s.charAt(i);

if(ch == '(' || ch == '[' || ch == '{'){

stack.push(ch);

} else {

if(stack.empty()){

return false;

}

//从栈中取栈顶

char ch1 = stack.pop();

if((ch1 =='(' && ch == ')') || (ch1 == '[' && ch == ']') || (ch1 == '{' && ch == '}')){

continue;

} else {

return false;

}

}

}

//栈中还有左括号

if(!stack.empty()){

return false;

}

return true;

}

4. 逆波兰表达式求值

代码实现

public int evalRPN(String[] tokens) {

Stack stack = new Stack();

for(String s:tokens){

if(!(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/"))){

stack.push(Integer.parseInt(s));

}else{

int num2 = stack.pop();

int num1 = stack.pop();

switch(s){

case "+":

stack.push(num1+num2);

break;

case "-":

stack.push(num1-num2);

break;

case "*":

stack.push(num1*num2);

break;

case "/":

stack.push(num1/num2);

break;

}

}

}

return stack.pop();

}

5. 出栈入栈次序匹配

代码实现

public boolean IsPopOrder (int[] pushV, int[] popV) {

Stack stack = new Stack<>();

//i遍历pushV，j遍历popV

int i = 0, j = 0;

for(;i < pushV.length; i++){

//入栈

stack.push(pushV[i]);

//获取栈顶元素

int pe = stack.peek();

//判断栈顶元素是否需要出栈

while(pe == popV[j]){

stack.pop();

j++;

//栈空

if(stack.empty()){

break;

}

//判断后面是否需要出栈

pe = stack.peek();

}

}

//栈中还有元素

if(!stack.empty()){

return false;

}

return true;

}

6. 最小栈

代码实现

class MinStack {

//普通栈

private Stack stack;

//最小值栈-》存放当前普通栈中的最小值

private Stack minStack;

public MinStack() {

stack = new Stack<>();

minStack = new Stack<>();

}

//入栈

public void push(int val) {

if(stack.empty()){

stack.push(val);

minStack.push(val);

}else {

stack.push(val);

int peek = minStack.peek();

//判断minStack是否要入栈

if(val <= peek){

minStack.push(val);

}

}

}

//出栈

public void pop() {

//普通栈为空

if(stack.empty()){

return;

}

int po= stack.pop();

//判断minStack是否要出栈

if(po == minStack.peek()){

minStack.pop();

}

}

//获取栈顶元素

public int top() {

//普通栈为空

if(stack.empty()){

return -1;

}

return stack.peek();

}

//获取当前栈中最小值

public int getMin() {

//最小值栈-》空

if(minStack.empty()){

return -1;

}

return minStack.peek();

}

}

1.5 概念区分

栈、虚拟机栈、栈帧有何区别？

栈是一种数据结构，虚拟机栈是JVM划分的一块内存，栈帧是方法调用时，虚拟机给方法分配的一块内存。

二、队列

2.1 概念

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

2.2 队列的使用

Queue是个接口，底层是通过链表实现。

方法	解释
boolean offer(E e)	入队列
E poll()	出队列并返回
E peek()	获取队头元素
int size()	获取队列中有效长度的个数
boolean isEmpty	判断队列是否为空

Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。

public static void main(String[] args) {    Queue queue = new LinkedList<>();    //入队    queue.offer(1);    queue.offer(2);    queue.offer(3);    System.out.println(queue);//[1, 2, 3]    //获取队头元素    int t = queue.peek();    System.out.println(t);//1    //出队    System.out.println(queue.poll());//1    System.out.println(queue);//[2, 3]    //判断队列是否为空    boolean bool = queue.isEmpty();    System.out.println(bool);//false}

2.3 队列的模拟实现

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

public class MyLinkqueue {    static  class  ListNode{        int val;        ListNode next;        ListNode pre;        public ListNode(int val){            this.val = val;        }    }    ListNode first;//队头    ListNode last;//队尾    int usedsize;//队列中元素个数    //入队列    public boolean offer(int data){        ListNode node = new ListNode(data);        if(first == null){            //空队列            first = node;            last = node;        }else {            last.next = node;            node.pre = last;            last = last.next;        }        usedsize++;        return  true;    }    //获取队头元素    public int peek(){        if(usedsize == 0){            return -1;        }        return first.val;    }    //出队列    public int poll(){        int x = peek();        //只有一个元素        if(first.next==null){            first = null;            last = null;        }        first = first.next;        first.pre = null;        usedsize--;        return  x;    }    //获取队列中元素的个数    public int size(){        return usedsize;    }    //判断队列是否为空    public boolean isEmpty(){        return usedsize == 0;    }}

2.4 循环队列

实际中我们有时会使用一种队列叫循环队列，环形队列通常使用数组实现。

设计循环队列

三、双端队列

双端队列（deque）指允许两端都可以进行入队和出队操作的队列，说明元素可以从队头入队和出队，也可以从队尾入队和出队。

Deque是一个接口，使用时必须创建LinkedList的对象。

实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque stack = new ArrayDeque<>();// 双端队列的线性实现 Deque queue = new LinkedList<>();//双端队列的链式实现

四、面试题

1、用队列实现栈链接

代码实现

class MyStack {

private Queue queue1 ;

private Queue queue2 ;

public MyStack() {

queue1 = new LinkedList<>();

queue2 = new LinkedList<>();

}

//入栈

public void push(int x) {

//栈为空

if (empty()){

queue1.offer(x);

}else {

//放入非空队列中

if(!queue1.isEmpty()){

queue1.offer(x);

}else {

queue2.offer(x);

}

}

}

//出栈

public int pop() {

//栈空

if(empty()){

return -1;

}

if(!queue1.isEmpty()){

//将queue1中的size-1个元素放入queue2

while (queue1.size()>1){

int x= queue1.poll();

queue2.offer(x);

}

//出队x并返回x

int x = queue1.poll();

return x;

}else {

//将queue2中的size-1个元素放入queue1

while (queue2.size()>1){

int x= queue2.poll();

queue1.offer(x);

}

//出队x并返回x

int x = queue2.poll();

return x;

}

}

//获取栈顶元素

public int top() {

//栈空

if(empty()){

return -1;

}

if(!queue1.isEmpty()){

//将queue1中的size-1个元素放入queue2

while (queue1.size()>1){

int x= queue1.poll();

queue2.offer(x);

}

//出队x放入另一队列并返回x

int x = queue1.poll();

queue2.offer(x);

return x;

}else {

//将queue2中的size-1个元素放入queue1

while (queue2.size()>1){

int x= queue2.poll();

queue1.offer(x);

}

//出队x放入另一队列并返回x

int x = queue2.poll();

queue1.offer(x);

return x;

}

}

//判断栈是否为空

public boolean empty() {

//两个队都为空-》栈为空

return queue1.isEmpty() && queue2.isEmpty();

}

}

2、用栈实现队列链接

代码实现

class MyQueue {

private Stack stack1;//入队

private Stack stack2;//出队

public MyQueue() {

stack1 = new Stack<>();

sstack2 = new Stack<>();

}

//入队

public void push(int x) {

stack1.push(x);

}

//出队

public int pop() {

//队空

if(empty()){

return -1;

}

//保证stack2不为空

if(stack2.isEmpty()){

while (!stack1.isEmpty()){

stack2.push(stack1.pop());

}

}

return stack2.pop();

}

//获取队头元素

public int peek() {

//队空

if(empty()){

return -1;

}

//保证stack2不为空

if(stack2.isEmpty()){

while (!stack1.isEmpty()){

stack2.push(stack1.pop());

}

}

return stack2.peek();

}

//判断队列是否为空

public boolean empty() {

//两个栈都为空-》队列为空

return stack1.isEmpty() && stack2.isEmpty();

}

}