Հերթ (Queue)

Հերթը (Queue) ալգորիթմներում հանդիպող հիմնական տվյալ-կառուցվածքներից մեկն է։ Այն շատ նման է իրական կյանքում տեսած հերթին։ Հերթում առաջինը տեղադրված տարրը կլինի առաջինը, որը «սպասարկվում» է և հեռացվում։
Պատկերացրեք, որ մի խումբ մրջյուններ կանգնել են հերթում՝ սպասելով սուրճ ստանալուն։ Հերթի առաջին մրջյունը ստանում է սուրճն ու դուրս գալիս հերթից, ապա հաջորդ մրջյունը ստանում է իր սուրճը և նույնկերպ հեռանում հերթից։ Այս գործընթացը շարունակվում է այնքան ժամանակ, մինչև հերթը լրիվ թափուր դառնա և այլևս ոչ ոք չմնա։
notion image
Շատ ծրագրավորման լեզուներում (օրինակ՝ 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
Steven Sam Sergio Don
4 add John Ford add Tom Ford pop pop
John Ford Tom Ford
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue