Stack (agham pangkompyuter)

Sa agham pangkompyuter, ang stack (patong) ay isang abstract data type na ginagamit sa maraming problema tulad ng paggawa ng listahan, pag-aayos ng pagkakasunod-sunod ng trabaho na gagawin ng isang kompyuter, at iba pa. Ang ideya sa stack ay ito ay "last-in, first-out" o ang huling ipinasok sa kanya ang siyang unang lalabas. Ang memory ng isang kompyuter ay gumagamit ng stack (tinatawag na internal stack), kung saan nilalagay nito ang mga instructions na kailangan nitong gawin, upang malaman ang tamang pagkakasunod-sunod nito.

May dalawang mahalagang operasyon sa paggamit ng stack, ang tinatawag na “push” at “pop”. Ang “push” ang naglalagay ng elemento sa ibabaw ng stack, habang ang “pop” naman ang nag-aalis ng elemento mula sa ibabaw ng stack. Hindi maaring gamiting ang “pop” kapag walang laman ang stack, at hindi rin maaring gamitin ang “push” kapag puno na ang stack. Ngunit ang isang stack ay maaring isipin na hindi napupuno; napupuno lamang ito kapag ito ay ginawa sa isang kompyuter na may limitadong memorya.

Sa paggawa ng stack, importante na alam ng programmer ang “top” o ang ibabaw ng stack. Hindi kinakailangan malaman ang laman nito, ang kailangan lamang ay ang lokasyon nito. Sa paggamit ng “push”, gagalaw ang top ng isang hakbang pataas, at tska ilalagay ang elemento. Sa paggamit ng push, gagalaw pababa ang top. Importante na hindi magagamit ang pop kapag walang laman ang isang stack, dahil ibig sabihin nito ay may problema sa program na ginagamit.

Ang stack ang isa sa mga importante at simpleng paraan ng pag-aayos ng data. Ito ay isa sa mga pinakasimple ngunit importanteng estruktura ng data na ginagamit sa mga algoritmo. Isang halimbawa ng aplikasyon nito ay ang mga baraha sa larong Solitaire. Maraming gamit ang stack tulad nalang ng pagtahak(traversing) sa mga lists at trees at iba pa.

Ang stack 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

Implementasyon

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

• implementasyong sekwensiyal
• implementasyong pinagdugtong(linked)

Sekwensiyal(Sequential)

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)

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;
    }
}