iT邦幫忙

2021 iThome 鐵人賽

DAY 4
1
自我挑戰組

【帶你輕鬆入門演算法-Leetcode】系列 第 4

【第四天 - 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], [], [], []] 這種字串輸入
    • I/O
  • 題目的條件

    • 放入的資料只會是數字 1~9
    • 最多執行100次 function
    • 只會在 Queue 裡面有資料的情況,執行 pop 跟 peek
    • 題目限制
  • 看完題目,需要思考的條件:

    • 如何用兩個 stack 的盒子,模擬出 Queue 的行為?
    • 如果不使用兩個 stack 來做,該如何實作 Queue ?
  • 明天會分析該題 python 不同解法的優點,希望大家今天可以多先自己想一下這題,如果是你,你的思考邏輯是什麼?


上一篇
【第三天 - Stack 題目分析】
下一篇
【第五天 - Queue 題目分析】
系列文
【帶你輕鬆入門演算法-Leetcode】30

尚未有邦友留言

立即登入留言