ಸ್ಟ್ಯಾಕ್ (ಅಬ್ಸ್ ಟ್ರ್ಯಾಕ್ಟ್ ಡೇಟಾ ಟೈಪ್)

 

ಅದೇ ರೀತಿ ತಟ್ಟೆಗಳ ರಾಶಿಯಲ್ಲಿ, ಸೇರಿಸುವುದು ಅಥವಾ ತೆಗೆದುಹಾಕುವುದು ಮೇಲ್ಭಾಗದಲ್ಲಿ ಮಾತ್ರ ಸಾಧ್ಯ.

ಪುಶ್ ಮತ್ತು ಪಾಪ್ ಕಾರ್ಯಾಚರಣೆಗಳೊಂದಿಗೆ ಸ್ಟ್ಯಾಕ್ ರನ್ ಟೈಮ್ ನ ಸರಳ ಪ್ರಾತಿನಿಧ್ಯ.

ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನ ದಲ್ಲಿ, ಸ್ಟ್ಯಾಕ್ ಎನ್ನುವುದು ಅಬ್ಸ್ ಟ್ರ್ಯಾಕ್ಟ್ ಡೇಟಾ ಪ್ರಕಾರವಾಗಿದ್ದು, ಇದು ಎರಡು ಮುಖ್ಯ ಕಾರ್ಯಾಚರಣೆಗಳೊಂದಿಗೆ ಎಲಿಮೆಂಟ್ (ಅಂಶ)ಗಳ ಸಂಗ್ರಹವಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆಃ

• ಪುಶ್, ಇದು ಈಗಾಗಲೇ ಇರುವ ಸಂಗ್ರಹಕ್ಕೆ ಒಂದು ಎಲಿಮೆಂಟ್ ಅನ್ನು ಸೇರಿಸುತ್ತದೆ, ಮತ್ತು
• ಪಾಪ್, ಇದು ಇತ್ತೀಚೆಗೆ ಸೇರಿಸಲಾದ ಎಲಿಮೆಂಟ್ ಅನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ.

ಹೆಚ್ಚುವರಿಯಾಗಿ, ಪೀಕ್ ಕಾರ್ಯಾಚರಣೆಯು, ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಮಾರ್ಪಡಿಸದೆ, ಇತ್ತೀಚೆಗೆ ಸೇರಿಸಿದ ಅಥವಾ ಕೊನೆಯ ಎಲಿಮೆಂಟ್ ನ ಮೌಲ್ಯವನ್ನು ಹಿಂದಿರುಗಿಸಬಹುದು. ಸ್ಟ್ಯಾಕ್ ಎಂಬುದು ಫಲಕಗಳ ಅಥವಾ ತಟ್ಟೆಗಳ ಸ್ಟ್ಯಾಕ್ನಂತಹ ಒಂದಕ್ಕೊಂದು ಜೋಡಿಸಲಾದ ಭೌತಿಕ ವಸ್ತುಗಳ ಗುಂಪಿಗೆ ಹೋಲಿಕೆ.

ಒಂದು ಸ್ಟ್ಯಾಕ್ ಗೆ ಒಂದು ಎಲಿಮೆಂಟ್ ಅನ್ನು ಸೇರಿಸಿದ ಅಥವಾ ತೆಗೆದುಹಾಕಿದ ಕ್ರಮವನ್ನು ಲಾಸ್ಟ್ ಇನ್, ಫಸ್ಟ್ ಔಟ್ ಎಂದು ವಿವರಿಸಲಾಗುತ್ತದೆ, ಇದನ್ನು ಸಂಕ್ಷಿಪ್ತ ರೂಪವಾದ LIFO ನಿಂದ ಉಲ್ಲೇಖಿಸಲಾಗುತ್ತದೆ. ಅಥವಾ ಇದನ್ನೇ ಫಸ್ಟ್ ಇನ್ ಲಾಸ್ಟ್ ಔಟ್ ಅಂತಾ ಸಹ ಕರೆಯಬಹುದು. ಇದನ್ನು ಸಂಕ್ಷಿಪ್ತ ರೂಪವಾದ FILO ನಿಂದ ಉಲ್ಲೇಖಿಸಲಾಗುತ್ತದೆ ‌‌‍ [ಎನ್ಬಿ 1] ಭೌತಿಕ ವಸ್ತುಗಳ ರಾಶಿಯಂತೆ, ಈ ರಚನೆಯು ರಾಶಿಯ ಮೇಲ್ಭಾಗದಿಂದ ವಸ್ತುವನ್ನು ತೆಗೆದುಕೊಳ್ಳಲು ಸುಲಭವಾಗಿಸುತ್ತದೆ, ಆದರೆ ಸ್ಟ್ಯಾಕ್ ನಲ್ಲಿ ಆಳವಾದ ಡೇಟಾ ಅಥವಾ ದತ್ತಾಂಶ ಪ್ರವೇಶಿಸಲು ಮೊದಲು ಅನೇಕ ಇತರ ವಸ್ತುಗಳನ್ನು ತೆಗೆದುಹಾಕಬೇಕಾಗುತ್ತದೆ.

ಲೀನಿಯರ್ ಡೇಟಾ ರಚನೆ ಅಥವಾ ಹೆಚ್ಚು ಅಮೂರ್ತವಾಗಿ ಅನುಕ್ರಮ ಸಂಗ್ರಹವೆಂದು ಪರಿಗಣಿಸಲಾಗಿರುವ, ಒಂದು ಸ್ಟ್ಯಾಕ್ ಒಂದು ತುದಿಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಇದು ಪುಶ್ ಮತ್ತು ಪಾಪ್ ಕಾರ್ಯಾಚರಣೆಗಳು ಸಂಭವಿಸಬಹುದಾದ ಏಕೈಕ ಜಾಗವಾಗಿದೆ, ಸ್ಟ್ಯಾಕ್ ನ ಮೇಲ್ಭಾಗ, ಮತ್ತು ಇನ್ನೊಂದು ತುದಿಯಲ್ಲಿ ಈ ಕಾರ್ಯಗಳನ್ನು ನಡೆಸಬಹುದು ಮತ್ತು ಯಾವಾಗಲೂ, ಕೆಳಭಾಗ ಸ್ಥಿರವಾಗಿರುತ್ತದೆ. ಈ ದತ್ತಾಂಶ ರಚನೆಯು ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಏಕವಾಗಿ ಲಿಂಕ್ ಮಾಡಲಾದ ಪಟ್ಟಿಯಾಗಿ ಮತ್ತು ಮೇಲಿನ ಎಲಿಮೆಂಟ್ ಗೆ ಪಾಯಿಂಟರ್ ಆಗಿ ಕಾರ್ಯಗತಗೊಳಿಸಲು ಸಾಧ್ಯವಾಗಿಸುತ್ತದೆ. ಒಂದು ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಸೀಮಿತ ಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದಲು ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು. ಸ್ಟ್ಯಾಕ್ ತುಂಬಿದಲ್ಲಿ ಮತ್ತು ಮತ್ತೊಂದು ಎಲಿಮೆಂಟ್ ಅನ್ನು ಸ್ವೀಕರಿಸಲು ಸಾಕಷ್ಟು ಸ್ಥಳಾವಕಾಶವಿಲ್ಲದಿದ್ದರೆ, ಸ್ಟ್ಯಾಕ್ ಓವರ್ಫ್ಲೋ ಸ್ಥಿತಿಯಲ್ಲಿರುತ್ತದೆ.

ಡೆಪ್ತ್-ಫಸ್ಟ್ ಹುಡುಕಾಟ ಕಾರ್ಯಗತಗೊಳಿಸಲು ಸ್ಟ್ಯಾಕ್ ನ ಅಗತ್ಯವಿದೆ.

ಇತಿಹಾಸ

ಅಲನ್ ಟ್ಯೂರಿಂಗ್ ಅವರು 1946ರಲ್ಲಿ "ಬರಿ" ಮತ್ತು "ಅನ್ಬರಿ" ಎಂಬ ಪದಗಳನ್ನು ಸಬ್ ರೂಟೀನ್ ಗಳಿಂದ ಕರೆ ಮಾಡುವ ಮತ್ತು ಹಿಂದಿರುಗುವ ಸಾಧನವಾಗಿ ಬಳಸಿ ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನ ಸಾಹಿತ್ಯಕ್ಕೆ ಪರಿಚಯಿಸಿದರು. ಸಬ್ ರೂಟೀನ್ ಗಳು ಮತ್ತು ಎರಡು-ಹಂತದ ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಈಗಾಗಲೇ 1945 ರಲ್ಲಿ ಕೊನ್ರಾಡ್ ಜ್ಯೂಸ್ನ Z4 ನಲ್ಲಿ ಜಾರಿಗೆ ತರಲಾಗಿತ್ತು.

