数据结构—栈和队列

栈：

概念：

栈是一种特殊的线性表，只允许在一端插入元素和取出表中的元素，插入元素和删除元素的一端叫栈顶，另一端叫栈底

压栈：在栈顶插入元素出栈：在栈顶将元素删除

栈的元素出栈遵循“先进后出”的原则。

栈的使用：

public static void main(String[] args) {//创建一个栈Stack<String> st1 = new Stack<>();//进行压栈st1.push("a");st1.push("b");st1.push("c");st1.push("d");//判断栈是否为空System.out.println(st1.empty());//将栈顶元素弹出栈再返回System.out.println(st1.pop());//获取栈内元素数目System.out.println(st1.size());//获取栈顶元素System.out.println(st1.peek());}

栈的应用场景：

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(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 + " ");}
}

队列：

概念：

队列是一种只允许在一端进行元素插入，在另一端进行元素删除的特殊线性表。删除元素的一端是队头，插入元素的一端是队尾。

队列的使用：

队列是一个底层接口，在进行实例化的时候要实例化Linklist对象，因为是linklist接口实现了Queue

对应Queue的API:

入队和出队：

稍作思考：如果要模拟实现队列，应该选择线性结构还是顺序结构比较好？？

就插入和删除元素的方式来看，显而易见是链式结构更为合适。用链表实现，在实现入队和出队操作时不必考虑容量的问题，对顺序表的元素进行操作容易牵一发而动全身，改一个队头就所有元素得进行改动

模拟实现：

思路：

先定义节点，节点中要有：①元素的值域 ②用于访问上一个元素的引用

将先入队的元素作为队头，后续插入的元素作为队尾。由于单向队列只能在队头出队，在队尾入队，我们在链表进行插入的时候选择用尾插法（如果是双向队列就头插法和尾插法都可以，出队操作就是删除头or尾节点）

代码实现：

class quenode
{//元素的值public  int val;public quenode prev;public quenode next;public quenode(int val){this.val = val;}public quenode(){}
}public class Quque implements que{//队头public quenode first;//队尾public quenode last;@Overridepublic Boolean isEmpty(){if(last != null){return false;}return  true;}@Override//入队① 队尾入队public void rearinputque(int val){quenode node = new quenode(val);if( first == null ){first = node;last  = first;}else {last.next = node;last = last.next;}}@Override//入队② 队头入队public void frontinputque(int val){quenode node = new quenode(val);if(first == null){first = node;last = first;}else {first.prev  = node;node.next = first;first = first.prev;}}@Override//出队①（单向队列）public void frontoutputque(){//改变链表的头结点就行//1、先判断队列是否为空if(isEmpty()){//队列为空，无法删除System.out.printf("队列为空！");}else {first = first.next;}}//遍历队列@Overridepublic void print() {if(first == null){return;}else {quenode que = first;while (que!=null){System.out.printf(String.valueOf(que.val)+" ");que = que.next;}}}@Override//出队② (双向队列) 队尾出队public void rearoutputque(){//改变链表的头结点就行//1、先判断队列是否为空if(first == null){//队列为空，无法删除System.out.printf("队列为空！");}else {last = last.prev;last.next = null;}}public static void main(String[] args) {Quque que = new Quque();quenode q1 = new quenode(5);quenode q2 = new quenode(4);quenode q3 = new quenode(3);quenode q4 = new quenode(2);quenode q5 = new quenode(1);que.frontinputque(q1.val);que.frontinputque(q2.val);que.frontinputque(q3.val);que.frontinputque(q4.val);que.frontinputque(q5.val);que.rearoutputque();que.frontoutputque();que.print();}
}

循环队列

用数组简单实现

主要思路：让队列头尾相连即可（数组下标实现循环），实现的方法有两种：一种是要浪费一个空间，另一种则是不需要浪费一个空间但是需要一个变量用来进行计数。

不浪费空间的做法：

浪费一个空间的做法：

