Stack (estruktura ng datos)

Mula sa Wikipediang Tagalog, ang malayang ensiklopedya
(Idinirekta mula sa Stack (data structure))
Jump to navigation Jump to search

Sa agham pangkompyuter, ang stack(patong) ay isang estruktura ng datos kung saan ang mga elemento ay nakasaayos ng sunod sunod at sinusunod ang konsepto ng last in first out (LIFO). Ang stack ay may dalawang pangunahing operasyon: ang push(pasok) at ang pop(labas). Ang push ay ang operasyon kung saan naglalagay ng bagong elemento sa ibabaw ng stack. Ang pop naman ay ang pagtanggal ng kasalukuyang elemento na nasa ibabaw ng stack at ang pag babalik nito sa tumatawag na punsiyon. Tandaan na ang mga operasyon na ito ay sumusunod sa konsepto ng LIFO. Ang ilan pa sa mga operasyon na maaaring gawin sa stack ay ang:

  • pagbibigay ng inisyal o simulang halaga(initialize) ng stack
  • pagsubok kung may laman ang stack
  • pagsubok kung puno na ang stack

Ito ay isa sa mga pinakasimple ngunit importanteng estruktura ng data na ginagamit sa mga algoritmo. Maraming gamit ang stack tulad nalang ng pagtahak(traversing) sa mga lists at trees at iba pa.

Implementasyon[baguhin | baguhin ang batayan]

Ang stack ay madaling iiplementa sa mga high-level languages. Ito ay maaaring iimplementa sa dalawang paraan:

  • implementasyong sekwensiyal
  • implementasyong pinagdugtong(linked)

Sekwensiyal(Sequential)[baguhin | baguhin ang batayan]

Ang ganitong klase ng pag-implementa ng stack ay gumagamit ng isang dimensiyonal na array kung saan ang huling elemento sa array ang taas ng stack at dito rin nagdadagdag at nagtatanggal ng elemento gamit ang mga operasyon. Medyo limitado ang pag gamit ng ganitong implementasyon dahil nakapirme ang sukat(size) ng array at kailangan subaybayan ang laki ng array.

Ang sumusunod ang halimbawang implementasyon ng mga operasyon ng stack gamit ang array sa wikang pamprogramang C.

typedef struct {
    size_t size;
    int items[STACKSIZE];
} STACK;
void push(STACK *ps, int x)
{
    if (ps->size == STACKSIZE) {
        fputs("Error: stack overflow\n", stderr);
        abort();
    } else
        ps->items[ps->size++] = x;
}
int pop(STACK *ps)
{
    if (ps->size == 0){
        fputs("Error: stack underflow\n", stderr);
        abort();
    } else
        return ps->items[--ps->size];
}

Pinagdugtong na listahan (linked list)[baguhin | baguhin ang batayan]

Ang ganitong klase ng pag-implementa ng stack ay gumagamit ng linked list kung saan gumagamit ng tinatawag na nodo (node) upang itago ang data at ang susunod na address ng node. Ang maganda dito ay maaari kang magdagdag ng magdagdag ng data hanggang sa kaya ng memory di tulad ng sa array sapagkat address ng susunod na node ang itinatago mo sa bawat node.

Ang sumusunod ang halimbawang implementasyon ng mga operasyon ng stack gamit ang linked list sa wikang pamprogramang C.

typedef struct stack {
    int data;
    struct stack *next;
} STACK;
void push(STACK **head, int value)
{
    STACK *node = malloc(sizeof(STACK));  /* create a new node */

    if (node == NULL){
        fputs("Error: no space available for node\n", stderr);
        abort();
    } else {                                      /* initialize node */
        node->data = value;
        node->next = empty(*head) ? NULL : *head; /* insert new head if any */
        *head = node;
    }
}
int pop(STACK **head)
{
    if (empty(*head)) {                          /* stack is empty */
       fputs("Error: stack underflow\n", stderr);
       abort();
    } else {                                     /* pop a node */
        STACK *top = *head;
        int value = top->data;
        *head = top->next;
        free(top);
        return value;
    }
}