క్యూ డేటా నిర్మాణం

క్యూ
క్యూ
	data structure
తరహా	డేటా నిర్మాణం
స్థాపన	డోనాల్డ్ నుత్ (నిర్వచనాన్ని అధికారికం చేసిన మొదటిది)
ప్రధానకేంద్రము	కాల్టెక్‌లో కనుగొనబడింది

కంప్యూటర్ సైన్స్లో, ఒక క్యూ అనేది ఒక సరళ నిర్మాణం, ఇది కార్యకలాపాలను నిర్వహించే ఒక నిర్దిష్ట క్రమాన్ని అనుసరిస్తుంది ఆర్డర్ "ఫస్ట్ ఇన్ ఫస్ట్ అవుట్" (FIFO).^[1] రోజువారీ జీవితంలో ఒక క్యూను వివరించడానికి ఒక మంచి ఉదాహరణ, మొదట వచ్చిన వినియోగదారుడు మొదట వడ్డించే వనరు కోసం వేచి ఉన్న వినియోగదారుల క్యూ. మూలకాలను తొలగించడంలో పైల్ క్యూల మధ్య వ్యత్యాసం ఉంది. చివరిగా జోడించిన అంశాన్ని పైల్ తొలగిస్తాము; క్యూలో, మేము మొదట జోడించిన అంశాన్ని తీసివేస్తాము. FIFO డేటా నిర్మాణంలో, క్యూలో చేర్చబడిన మొదటి మూలకం తొలగించబడిన మొదటిది. క్రొత్త మూలకాన్ని జోడించిన తర్వాత, క్రొత్త మూలకాన్ని తొలగించే ముందు తొలగించబడిన అన్ని మూలకాలను తొలగించాల్సిన అవసరానికి ఇది సమానం. తరచుగా ఒక పీక్ లేదా ఫ్రంట్ ఆపరేషన్ కూడా నమోదు చేయబడుతుంది, ఫ్రంట్ ఎలిమెంట్ విలువను డీక్యూ చేయకుండా తిరిగి ఇస్తుంది. క్యూ అనేది సరళ డేటా నిర్మాణానికి ఉదాహరణ, లేదా మరింత వియుక్తంగా ఒక వరుస సేకరణ.

అమలుసవరించు

ప్రధానంగా కింది నాలుగు ప్రాథమిక కార్యకలాపాలు క్యూలో నిర్వహించబడతాయి:^[2]

ఎన్క్యూ: క్యూలో ఒక అంశాన్ని జోడిస్తుంది. క్యూ నిండి ఉంటే, అది ఓవర్‌ఫ్లో కండిషన్ అని అంటారు.
డీక్యూ: క్యూ నుండి ఒక అంశాన్ని తొలగిస్తుంది. అంశాలు నెట్టివేయబడిన అదే క్రమంలో పాప్ చేయబడతాయి. క్యూ ఖాళీగా ఉంటే, అది అండర్ ఫ్లో కండిషన్ అని అంటారు.

ఈ రేఖాచిత్రం క్యూ ప్రాథమిక నిర్మాణాన్ని హైలైట్ చేస్తుంది.
ముందు: క్యూ నుండి ముందు అంశాన్ని పొందండి.
వెనుక: క్యూ నుండి చివరి అంశాన్ని పొందండి.

ఎన్క్యూసవరించు

ఎన్క్యూ ఆపరేషన్ క్యూలు ముందు వెనుక రెండు డేటా పాయింటర్లను నిర్వహిస్తాయి. అందువల్ల, దాని కార్యకలాపాలు పైల్ కంటే అమలు చేయడం చాలా కష్టం. డేటాను క్యూలో ఉంచడానికి (చొప్పించడానికి) క్రింది చర్యలు తీసుకోవాలి -

క్యూ నిండి ఉందో లేదో తనిఖీ చేయండి.
క్యూ నిండి ఉంటే, ఓవర్‌ఫ్లో లోపం ఉత్పత్తి చేసి నిష్క్రమించండి.
క్యూ పూర్తి కాకపోతే, తదుపరి ఖాళీ స్థలాన్ని సూచించడానికి ఇంక్రిమెంట్ వెనుక పాయింటర్.
వెనుక స్థానానికి సూచించే క్యూ స్థానానికి డేటా మూలకాన్ని జోడించండి.
తిరిగి విజయం.

