Հերթ (Queue)

Հերթը (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 հրահանգի դեպքում ծրագիրը պետք է տպի հերթի առաջին հաճախորդի անունը։

Օրինակներ