入队列：给队列填入元素（数组赋值）前，得已进行判断队列是否为满，只要不满就能往队尾填入元素。每次填入元素之后就让rear往后走，即 rear == (rear+1) % elem.length;

出队列：改变队头（front往后走），然后每次进行出队列操作之后将计数usedsize减一，表示队列元素减少一个

判断队列是否为满/空：当计数 == 队列长度则为满，当计数 == 0 队列为空

获得队头元素：先对队列进行判断，不为空直接返回elem[front]

获得队尾元素：先对队列进行判断，队列不为空：

①队列为满(此时的rear下标已经完成循环了，rear==0)，直接返回elem[elem.length-1]

②队列不满，直接返回[rear-1]

力扣链接：622. 设计循环队列 - 力扣（LeetCode）

代码实现：

class MyCircularQueue
{public int[] elem;                        //用来放元素的队列public int front;                         //队头public int rear;                          //队尾  public int usesized ;                     //用来计数入队元素个数public MyCircularQueue(int k) {elem = new int[k];                    //重写队列的构造方法，用来定义队列的长度}//入队列public Boolean enQueue(int value) {        if(isFull()){return false;}elem[rear] = value;usesized++;rear = (rear+1)%elem.length;return true;}//出队列public Boolean deQueue() {if(isEmpty()){return false;}front  = (front+1)%elem.length;      //出队列就把队头往后挪（front往后走一步） usesized--;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 elem[index];}//判断队列是否为空public Boolean isEmpty() {return usesized == 0;}//判断队列是否为满public Boolean isFull() {return usesized == elem.length;}
}

用栈实现队列，用队列实现栈

用队列实现栈：

一个队列不能实现栈，因为队列的特性是头出尾进，要两个队列才能够实现栈。

如何判断为空栈？

当两个队列都为空说明模拟的栈是空栈。

如何解决压栈和出栈？

选择一个空队列负责实现元素压栈，当要出栈的时候就把队列的除了队尾元素的其他元素都放到另一个队列中，将队尾元素出队列就是实现出栈。

将除了队尾元素的其他元素全部出队列，然后依序入队到另一个队列里

后面如果有压栈操作，依旧是将元素压入不为空的队列，即——两个队列总有一个是空的，用来放除了栈顶元素的其他元素

力扣链接：225. 用队列实现栈 - 力扣（LeetCode）

代码实现：

class MyStack {private Queue<Integer> q1;private Queue<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2 = new LinkedList<>();}public void push(int x) {if(empty()){q1.offer(x);return;}if(!q1.isEmpty()){q1.offer(x);}else{q2.offer(x);}}public int pop() {if(empty()){return -1;}if(!q1.isEmpty()){int size = q1.size();for(int i = 0; i<size-1; i++){q2.offer(q1.poll());}return q1.poll();}else{int size = q2.size();for(int i = 0; i<size-1; i++){q1.offer(q2.poll());}return q2.poll();}}public int top() {if(empty()){return -1;}if(!q1.isEmpty()){int size = q1.size();int tmp = -1;for(int i = 0; i<size; i++){tmp = q1.poll();q2.offer(tmp);}return tmp;}else{int size = q2.size();int tmp = -1;for(int i = 0; i<size; i++){tmp = q2.poll();q1.offer(tmp);}return tmp;}}public boolean empty() {return q1.isEmpty()&&q2.isEmpty();}
}

用栈实现队列：

一个栈同样不能实现队列，模拟实现队列需要两个队列，一个栈负责入队列，一个队列负责出队列和获取队头元素。

主要思路：

入队列：将要入队列的元素压入指定的栈s1

出队列：将栈s1中所有的元素弹出栈，并压栈到栈s2，栈s2的栈顶元素就是模拟队列的队头元素

获取队头元素：peek一下栈s2的栈顶元素

在将栈s1中的元素全部压入栈s2之后，后续获取队头元素（出队列）只需要直接弹出（获取）s2的栈顶元素就行

力扣链接： 232. 用栈实现队列 - 力扣（LeetCode）