ఎన్క్యూ ఆపరేషన్ కోసం అల్గోరిథం
విధానం
ఎన్క్యూ (డేటా)
క్యూ నిండి ఉంటే
రిటర్న్ ఓవర్ఫ్లో
ముగింపు
వెనుక ← వెనుక + 1
క్యూ [వెనుక]. డేటా
నిజం తిరిగి
ముగింపు విధానం

డీక్యూసవరించు

డీక్యూ ఆపరేషన్ క్యూ నుండి డేటాను యాక్సెస్ చేయడం రెండు పనుల ప్రక్రియ - ముందు సూచించే డేటాను యాక్సెస్ చేయండి యాక్సెస్ తర్వాత డేటాను తొలగించండి. డీక్యూ ఆపరేషన్ చేయడానికి క్రింది చర్యలు తీసుకుంటారు -

క్యూ ఖాళీగా ఉందో లేదో తనిఖీ చేయండి.
క్యూ ఖాళీగా ఉంటే, అండర్ఫ్లో లోపం ఉత్పత్తి చేసి నిష్క్రమించండి.
క్యూ ఖాళీగా లేకపోతే, ముందు సూచించే డేటాను యాక్సెస్ చేయండి.
తదుపరి అందుబాటులో ఉన్న డేటా మూలకాన్ని సూచించడానికి ఫ్రంట్ పాయింటర్ పెంచండి.
తిరిగి విజయం.

విధానం డీక్యూ
క్యూ ఖాళీగా ఉంటే
తిరిగి ప్రవాహం
ముగింపు
డేటా = క్యూ [ముందు]
ముందు ← ముందు + 1
నిజం తిరిగి
ముగింపు విధానం

ముందుసవరించు

ముందు ఆపరేషన్ క్యూ ముందు భాగంలో మూలకాన్ని అందిస్తుంది. ఇది తదుపరి ప్రాసెస్ చేయబడే మూలకం. దీన్ని q [ముందు] ద్వారా సులభంగా యాక్సెస్ చేయవచ్చు, ఇక్కడ 'ఫ్రంట్' అనేది మొదటి మూలకానికి సూచించే పాయింటర్ 'q' అనేది క్యూను అమలు చేయడానికి ఉపయోగించే శ్రేణి.

వెనుకసవరించు

వెనుక ఆపరేషన్ క్యూ వెనుక భాగంలో మూలకాన్ని అందిస్తుంది. చివరిగా ప్రాసెస్ చేయబడే మూలకం ఇది. Q [వెనుక] ద్వారా దీన్ని సులభంగా యాక్సెస్ చేయవచ్చు, ఇక్కడ 'వెనుక' అనేది చివరి మూలకాన్ని సూచించే పాయింటర్ 'q' అనేది క్యూను అమలు చేయడానికి ఉపయోగించే శ్రేణి.

పూర్తిగా ఫంక్షనల్ అమలుసవరించు

క్యూలను పూర్తిగా పనిచేసే డేటా నిర్మాణంగా^[3] కూడా అమలు చేయవచ్చు. మలు రెండు వెర్షన్లు ఉన్నాయి. మొదటిది, రియల్ టైమ్ క్యూ^[4] అని పిలుస్తారు, క్రింద ఇవ్వబడినది, క్యూ O (1) చెత్త-సమయ కార్యకలాపాలతో నిరంతరాయంగా ఉండటానికి అనుమతిస్తుంది, కానీ జ్ఞాపకశక్తితో సోమరితనం జాబితాలు అవసరం.

క్యూ వైవిధ్యాలుసవరించు

ప్రామాణిక క్యూ డేటా నిర్మాణం క్రింది వైవిధ్యాలను కలిగి ఉంది:^[5]

డబుల్ ఎండ్ క్యూ
వృత్తాకార క్యూ

డబుల్ ఎండ్ క్యూ

డబుల్ ఎండ్ క్యూసవరించు

