Հերթը (Queue) ալգորիթմներում հանդիպող հիմնական տվյալ-կառուցվածքներից մեկն է։ Այն շատ նման է իրական կյանքում տեսած հերթին։ Հերթում առաջինը տեղադրված տարրը կլինի առաջինը, որը «սպասարկվում» է և հեռացվում։
Պատկերացրեք, որ մի խումբ մրջյուններ կանգնել են հերթում՝ սպասելով սուրճ ստանալուն։ Հերթի առաջին մրջյունը ստանում է սուրճն ու դուրս գալիս հերթից, ապա հաջորդ մրջյունը ստանում է իր սուրճը և նույնկերպ հեռանում հերթից։ Այս գործընթացը շարունակվում է այնքան ժամանակ, մինչև հերթը լրիվ թափուր դառնա և այլևս ոչ ոք չմնա։
Շատ ծրագրավորման լեզուներում (օրինակ՝ Python, C++, Java և այլն) հերթի հայտարարումն ու օգտագործումն արդեն իսկ ապահովված է, որպեսզի այն հեշտ լինի օգտագործել։ Այնուամենայնիվ, կարելի է այն ինքնուրույն իրականացնել կապակցված ցուցակի (Linked List) միջոցով։ Կարո՞ղ եք պատկերացնել, թե ինչպես կարելի է դա անել 🤔?
from queue import Queue
q = Queue() # Ստեղծում ենք նոր հերթ (queue)
q.put(1) # Ավելացնում ենք 1-ը հերթի առաջին դիրքում
q.put(2) # Ավելացնում ենք 2-ը (հաջորդը)
q.put(3) # Ավելացնում ենք 3-ը 2-ից հետո
# Հեռացնում ենք տարրերը հերթից get() հրամանով
print(q.get()) # տպում է 1
print(q.get()) # տպում է 2
print(q.get()) # տպում է 3
Առաջադրանք: Queue Simulation
Դուք իրականացնում եք համակարգ, որտեղ պետք է պահպանեք խանութում հերթի մեջ կանգնած հաճախորդներին։ Համակարգը պետք է կարողանա երկու գործողություն կատարել՝ հաճախորդին ավելացնել սպասման հերթին և հերթից հեռացնել առաջին հաճախորդին, երբ նա ավարտել է իր գործը։ Յուրաքանչյուր անգամ, երբ հեռացնում եք հաճախորդին, պետք է տպեք նրա անունը։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 100 000)։
Հաջորդ n տողերում ներկայացված են հրահանգները՝ կա՛մ add, կա՛մ pop․
add հրահանգին հաջորդում է հաճախորդի անունը, որը պետք է ավելացվի հերթում։
pop հրահանգի դեպքում հարկավոր է պարզապես հեռացնել հերթի առաջին հաճախորդին։
Երաշխավորված է, որ յուրաքանչյուր pop հրահանգից առաջ հերթում հաստատ կլինի գոնե մեկ հաճախորդ։
Անունները չեն գերազանցում 20 նիշը։
Ելք
Յուրաքանչյուր pop հրահանգի դեպքում ծրագիրը պետք է տպի հերթի առաջին հաճախորդի անունը։
Օրինակներ
Մուտք
Ելք
9
add Steven
add Sam
pop
add Sergio
add Don
pop
add John
pop
pop