ಮ್ಯೂನಿಚ್ ತಾಂತ್ರಿಕ ವಿಶ್ವವಿದ್ಯಾಲಯದ ಕ್ಲಾಸ್ ಸ್ಯಾಮಲ್ಸನ್ ಮತ್ತು ಫ್ರೆಡ್ರಿಕ್ ಎಲ್. ಬಾಯರ್ ಅವರು 1955 ರಲ್ಲಿ ಆಪರೇಷನ್ಸ್ ಸ್ಕೆಲ್ಲರ್ ಎಂಬ ಸ್ಟ್ಯಾಕ್ ಕಲ್ಪನೆಯನ್ನು ಪ್ರಸ್ತಾಪಿಸಿದ ನಂತರ 1957 ರಲ್ಲಿ ಪೇಟೆಂಟ್ ಸಲ್ಲಿಸಿದರು. ಮಾರ್ಚ್ 1988 ರಲ್ಲಿ, ಸ್ಯಾಮಲ್ಸನ್ ನಿಧನರಾದರು, ಬಾಯರ್ ಸ್ಟಾಕ್ ತತ್ವದ ಆವಿಷ್ಕಾರಕ್ಕಾಗಿ ಐಇಇಇ ಕಂಪ್ಯೂಟರ್ ಪಯೋನಿಯರ್ ಪ್ರಶಸ್ತಿ ಪಡೆದರು.[2] ಇದೇ ರೀತಿಯ ಪರಿಕಲ್ಪನೆಗಳನ್ನು ಸ್ವತಂತ್ರವಾಗಿ ಚಾರ್ಲ್ಸ್ ಲಿಯೊನಾರ್ಡ್ ಹ್ಯಾಂಬ್ಲಿನ್ 1954 ರ ಮೊದಲಾರ್ಧದಲ್ಲಿ ಮತ್ತು ವಿಲ್ಹೆಲ್ಮ್ ಕಾಮ್ಮೆರರ್ [ಡಿ] 1958 ರಲ್ಲಿ ತನ್ನ ಸ್ವಯಂಚಾಲಿತ ಗೆಡಾಚ್ಟ್ನಿಸ್ (′ಆಟೋಮ್ಯಾಟಿಕ್ ಮೆಮೊರಿ) ಯೊಂದಿಗೆ ಅಭಿವೃದ್ಧಿಪಡಿಸಿದರು.[de]

ಹಲವುವೇಳೆ, ಒಂದು ಕೆಫೆಟೇರಿಯಾದಲ್ಲಿನ ಅಥವಾ ಕ್ಯಾಂಟೀನ್ ನಲ್ಲಿ ಒಟ್ಟಿಗೆ ಜೋಡಿಸಿರುವ ಪ್ಲೇಟ್ ಅಥವಾ ತಟ್ಟೆಗಳನ್ನು ಸ್ಟ್ಯಾಕ್ ಉದಾಹರಣೆಯನ್ನು ಸಾದೃಶ್ಯವಾಗಿ ವಿವರಿಸಲಾಗುತ್ತದೆ. ಸ್ವಚ್ಛವಾದ ತಟ್ಟೆಗಳನ್ನು ಸ್ಟ್ಯಾಕ್ ನ ಮೇಲೆ ಇರಿಸಲಾಗುತ್ತದೆ, ಅಲ್ಲಿ ಈಗಾಗಲೇ ಇರುವ ಯಾವುದೇ ತಟ್ಟೆಗಳನ್ನು ಕೆಳಕ್ಕೆ ತಳ್ಳಲಾಗುತ್ತದೆ. ಸ್ಟ್ಯಾಕ್ ನಿಂದ ಮೇಲಿನ ತಟ್ಟೆಯನ್ನು ತೆಗೆದುಹಾಕಿದಾಗ, ಅದರ ಕೆಳಗಿರುವ ತಟ್ಟೆಯು ಹೊಸ ಮೇಲಿನ ತಟ್ಟೆಯಾಗುವಂತೆ ಮೇಲಕ್ಕೆ ಬರುತ್ತದೆ.

ಅಗತ್ಯವಲ್ಲದ ಕಾರ್ಯಾಚರಣೆಗಳು

