java基础 之 集合与栈的使用（四）

前文回顾：
戳这里 → java基础 之 集合与栈的使用（一）
戳这里 → java基础 之 集合与栈的使用（二）
戳这里 → java基础 之 集合与栈的使用（三）

代码可以直接复制粘贴~

严格来说，栈不能与队列、List、Set、Map归于一类。但是平时提到队列时总少不了提到栈，所以这次就放在一起对比总结下了。

Queue

• 特点

  • 队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作
  • 队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队
  • 队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
  • LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用

• Queue集合的一些方法

  public static void main(String[] args) {Queue<String> queue = new LinkedList<>();// offer/add:添加；如果满了之后，offer返回false，add报异常。queue.add("a");queue.offer("abc");// poll/remove：删除；如果队列为空，poll返回null，remove报异常。System.out.println(queue.remove());System.out.println(queue.poll());// peek/element：查看头部元素；如果队列为空，peek返回null，element报异常。System.out.println(queue.peek());System.out.println(queue.element());}
  

  所有已知实现类：AbstractQueue,ArrayBlockingQueue,ArrayDeque,ConcurrentLinkedQueue,DelayQueue,LinkedBlockingQueue,LinkedList,PriorityBlockingQueue,PriorityQueue,SynchronousQueue

栈Stack

• Stack的一些方法

  public static void main(String[] args) {Stack stack = new Stack();// 判断栈是否为空，返回值为boolean类型System.out.println(stack.isEmpty());// 将数据压入栈顶部stack.push(1);stack.push(2);stack.push(3);stack.push(4);// 查看栈顶部的元素，但是不从栈中移除System.out.println(stack.peek());  // 结果为2// 查看栈顶部的元素，并从栈中移除，并返回该元素System.out.println(stack.pop());   // 结果为2// 返回对象在栈中的位置，以1为技术System.out.println(stack.search(1));  // 结果为3}
  

  每次方法的调用jvm都会创建一个栈帧并压入调用栈中。大家可以思考一下递归方法与栈的联系。

队列和栈的区别

• 存储方式：队列为先进先出[FIFO]，栈为先进后出[LIFO]
• 删除操作：队列在队头删除元素，保证了元素的顺序；栈在栈顶进行删除操作
• 插入操作：队列在队尾插入元素；栈在栈顶进行插入操作
• 应用场景：队列多用于按照先后顺序处理数据的场景，如任务调度，消息队列等；栈多用于后进先出的场景，如函数调用，表达式求值等
• 数据访问方式：队列允许从队头和队尾分别访问元素，但一般只能在队头删除元素，在队尾插入元素；栈只能从栈顶访问元素

小扩展

自己写个简单的队列

public class MyQueue<K>{public K[] arr; // 定义一个泛型的数组private int maxSize;  // 定义数组的长度private int flag;  // 定义一个标签private int front;  // 队头索引private int rear;  // 队尾索引// 构造函数public MyQueue(int maxSize) {this.maxSize = maxSize;arr = (K[]) new Object[maxSize];flag = 0;  // 初始时定义为0,用来标记队空front = -1;  // 初始队头索引rear = -1;  // 初始队尾索引}// 判断队空public boolean isEmpty(){// 当队头和队尾相等时，也有可能是队满了。这时候加个标志，0说明前一个操作是出队，这样能保证当队头=队尾时，队列为空return front==rear && flag==0;}// 判断队满public boolean isFull(){// frontreturn (front+maxSize)%maxSize==rear && flag=1;}// 入队public void push(K element){// 先判断是否队满if(isFull()){System.out.println("入队失败，因为队满了");return;}rear = (rear+1)%maxSize;arr[rear]= element;flag=1;}// 出队public K pop(){// 先判断是否为空if(isEmpty()){throw new RuntimeException("出队失败，因为队空了");}front = (front+1)%maxSize;flag = 0;return arr[front];}
}

1、rear = (rear+1) % maxSize 每次进队后执行该操作，让队尾指向下一个，当队尾指向最后一个位置时重新到第一个位置

自己写个简单的栈

public class MyStack<K> {private K[] arr;  // 存储的数组private int MaxSize; // 栈的长度private int top;  // 栈顶public MyStack(int maxSize) {MaxSize = maxSize;arr = (K[]) new Object[maxSize];top = -1;}// 判断栈空public boolean isEmpty(){ return top==-1; }// 判断栈满public boolean isFull(){  return top==MaxSize-1; }// 入栈public void push(K element){// 先判断栈是不是满的if(isFull()){System.out.println("栈满了，无法插入");return;}top++;arr[top] = element;}// 出栈public K pop(){// 先判断是不是空的if(isEmpty()){// 这里不能返回数值，因为不确定是不是存入的数据。如果栈内数据不是Integer的时候，可以返回0或者-1；throw new RuntimeException("出栈失败，因为栈为空");}K temp = arr[top];top--;return temp;}
}

使用栈来实现个队列

戳这里→ leetcode 232：用栈实现队列

class MyQueue {private Stack<Integer> A;private Stack<Integer> B;public MyQueue() {A = new Stack();B = new Stack();}// 将x推到队列的末尾public void push(int x) {A.push(x);}// 从队列的开头移除并返回元素public int pop() {int peek = peek();B.pop();return peek;}// 返回队列开头的元素public int peek() {if(!B.isEmpty()){return B.peek();}if(A.isEmpty()){return -1;}while(!A.isEmpty()){B.push(A.pop());}return B.peek();}// 队列是否为空public boolean empty() {return A.isEmpty() && B.isEmpty();}
}

使用队列来实现个栈

戳这里→ leetcode 255：用队列实现栈

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<Integer>();queue2 = new LinkedList<Integer>();}// 入栈：将数据放入队列中public void push(int x) {queue2.offer(x);while(!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> temp = queue2;queue2 = queue1;queue1 = temp;}// 出栈：// 1、将queue1中除最后一个元素外，其余元素放入queue2中；// 2、queue中最后一个数据作为结果返回// 3、将queue2中的数据写回queue1public int pop() {return queue1.poll();}// 栈顶元素返回：// 1、将queue1中全部元素放入queue2中；// 2、queue1中最后一个数据作为结果返回// 3、将queue2中的数据写回queue1public int top() {return queue1.peek();}// 判断栈空：queue1（是存放数据的）是否为空public boolean empty() {return queue1.isEmpty();}
}

写在最后

• 计算机二级的公共基础部分最容易出栈和队列的选择题，想对理论知识充分了解的的话，建议看这个→ B栈视频 - 栈和队列树与二叉树软件工程基础数据库视频教程