את פעולת ההסרה ניתן להגדיר על מחסנית ריקה ככזאת שמחזירה את אותה המחסנית. לחלופין, ניתן להימנע מלהגדיר אותה, או להגדיר אותה כמחזירה ערך שגיאה מיוחד. באופן דומה, (()top(init (בדיקת ראש מחסנית ריקה) ניתן להגדיר כמחזירה שגיאה, או להימנע מהגדרתה.
חשוב לשים לב לכך שכל אוסף של פונקציות וערכים המקיים את התנאים האלה נחשב למחסנית. דוגמה לא-טריוויאלית לכך היא קבוצת המספרים הטבעיים, עבור הפעולות "החזר 0" (אתחול), "הוסף 1"(push), "הפחת 1"(pop), "האם_אפס"(isEmpty). בכיוון השני ניתן לומר שכל מחסנית עשויה להוות ייצוג למספרים הטבעיים.
יישומי המחסנית.
מחסנית היא מבנה נתונים בסיסי במימוש שפות תכנות. במעבדים רבים קיים אוגר מיוחד המשמש כמצביע למחסנית, ובשפת המכונה של מעבדים אלו ממומשת הקריאה לתת-שיגרה על ידי הכנסת כתובת החזרה למחסנית. ברוב השפות העיליות נשמרים גם המשתנים המקומיים במבנה המחסנית הנתמך במעבד.
ישנו קשר הדוק בין מחסנית לעץ: מחסנית היא מבנה הנתונים הנפוץ ביותר לצורכי מעבר על עצים, על ידי אלגוריתם DFS, וכן ניתן להציג כל רצף פעולות על מחסנית בעזרת עץ מכוון. בכל רגע נתון, האיברים הנמצאים במחסנית הם המסלול משורש העץ אל הצומת שבו נמצאים. דוגמה לשימוש כזה אפשר למצוא בשפות פורמליות: לכל מילה הנגזרת בעזרת דקדוק חסר הקשר קיים עץ גזירה, ולכל דקדוק כזה קיים אוטומט מחסנית המקבל אותו.
מימוש מחסנית.
ישנן מספר דרכים לממש מחסנית:
מימושים שונים עלולים לאפשר מצבים לא תקינים:
שורש (שפות שמיות)
בדקדוק של שפות שמיות, בהן עברית, מקובל להתייחס לישות מורפולוגית המכונה שורש. שורש הוא יחידה בת 3–4 עיצורים (לעיתים נדירות: חמישה או שישה), הנתונים בסדר קבוע (בדומה ל"מחרוזת"), ומשתלבים במשקלים שונים ליצירת מילים. בבלשנות הערבית מכונה השורש: גִ'דְ'ר (جـِذر). המונח המקובל באנגלית הוא Semitic root.
מינוח.
העיצורים של השורש מכונים "רדיקלים", "עיצורי השורש" או "אותיות השורש". על-פי המסורת שהתפתחה בבלשנות הערבית בימי הביניים מקובל להשתמש בשורש פ-ע-ל כדגם לכל השורשים בני שלושה עיצורים. לפיכך מכנים את האות הראשונה בשורש פ' הפועל (פה"פ), את האות השנייה ע' הפועל (עה"פ) ואת האות השלישית ל' הפועל (לה"פ). שיטה חדשה יותר קובעת את השורש ק-ט-ל כדגם. זאת, כיוון שהוא קיים בכל השפות השמיות וכיוון שהעיצורים שבו כמעט שאינם עוברים תהליכים פונולוגיים בשפות השונות. שורשים בני ארבעה עיצורים מכונים "שורשים מרובעים". בחלק מהשפות השמיות אפשר למצוא גם שורשים מועטים בני חמישה עיצורים או יותר, רובם נגזרו ממילים שאולות, למשל: ט-ל-ג-ר-ף בעברית (מהמילה "טלגרף") או ד-מ-ק-ר-ט בערבית (دمقرط, מהמילה "דמוקרטיה").
שילוב השורש במשקל מכונה "שיבוץ" או "יציקה". בבלשנות העברית מכנים את משקלי הפועל "בניינים", כך שהמונח "משקל" מתייחס בדרך כלל למשקלי שמות העצם. בבלשנות הערבית המילה "וַזְן" (وَزن - משקל) משמשת הן לתבניות הפועל והן לתבניות של שמות עצם.
מהות מורפולוגית.
השורש הוא סוג מיוחד של מורפמה. זוהי מורפמה שאיננה יכולה לעמוד בפני עצמה, אלא חייבת להיות מורכבת עם מורפמה אחרת - הבניין או המשקל. יתר על כן, ההרכבה אינה חיבור רציף (כמו ההרכבה מדע + ָן = מדען), אלא שזירה מלאה של שתי המורפמות אחת בתוך האחרת. לפיכך, יש המכנים את השורש "מורפמה שזורה", או באנגלית: non-concatenative, על-פי הצעתו של הבלשן ג'ון מקרתי (McCarthy 1981). כמו כל מורפמה, השורש נושא משמעות לקסיקלית משל עצמו, אבל המשמעות שלו עמומה. המשמעות נעשית מדויקת רק כשהוא משובץ במשקל או בבניין. כך למשל סָקַל (בבניין קל) משמעותו השליך אבנים על אדם, ואילו סיקל (בניין פיעל) משמעותו הוציא אבנים ממקום כלשהו החוצה. מורפמה מסוג כזה כמעט שאינה מוכרת בשפות שאינן מהמשפחה האפרו-אסיאתית.
בקרב הבלשנים יש מחלוקת לגבי מהותו של השורש בשפות שמיות - האם מדובר במושג תאורטי בלבד, או שמדובר במרכיב בלתי נפרד מהידע הלשוני (הבלתי מודע) של הדוברים בשפה. מחד, יש המביאים עדויות ממשחקי מילים שלפיהן הדוברים יודעים באופן אינטואיטיבי להפריד את השורש מן המשקל. למשל "שבורית זכוכה" במקום "זכוכית שבורה" - משחק מילים שבו הדובר מחליף בין השורשים, אבל משאיר את משקלי המילים במקומם. מאידך, תהליך גזירת פעלים חדשים משמות עצם (דנומינציה) הוא תהליך שונה מהמצופה לפי תאוריית השורשים. כך למשל, מהמילה השאולה "פַקְס" נוצר הפועל "פִקְסֵס", ולא "פִקֵס" כפי שאפשר היה לצפות לפי תאוריית השורשים. מדוגמאות כאלה עולה שהיחידה המורפולוגית הבסיסית שהדובר מתייחס אליה אינה כוללת רק עיצורים בסדר מסוים, אלא גם מידע לגבי תת-יחידות של השורש (של צרורות של עיצורים וכיוצא באלה) המכונות שורשנים (ראו עוד להלן).
בחלק מן השורשים, חלק משלושת הרדיקאלים המרכיבים אותם אינם עיצורים במלוא מובן המילה, אלא פונמות "חלשות", הבאות לידי ביטוי לפעמים כתנועות. בדקדוק העברי מכנים את סוגי השורשים, לפי האופי של הרדיקאלים שלהם, בשם גזרות. למשל, הגזרה שבה האות הראשונה היא נ' נקראת "פ"נ" (כלומר: פ"א הפועל נ'), והגזרה שבה האות האחרונה היא א' נקראת "ל"א".
שורשים בני ארבעה עיצורים הם במקרים רבים גזירות משמות עצם, למשל: ארגן, פרסם. יש גם שורשים מרובעים שנוצרו מהרחבה של שורש תלת-עיצורי: ג-ל-ג-ל (מהשורש ג-ל-ל) או ע-ר-ב-ב (מהשורש ע-ר-ב).
בעת גזירת שורשים חדשים משמות עצם, יש נטייה לשמור על צרורות העיצורים שהתקיימו בשם העצם המקורי. כך למשל, בפועל "פלרטט", שנגזר מהמילה "פלירט" (מאנגלית: flirt), הצרורות "פל" ו"רט" נשמרים לאורך כל הנטייה, כאילו כל צרור מהווה עיצור אחד.
שורש תנייני.
לעיתים העיצורים של מילה שבה משובץ כבר שורש אחד הופכים לשורש חדש, ואז השורש החדש נקרא שורש תנייני. בעברית החדשה גזירה של שורשים תנייניים היא נפוצה מאוד, למשל ת-פ-ק-ד (תִפְקֵד) - שורש תנייני מן פ-ק-ד (דרך המילה תפקיד), א-ב-ט-ח (אִבְטֵחַ) - שורש תנייני מן ב-ט-ח (דרך המילה אבטחה), מ-ק-ש (לְמַקֵש) - שורש תנייני מן י-ק-ש (פח יקוש, דרך המילה מוקש).
גזירה של שורש תנייני מתרחשת בשתי דרכים עיקריות. האחת נובעת מניתוח צורני מחודש של המילה, כשהדובר מתייחס אל עיצורים השייכים במקורם למשקל כאל חלק מהשורש. בכך נוצר למעשה שורש חדש. דרך גזירה זו קיימת בלשון חז"ל. למשל, המילה "תרומה" היא מן השורש ר-ו-ם (כמו הֵרִים) במשקל תְּקוּלָה. בלשון חז"ל התייחסו אל התי"ו כאל שורשית, והעניקו למילה ניתוח חדש, כגזורה משורש ת-ר-ם במשקל קְטוּלָה. הדרך השנייה, הנפוצה יותר בעברית החדשה, היא גזירה מכוונת של שורש מבסיס על ידי השמטת תנועות הבסיס, בתהליך המכונה "סחיטה" (לדוגמה: ת-פ-ק-ד מן "תפקיד", במקור משורש פ-ק-ד), ולעיתים אף גזירה ישירה של שורש משורש אחר בתבניות קבועות כמו פ-ע-ל-ל (למשל: דברר), א-פ-ע-ל (אחזר), ת-פ-ע-ל (תשאל), ש-פ-ע-ל (שכתב), מ-פ-ע-ל (מחזר), פ-ע-ל-ן (עצבן), פ-ע-ל-ת (תכנת), פ-ל-פ-ל (בלבל).
התהליך של גזירת שורש תנייני יכול להתרחש מספר פעמים בזו אחר זו. כך למשל מהשורש התנייני ת-ח-ל (התחיל) - שהוא בעצמו נגזר בתקופת חז"ל מהשורש המקראי ח-ל-ל (הֵחֵל) - נגזר, בתקופת העברית החדשה, השורש החדש א-ת-ח-ל (אִתְחֵל).
התפתחות השורש.
אף על פי שנהוג לטעון שבשפות השמיות שורש הוא בן שלושה עיצורים, יש תפיסה שהייתה נהוגה בדקדוק הקדום ויש המצדדים בה כיום שטוענת כי השורש הבסיסי היה בן שני עיצורים בלבד, למשל: קמתי, באתי (*ק-מ, *ב-א - פועלי 'ע"ו', וכן גזרת ע"ע ועוד), ובשלב מאוחר יותר התפתחו השורשים לשלוש אותיות, בין השאר על ידי הוספת תנועה או עיצור באמצע השורש (כך נוצרו גזרות ע"ו, ע"י) או הכפלת העיצור השני של השורש (גזרת הכפולים - ע"ע). יש המרחיקים לכת עוד יותר, ומצביעים על הדמיון הסמנטי בין השורשים פ-ר-ד, פ-ר-ך, פ-ר-ס, פ-ר-ע, פ-ר-ץ, פ-ר-ק, פ-ר-ר ועוד, או בין השורשים ק-צ-ב, ק-צ-ץ, ק-צ-ר, ק-צ-ע, וטוענים שגם במקרים האלה היו במקור רק שורשים בני שני עיצורים (*פ-ר, *ק-צ) ואלה התגוונו למשמעויות דקות יותר על ידי הוספת עיצורים שלישיים שונים. הטענה הזו מתקבלת על הדעת, ואף אומצה בידי חלק מחוקרי הלשון העברית בתקופתנו, ביחס לפעלים מן הגזרות, אך החוקרים מסכימים שאי אפשר לקבל אותה ביחס לפעלים השלמים (כלומר אלה שכל העיצורים בהם רגילים, כמו הדוגמאות של פ-ר-ק וק-צ-ב).
חקר השורשים בימי הביניים.
שיטת הדקדוק בימי הביניים: מאז אמצע ימי הביניים מקובלת השיטה החד-גונית, לפיה כל שורש הוא שלָשי. לשיטה זו קדמה השיטה הרב-גונית, בה השורש מוגדר לפי אותן האותיות המתקיימות בכל ההטיות שלו. תוצאה של הגדרה זו היא שאין מספר קבוע של רדיקאלים בשורש, והוא יכול לנוע החל מאחד ועד שבעה רדיקאלים. לדוגמה: המילים הלכתי, אלך - מקורן מהשורש 'לך'. המילים מטה, נטיתי, אטה - השורש הוא בן אות אחת בלבד, 'ט'. מכה, הכיתי, אכה - השורש 'כ'. בתפיסה זו החזיק, בין השאר, מנחם בן סרוק, המדקדק בן המאה ה-10.