【算法训练-队列 一】【结构特性】用两个栈实现队列

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【队列的结构特性】，使用【队列】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

名曲目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

用两个栈实现队列【EASY】

还是一道结构特性的题，用两个栈来实现队列

题干

结合队列和栈的结构特性来解题

解题思路

元素进栈以后，只能优先弹出末尾元素，但是队列每次弹出的却是最先进去的元素，如果能够将栈中元素全部取出来，才能访问到最前面的元素，此时，可以用另一个栈来辅助取出。

step 1：push操作就正常push到第一个栈栈顶。
step 2：pop操作时，如果第二个栈为空则优先将第一个栈的元素弹出，并依次进入第二个栈中，如果不为空则直接弹出第二个栈栈顶元素

第一个栈中栈底元素也就是最后进入第二个栈的栈顶元素就是队列首部元素。

代码实现

给出代码实现基本档案

基本数据结构：队列
辅助数据结构：栈
算法：无
技巧：无

其中数据结构、算法和技巧分别来自：

• 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
• 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法
• 技巧：双指针、滑动窗口、中心扩散

当然包括但不限于以上

import java.util.*;
import java.util.Stack;

public class Solution {
    // 1 定义两个栈, 分别是队列的两头，stackPush为队列尾部，入队使用，stackPop为队列头部，出队使用
    Stack<Integer> stackPush = new Stack<Integer>();
    Stack<Integer> stackPop = new Stack<Integer>();
    
    public void push(int node) {
    // 2 直接入队
       stackPush.push(node);
        
    }
    
    public int pop() {
    // 3 出队前做判断，如果出队栈已经空了，则把入队栈的元素倒着压入出堆栈，如果不为空，则正常从出队栈出
       if(stackPop.isEmpty()){
         while(!stackPush.isEmpty()){
            stackPop.push(stackPush.pop());
         }
       }
       return stackPop.pop();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

复杂度分析

时间复杂度：时间复杂度是O（N），pop操作可能会触发遍历第一个栈。push操作就是O（1）
空间复杂度：空间复杂度为O（N），按题意本来提供的两个栈，并没有使用辅助数据结构，这里感觉O（1）和O（N）都可以说

拓展知识：队列的基本操作

在Java中，队列（Queue）是一种常用的数据结构，它遵循先进先出（FIFO）的原则。Java提供了多种方式来操作队列，其中最常用的是使用java.util.Queue接口，它是一个基本的队列接口，有许多不同的实现类可供选择，如LinkedList、ArrayDeque和PriorityQueue等。以下是一些常见的队列操作：

1. 创建队列：

   Queue<Type> queue = new LinkedList<>(); // 使用LinkedList实现队列
   // 或
   Queue<Type> queue = new ArrayDeque<>(); // 使用ArrayDeque实现队列
   // 或
   Queue<Type> queue = new PriorityQueue<>(); // 使用PriorityQueue实现队列
   1
   2
   3
   4
   5

2. 入队列（添加元素到队列尾部）：

   queue.add(element); // 或 queue.offer(element);
   1

3. 出队列（移除队列头部的元素并返回）：

   Type element = queue.poll(); // 如果队列为空，返回null
   // 或
   Type element = queue.remove(); // 如果队列为空，抛出异常
   1
   2
   3

4. 获取队列头部元素但不移除：

   Type element = queue.peek(); // 如果队列为空，返回null
   // 或
   Type element = queue.element(); // 如果队列为空，抛出异常
   1
   2
   3

5. 检查队列是否为空：

   boolean isEmpty = queue.isEmpty();
   1

6. 获取队列的大小：

   int size = queue.size();
   1

7. 遍历队列：

   可以使用迭代器或增强for循环来遍历队列。

   for (Type element : queue) {
       // 处理元素
   }
   1
   2
   3

这些是队列的基本操作。不同的队列实现可能具有不同的性能特性和用途，你可以根据你的具体需求选择合适的队列实现。请注意，在多线程环境下使用队列时，需要考虑线程安全性，可以考虑使用java.util.concurrent包中的并发队列实现，如LinkedBlockingQueue或ConcurrentLinkedQueue。