ప్రామాణిక క్యూలో, ఒక అక్షరం వెనుక భాగంలో చొప్పించబడింది ముందు భాగంలో తొలగించబడుతుంది. ఏదేమైనా, డబుల్ ఎండ్ క్యూలో, క్యూ ముందు వెనుక రెండింటి నుండి అక్షరాలను చొప్పించి తొలగించవచ్చు.

వృత్తాకార క్యూలుసవరించు

వృత్తాకార క్యూ అనేది ప్రామాణిక క్యూ నిర్మాణంపై మెరుగుదల. ప్రామాణిక క్యూలో, ఒక మూలకం తొలగించబడినప్పుడు, ఖాళీ స్థలం తిరిగి ఉపయోగించబడదు. అయినప్పటికీ, వృత్తాకార క్యూలో, ఖాళీ స్థలాలు తిరిగి ఉపయోగించబడతాయి.

మూలకాలను చొప్పించేటప్పుడు, మీరు శ్రేణి చివరకి చేరుకున్నప్పుడు మీరు మరొక మూలకాన్ని చొప్పించాల్సిన అవసరం వచ్చినప్పుడు, మీరు ఆ మూలకాన్ని ప్రారంభంలో చొప్పించాలి (మొదటి మూలకం తొలగించబడింది స్థలం ఖాళీగా ఉంది).

క్యూ అనువర్తనాలుసవరించు

కంప్యూటర్ ప్రోగ్రామ్‌లలో క్యూలు సర్వసాధారణం, ఇక్కడ అవి డేటా స్ట్రక్చర్‌లతో పాటు యాక్సెస్ నిత్యకృత్యాలతో, ఒక నైరూప్య డేటా స్ట్రక్చర్‌గా లేదా ఆబ్జెక్ట్-ఓరియెంటెడ్ భాషల్లో క్లాస్‌లుగా అమలు చేయబడతాయి. సాధారణ అమలులు వృత్తాకార బఫర్‌లు లింక్డ్ జాబితాలు. కంప్యూటర్ సైన్స్, రవాణా కార్యకలాపాల పరిశోధనలలో క్యూలు సేవలను అందిస్తాయి, ఇక్కడ డేటా, వస్తువులు, వ్యక్తులు లేదా సంఘటనలు వంటి వివిధ సంస్థలు నిల్వ చేయబడతాయి తరువాత ప్రాసెస్ చేయబడతాయి. ఈ సందర్భాలలో, క్యూ బఫర్ పనితీరును నిర్వహిస్తుంది. క్యూల మరొక ఉపయోగం వెడల్పు-మొదటి శోధన అమలులో ఉంది. ప్యూటర్ సైన్స్ మరెన్నో రంగాలలో విస్తరించి ఉన్న అనేక ఇతర పనులలో కూడా క్యూ ఉపయోగించబడుతుంది. వాస్తవ ప్రపంచ అనువర్తనాలలో కొన్ని క్రింద ఇవ్వబడ్డాయి:^[6]

ప్రింటర్, CPU టాస్క్ షెడ్యూలింగ్ మొదలైన ఒకే భాగస్వామ్య వనరుపై అభ్యర్థనలను అందిస్తోంది.
నిజ జీవిత దృష్టాంతంలో, సేవా ప్రతినిధి ఉచితం అయ్యే వరకు కాల్ సెంటర్ ఫోన్ వ్యవస్థలు వారిని పిలుస్తున్న వ్యక్తులను క్రమం తప్పకుండా ఉంచడానికి క్యూలను ఉపయోగిస్తాయి.
రియల్ టైమ్ సిస్టమ్స్‌లో అంతరాయాల నిర్వహణ. అంతరాయాలు వచ్చినప్పుడు అదే క్రమంలో నిర్వహించబడతాయి, మొదట మొదట వడ్డిస్తారు.

సంక్లిష్టత విశ్లేషణసవరించు

సరళ డేటా సంక్లిష్టతను కొనసాగిస్తూ క్యూ డేటా నిర్మాణం వినియోగదారుని దాని కీ ఆపరేషన్లను (ఎన్క్యూ డీక్యూ)^[7] స్థిరమైన సమయంలో నిర్వహించడానికి అనుమతిస్తుంది. క్యూ సంక్లిష్టత విశ్లేషణను సంగ్రహించే పట్టిక క్రింద ఇవ్వబడింది.^[8]