ಅನೇಕ ಅನುಷ್ಠಾನಗಳಲ್ಲಿ, ಒಂದು ಸ್ಟ್ಯಾಕ್ ಅಗತ್ಯವಾದ "ಪುಶ್" ಮತ್ತು "ಪಾಪ್" ಕಾರ್ಯಾಚರಣೆಗಳಿಗಿಂತ ಹೆಚ್ಚಿನ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಅನಿವಾರ್ಯವಲ್ಲದ ಕಾರ್ಯಾಚರಣೆಯ ಒಂದು ಉದಾಹರಣೆಯೆಂದರೆ "ಟಾಪ್ ಆಫ್ ದಿ ಸ್ಟಾಕ್" ಅಥವಾ "ಪೀಕ್". ಇದು ಸ್ಟ್ಯಾಕ್ ನಿಂದ ತೆಗೆದುಹಾಕದೆ ಮೇಲಿನ ಎಲಿಮೆಂಟ್ ಅನ್ನು ಗಮನಿಸುತ್ತದೆ. ಇದನ್ನು "ಪಾಪ್" ಆಗಿ ವಿಭಜಿಸಬಹುದು ಮತ್ತು ನಂತರ ಅದೇ ಡೇಟಾವನ್ನು ಸ್ಟ್ಯಾಕ್ ಗೆ ಹಿಂದಿರುಗಿಸಲು "ಪುಶ್" ಮಾಡಬಹುದು. ಇದನ್ನು ಅಗತ್ಯ ಕಾರ್ಯಾಚರಣೆ ಎಂದು ಪರಿಗಣಿಸಲಾಗುವುದಿಲ್ಲ. ಸ್ಟ್ಯಾಕ್ ಖಾಲಿಯಾಗಿದ್ದರೆ, "ಸ್ಟ್ಯಾಕ್ ಟಾಪ್" ಅಥವಾ "ಪಾಪ್" ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಿದ ನಂತರ ಅಂಡರ್ ಫ್ಲೋ ಸ್ಥಿತಿ ಉಂಟಾಗುತ್ತದೆ. ಹೆಚ್ಚುವರಿಯಾಗಿ, ಅನೇಕ ಅನುಷ್ಠಾನಗಳು ಸ್ಟ್ಯಾಕ್ ಖಾಲಿಯಾಗಿದೆಯೇ ಮತ್ತು ಅದರ ಗಾತ್ರವನ್ನು ಹಿಂದಿರುಗಿಸುವ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಒದಗಿಸುತ್ತವೆ.

ತಂತ್ರಾಂಶದ ಸ್ಟ್ಯಾಕ್ ಗಳು

ಅನುಷ್ಠಾನ

ಒಂದು ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಒಂದು ಅರ್ರೇ ಅಥವಾ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ ಮೂಲಕ ಸುಲಭವಾಗಿ ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದು, ಏಕೆಂದರೆ ಇದು ಕೇವಲ ಲಿಸ್ಟ್ ನ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ. ಎರಡೂ ಸಂದರ್ಭಗಳಲ್ಲಿ, ಡೇಟಾ ರಚನೆಯನ್ನು ಸ್ಟ್ಯಾಕ್ ಎಂದು ಗುರುತಿಸುವುದು ಅನುಷ್ಠಾನವಲ್ಲ ಆದರೆ ಇಂಟರ್ಫೇಸ್ ಗಳು ಬಳಕೆದಾರರಿಗೆ ಕೆಲವು ಇತರ ಸಹಾಯಕ ಕಾರ್ಯಾಚರಣೆಗಳೊಂದಿಗೆ, ಅರ್ರೇ (ಡೇಟಾ ಸ್ಟ್ರಕ್ಚರ್) ಅಥವಾ ಲಿಂಕ್ಡ್ ಲಿಸ್ಟ್ ಗೆ ವಸ್ತುಗಳನ್ನು ಪಾಪ್ ಮಾಡಲು ಅಥವಾ ಪುಶ್ ಮಾಡಲು ಮಾತ್ರ ಅನುಮತಿಸಲಾಗಿದೆ. ಕೆಳಗಿನವುಗಳು ಸೂಡೊಕೋಡ್ ಬಳಸಿ ಎರಡೂ ಅನುಷ್ಠಾನಗಳನ್ನು ಪ್ರದರ್ಶಿಸುತ್ತವೆ.

ಅರ್ರೇ.

