【第四天 - Queue 介绍】

Q1. Queue是什麽?

• 与 Stack 一样，是一种资料结构的概念，假设有一个容器是装马克杯的盒子 (从这个盒子下方拿东西，有点类似饮水机旁边会放的下落式纸杯架)
  • 
• 与 Stack 举例一样，我们依序将小明、小美、小雅的马克杯，从上方放入盒子中
• 课间小 Q&A： 你现在要从盒子中取出一个马克杯，请问你会拿到谁的马克杯 ? (注意，Stack 的盒子只有一个开口，只能从上方拿，Queue 只能从下方拿)
• ANS：盒子内的杯子排序预期是如下图，所以你从盒子下方取，会拿到最下面的杯子，也就是小明的杯子
• 
• 
• 也就是说，这种 Queue概念，最先放的杯子，会最先拿起来，最晚放的杯子，最後才能拿到，也就是「先进先出」「後进後出」的概念 ( 英文称为 First-In-First-Out )，这种概念就很像我们平常在排队的概念，先到的人会先排到

Q2. 学会 Queue 概念可以做什麽?

• 需要依序执行的时候
  • 抢课系统 (先抢先赢)
  • 点餐系统 (先排队点餐的人先做餐点)

Lab. 明天要解的题目：232 Implement Queue using Stacks

题目连结：https://leetcode.com/problems/implement-queue-using-stacks/

题目叙述：

• 使用两个 stack 完成 Queue 的概念

• 要有以下几个功能

  • push：把资料放入 Queue
  • peek：看排队最前面的是谁 (不会把东西拿出来)
  • pop：把排队最前面的拿出来
  • empty：检查 stack 是不是空的

• 

• 

• 测资的 Input/Output

  • 实作完的 class，可以被 new 出来使用即可，不会真的有 ["MyQueue", "push", "push", "peek", "pop", "empty"] 跟 [[], [1], [2], [], [], []] 这种字串输入
  • 

• 题目的条件

  • 放入的资料只会是数字 1~9
  • 最多执行100次 function
  • 只会在 Queue 里面有资料的情况，执行 pop 跟 peek
  • 

• 看完题目，需要思考的条件：

  • 如何用两个 stack 的盒子，模拟出 Queue 的行为?
  • 如果不使用两个 stack 来做，该如何实作 Queue ?

• 明天会分析该题 python 不同解法的优点，希望大家今天可以多先自己想一下这题，如果是你，你的思考逻辑是什麽?