క్యూ

పెద్ద O సంజ్ఞామానం లో సమయం సంక్లిష్టత

అల్గోరిథం	సగటు	చెత్త కేసు
స్థలం	O(n)	O(n)
వెతకండి	O(n)	O(n)
చొప్పించు	O(1)	O(1)
తొలగించు	O(1)	O(1)

మరింత చదవడానికిసవరించు

డోనాల్డ్ నుత్. ది ఆర్ట్ ఆఫ్ కంప్యూటర్ ప్రోగ్రామింగ్, వాల్యూమ్ 1: ఫండమెంటల్ అల్గోరిథమ్స్, థర్డ్ ఎడిషన్. అడిసన్-వెస్లీ, 1997. ISBN 0-201-89683-4. విభాగం 2.2.1: స్టాక్స్, క్యూలు డీక్యూస్, పేజీలు 238-243.
థామస్ హెచ్. కార్మెన్, చార్లెస్ ఇ. లీజర్సన్, రోనాల్డ్ ఎల్. రివెస్ట్, క్లిఫోర్డ్ స్టెయిన్. అల్గోరిథంల పరిచయం, రెండవ ఎడిషన్. MIT ప్రెస్ మెక్‌గ్రా-హిల్, 2001. ISBN 0-262-03293-7. విభాగం 10.1: స్టాక్స్ క్యూలు, పేజీలు 200-204.
విలియం ఫోర్డ్, విలియం టాప్. C ++ STL తో డేటా స్ట్రక్చర్స్, రెండవ ఎడిషన్. ప్రెంటిస్ హాల్, 2002. ISBN 0-13-085850-1. చాప్టర్ 8: క్యూస్ అండ్ ప్రియారిటీ క్యూస్, పేజీలు 386–390.
ఆడమ్ డ్రోజ్‌డెక్. సి ++, మూడవ ఎడిషన్‌లో డేటా స్ట్రక్చర్స్ అల్గోరిథంలు. థామ్సన్ కోర్సు టెక్నాలజీ, 2005. ISBN 0-534-49182-0. చాప్టర్ 4: స్టాక్స్ అండ్ క్యూస్, పేజీలు 137-169.

మూలాలుసవరించు

↑ "Queue (Java Platform SE 7 )". docs.oracle.com. Retrieved 2020-08-24.
↑ Chik, Adam. Stack & Queue. Pittsburgh: CMU.
↑ Okasaki, Chris (1996). Purely Functional Data Structures. Pittsburgh: CMU. pp. 1–162.
↑ Hood, Robert T.; Melville, Robert C. (1980). "Real Time Queue Operations in Pure LISP". Cornell (in అమెరికన్ ఇంగ్లీష్).
↑ "Basics of Queues Tutorials & Notes | Data Structures". HackerEarth (in ఇంగ్లీష్). Retrieved 2020-08-24.
↑ "Queue Data Structure | Studytonight". www.studytonight.com. Retrieved 2020-08-24.
↑ "Queue Data Structure | Studytonight". www.studytonight.com. Retrieved 2020-08-24.
↑ "Queue Complexity". Wikipedia.{{cite web}}: CS1 maint: url-status (link)

[1] "Queue (Java Platform SE 7 )". docs.oracle.com. Retrieved 2020-08-24.

[2] Chik, Adam. Stack & Queue. Pittsburgh: CMU.

[3] Okasaki, Chris (1996). Purely Functional Data Structures. Pittsburgh: CMU. pp. 1–162.

[4] Hood, Robert T.; Melville, Robert C. (1980). "Real Time Queue Operations in Pure LISP". Cornell (in అమెరికన్ ఇంగ్లీష్).

[5] "Basics of Queues Tutorials & Notes | Data Structures". HackerEarth (in ఇంగ్లీష్). Retrieved 2020-08-24.

[6] "Queue Data Structure | Studytonight". www.studytonight.com. Retrieved 2020-08-24.

[7] "Queue Data Structure | Studytonight". www.studytonight.com. Retrieved 2020-08-24.

[8] "Queue Complexity". Wikipedia.{{cite web}}: CS1 maint: url-status (link)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]