Understanding Stack - An Essential Abstract Data Type.hy.md

Ստեկ տվյալների կառուցվածքը: JavaScript ծրագրավորման լեզվի օգնությամբ պարզագույն ստեկի ստեղծումը:

Ստեկը (անգ․ Stack, հայերեն մասնագիտական գրականության մեջ երբեմն թարգմանվում է որպես պարունակ) տվյալների կառուցվածք է, որն իրենից ներկայացնում է էլեմենտների կարգավորված ցուցակ, որտեղ նոր էլեմենտ ավելացնելը և արդեն եղածները հեռացնելը կատարվում է միայն մի կողմից, որը և անվանում են ստեկի գագաթ։ Ընդ որում ստեկից առաջինը միշտ հեռացվում է այն էլեմենտը, որն ավելացվել է ամենավերջում։ Այսպիսով ստեկում էլեմենտների հեռացումը կատարվում է «վերջին եկածը դուրս է գալիս առաջինը» սկզբունքով։ (Այդ սկզբունքն ընդունված է անվանել LIFO՝ անգլերեն Last In First Out արտահայտության հապավումն է)։

Ստեկ հասկացությունն առաջին անգամ օգտագործել է անգլիացի մաթեմատիկոս, տրամաբան և համակարգչային գիտության զարգացման մեջ խոշոր ներդրում ունեցած գիտնական Ալան Թյուրինգը՝ դեռևս հեռավոր 1946 թվականին։ Հետագայում՝ 1955 ֊ 1957 թվ․Մյունխենի տեխնոլոգիական համալսարանի դոկտորներ Քլաուս Սամելսընի և Ֆրիդրիխ Բաուերի կողմից կատարվեց ստեկի և նրա հիմնական մեթոդների ալգորիթմերի նկարագրությունը, ապա նաև պատենտավորումը։

Ստեկի ամենատարածված կենցաղային օրինակ կարող են լինել իրար վրա դրված գրքերը կամ ափսեները, երբ անհրաժեշտ ափսեյին հասնելու համար պետք է հանել դրանից վերև դրված բոլոր ափսեները։ Համակարգչային գիտության մեջ ստեկի կիրառությունն ամենուր է։ Գրաֆների և նրանց մասնավոր դեպք հանդիսացող ծառերի հետ կապված բազմաթիվ խնդիրներ հեշտությամբ լուծվում են ստեկի օգնությամբ։ Ռեկուրսիվ ֆունկցիաների աշխատանքը նույնպես կատարվում է ստեկի օգնությամբ։

Ստեկի հիմնական մեթոդներն են նրա մեջ էլեմենտ ավելացնելը՝ push և հեռացնելը՝ pop։ Շատ հաճախ այն ունենում է նաև մեթոդ, որը ստուգում է արդյոք ստեկը դատարկ է թե ոչ՝ isEmpty։ Կախված նրանից, թե ինչ բնույթի խնդիրներ լուծելու համար է նախատեսված ստեկը՝ այն կարող է ունենալ մի շարք այլ մեթոդներ, օրինակ՝ peek մեթոդը՝ ստեկի գագաթին գտնվող էլեմենտը տեսնելու համար, կամ size մեթոդը՝ ստեկում գտնվող էլեմենտների քանակն իմանալու համար։

JavaScript ծրագրավորման լեզվով ստեկի ստեղծման համար մենք կօգտվենք class-ների սինթաքսիսից։ Այն հնարավոր է անել բազմաթիվ տարբեր եղանակներով, օրինակ կարելի է որպես ստեկի հիմք վերցնել զանգված կամ կապակցված ցուցակ (պետք է նախ ստեղծել կապակցված ցուցակը, որովհետև JavaScript-ի ստանդարտ գրադարանների մեջ դրա իմպլեմենտացիան չկա), կարելի է առանձին պահել ստեկի գագաթին հղվող մարկեր, կամ հեշտությամբ գրել առանց դրա, իսկ մեթոդների առկայությունն էլ ինչպես վերևում նշվեց, կարող է կախված լինել թե ինչի մեջ ենք ուզում ստեկն օգտագործել, կարևորը, որ իրականացվի երկու հիմնական մեթոդները՝ push և pop:

Նախ ստեղծենք Stack դասը։

class Stack {
  constructor() {
    this.data = [];
  }
}

Ինչպես գիտենք, ստեկի համար որպես հիմք կարելի է օգտագործել զանգված։ Դրա համար մենք ստեղծում ենք data անունով դատարկ զանգվածը, որը հետագայում ստեկի էլեմենտների համար ծառայելու է որպես կոնտեյներ։ Այժմ դիտարկենք ստեկի մեջ էլեմենտ ավելացնելու հնարավորություն ստեղծող մեթոդը՝ push-ը։

class Stack {
  constructor() {
    this.data = [];
  }

  push(item) {
    return this.data.push(item);
  }
}

Մեթոդը որպես արգումենտ ստանում է այն էլեմենտը, որը ցանկանում ենք ավելացնել ստեկի մեջ, ապա այն ավելացնում է մեր ստեկի համար որպես հիմք ծառայող data անունով զանգվածի վերջից։ Ապա վերադարձնում է զանգվածի երկարությունը (Քանի֊որ զանգվածների push մեթոդը նույնպես վերադարձնում է զանգվածի երկարությունը)։

Ստեկից էլեմենտ հեռացնող pop մեթոդը նույնպես պարզ է։

class Stack {
  constructor() {
    this.data = [];
  }

  push(item) {
    return this.data.push(item);
  }

  pop() {
    return this.data.pop();
  }
}

Այն հեռացնում է ստեկի համար որպես հիմք ծառայող զանգվածի վերջին էլեմենտը և վերադարձնում այն։

Ստեկի երկու հիմնական մեթոդներից բացի, ավելացնենք ևս մի շատ օգտագործվող մեթոդ, որը ստուգում է արդյո՞ք ստեկը դատարկ է, և վերադարձնում համապատասխան բուլյան արժեք՝ true կամ false:

class Stack {
  constructor() {
    this.data = [];
  }

  push(item) {
    return this.data.push(item);
  }

  pop() {
    return this.data.pop();
  }

  isEmpty() {
    return this.data.length === 0;
  }
}

Մեթոդն ուղղակի ստուգում է թե ստեկի համար որպես կոնտեյներ ծառայող զանգվածի երկարությունն արդյոք հավասար է 0֊ի թե ոչ, և բնականաբար եթե զանգվածի երկարությունը 0 է, ապա ստեկը դատարկ է և մեթոդը վերադարձնում է true: Հակառակ դեպքում, եթե զանգվածի երկարությունը մեծ է 0֊ից, ապա ստեկը դատարկ չէ, և մեթոդը վերադարձնում է false:

Սա ստեկի ստեղծման պարզ եղանակ է, այն կարելի է կատարելագործել, ավելացնել տարբեր ստուգումներ, օրինակ, որ հնարավոր չլինի ստեկում ավելացնել null կամ undefined տիպի արժեքներ, կամ որ ստեկի դատարկ լինելու դեպքում pop ֆունկցիան կանչելիս throw օպերատորի օգնությամբ գեներացվի սխալի օբյեկտ, կամ էլ նոր մեթոդներ ստեղծել (օրինակ peek, size, clear և այլն):

Ստեկի ստեղծման համար մենք կարող ենք օգտագործել նաև ֆունկցիոնալ ոճը։ Ահա մի օրինակ՝ բոլոր հիմնական մեթոդների առկայությամբ՝

function createStack() {
  let items = [];

  return {
    push(item) {
      items.push(item);
    },

    pop() {
      if (items.length === 0) {
        throw new Error("Stack is empty");
      }
      return items.pop();
    },

    peek() {
      if (items.length === 0) {
        throw new Error("Stack is empty");
      }
      return items[items.length - 1];
    },

    isEmpty() {
      return items.length === 0;
    },

    size() {
      return items.length;
    },

    clear() {
      items = [];
    },
  };
}