ಈ ಕೆಳಗಿನಂತೆ ಒಂದು ಶ್ರೇಣಿಯನ್ನುಅರ್ರೇಯನ್ನು (ಬೌಂಡೆಡ್ ಸ್ಟ್ಯಾಕ್) ಕಾರ್ಯಗತಗೊಳಿಸಲು ಬಳಸಬಹುದು. ಮೊದಲ ಎಲಿಮೆಂಟ್, ಸಾಮಾನ್ಯವಾಗಿ ಸೊನ್ನೆ ಆಫ್ಸೆಟ್, ಕೆಳಭಾಗದಲ್ಲಿರುತ್ತದೆ. ಇದರ ಪರಿಣಾಮವಾಗಿ ರಚನೆಯು ಮೊದಲ ಎಲಿಮೆಂಟ್ ಅನ್ನು ಸ್ಟ್ಯಾಕ್ ಗೆ ತಳ್ಳುತ್ತದೆ (array[0]) ಮತ್ತು ಕೊನೆಯ ಎಲಿಮೆಂಟ್ ಹೊರಬರುತ್ತದೆ. ಪ್ರೋಗ್ರಾಂ ಸ್ಟ್ಯಾಕ್ ಗಾತ್ರವನ್ನು ಟ್ರ್ಯಾಕ್ ಮಾಡಬೇಕು (ಸ್ಟ್ಯಾಕ್ ಉದ್ದ, ಇಲ್ಲಿಯವರೆಗೆ ತಳ್ಳಿದ ಐಟಂಗಳ ಸಂಖ್ಯೆಯನ್ನು ದಾಖಲಿಸುವ ವೇರಿಯೇಬಲ್ ಟಾಪ್ ಬಳಸಿ, ಆದ್ದರಿಂದ ಮುಂದಿನ ಎಲಿಮೆಂಟ್ ಅನ್ನು ಸೇರಿಸಬೇಕಾದ ರಚನೆಯಲ್ಲಿನ ಸ್ಥಳವನ್ನು ಸೂಚಿಸುತ್ತದೆ (ಸೊನ್ನೆ ಆಧಾರಿತ ಸೂಚ್ಯಂಕ ಸಂಪ್ರದಾಯವನ್ನು ಊಹಿಸಿ). ಹೀಗಾಗಿ, ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಮೂರು-ಎಲಿಮೆಂಟ್ ಗಳ ರಚನೆಯಾಗಿ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಕಾರ್ಯಗತಗೊಳಿಸಬಹುದುಃ

Structure stack: 

      maxsize:integer 

      top:integer 

      items: array of item

procedure initialize(stk : stack, size : integer):
    stk.items ← new array of size items, initially empty
    stk.maxsize ← size
    stk.top ← 0

ಪುಶ್ ಕಾರ್ಯಾಚರಣೆಯು ಒಂದು ಎಲಿಮೆಂಟ್ ಅನ್ನು ಸೇರಿಸುತ್ತದೆ ಮತ್ತು ಓವರ್ಫ್ಲೋ ಅನ್ನು ಪರಿಶೀಲಿಸಿದ ನಂತರ ಮೇಲಿನ ಸೂಚ್ಯಂಕವನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ:

procedure push(stk : stack, x : item):
    if stk.top = stk.maxsize:
        report overflow error
    else:
        stk.items[stk.top] ← x
        stk.top ← stk.top + 1

ಅಂತೆಯೇ, ಪಾಪ್ ಅಂಡರ್ ಫ್ಲೋ ಅನ್ನು ಪರಿಶೀಲಿಸಿದ ನಂತರ ಮೇಲಿನ ಸೂಚ್ಯಂಕವನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತದೆ ಮತ್ತು ಹಿಂದೆ ಅಗ್ರಸ್ಥಾನದಲ್ಲಿದ್ದ ವಸ್ತುವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆಃ

procedure pop(stk : stack):
    if stk.top = 0:
        report underflow error
    else:
        stk.top ← stk.top − 1
        r ← stk.items[stk.top]
        return r

ಡೈನಾಮಿಕ್ ಅರ್ರೇ ಯನ್ನು ಬಳಸಿಕೊಂಡು, ಅಗತ್ಯವಿರುವಷ್ಟು ಬೆಳೆಯುವ ಅಥವಾ ಕುಗ್ಗುವಂತಹ ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಲು ಸಾಧ್ಯವಿದೆ. ಸ್ಟ್ಯಾಕ್ ನ ಗಾತ್ರವು ಕೇವಲ ಕ್ರಿಡೈನಾಮಿಕ್ ಅರ್ರೇ ಯ ಗಾತ್ರವಾಗಿದೆ, ಇದು ಸ್ಟ್ಯಾಕ್ ನ ಅತ್ಯಂತ ಪರಿಣಾಮಕಾರಿ ಅನುಷ್ಠಾನವಾಗಿದೆ. ಏಕೆಂದರೆ ಡೈನಾಮಿಕ್ ಅರ್ರೇಗೆ ವಸ್ತುಗಳನ್ನು ಸೇರಿಸುವುದರ ಅಥವಾ ತೆಗೆದುಹಾಕುವುದರ ಸಮಯ O(1) ಆಗಿರುತ್ತದೆ.