Việc cài đặt stack bằng mảng có vẻ như rất dễ dàng cài đặt và khá hiệu quả với chi phí O(1). Tuy nhiên, đối với mảng lại có một số hạn chế nhất định về kích thước cố định hay việc tận dụng lãng phí bộ nhớ. Vì vậy để khắc phục những hạn chế trên, ta hoàn toàn có thể sử dụng danh sách liên kết để cài đặt stack thay cho mảng. Các thao tác cơ bản khi cài đặt stack bằng danh sách liên kết bao gồm:

• Khởi tạo stack: Init (S)
• Tạo mới 1 nút: CreateNode (x)
• Kiểm tra stack rỗng: IsEmpty (S)
• Đưa phần tử vào Stack: Push (S,x)
• Lấy phần tử ra khỏi Stack: Pop (S, x)

1.Khai báo các node và cấu trúc stack với danh sách liên kết

Vì chúng ta đang cài đặt stack bằng danh sách liên kết, vì vậy ta cần khai báo một stack và một Node (hay phần tử của stack đó).

Đầu tiên, ta sẽ khai báo một Node để chứa các thành phần dữ liệu và con trỏ đến node khác trong stack và với giả sử rằng dữ liệu được lưu trữ trong Node của chúng ta có kiểu int data;

struct node{
    int data;
    node *next;
};
typedef struct node NODE;

Tiếp theo, ta sẽ khai báo stack ban đầu gồm một Node là NODE *top; (phần tử trên đỉnh của stack)

struct stack{
    NODE *top;
};
typedef struct stack STACK;

Hai việc khai báo trên có vẻ rất giống cho việc khai báo danh sách liên kết đơn. Tuy nhiên, thay vì khai báo struct list với hai thành phần NODE *pHead và NODE *pTail cho việc cà đặt danh sách liên kết đơn thì ta lại khai báo struct stack với một thành phần NODE *top; cho cấu trúc stack.

2.Các hàm khởi tạo và kiểm tra stack bằng danh sách liên kết

2.1 Hàm khởi tạo stack

Hàm khởi tạo có chức năng gán phần tử top ban đầu của stack về NULL và khiến cho stack đó trở nên rỗng.

Hàm void Init(STACK &s) dưới đây nhận STACK &s là stack cần khởi tạo. Sau đó gán phần tử top của stack đó về NULL.

void Init (STACK &s){
    //gan top cua stack ve NULL
    s.top = NULL;
}

2.2 Hàm tạo mới một node

Khi cài đặt stack bằng danh sách liên kết, chắc chắn rằng các phần tử của stack đó sẽ là một node. Và một node thì lại có 2 thành phần đó là thành phần data và thành phần địa chỉ đến node khác. Vì vậy ta cần hàm khởi tạo node để khai báo đủ 2 thành phần trên trước khi đưa node đó vào stack.

Hàm NODE* CreateNode(int x) dưới đây nhận int x là dữ liệu cần thêm vào Node khi được khởi tạo.

NODE* CreateNode (int x) {
    NODE *p;
    p = new NODE;
    //neu p = NULL thi ko du bo nho cap phat
    if (p==NULL) {
        printf ("KHONG DU BO NHO!");
        return NULL;
    }
    //gan data bang X
    p->data=x;
    //gan con tro next bang NULL
    p->next=NULL;
    //tra ve node p
    return p;
}

Vì dữ liệu trong bài được giả sử là số nguyên nên tham số truyền vào sẽ là int x, trong một số trường hợp ta có thể thay đổi bằng float x, char x…hay một kiểu dữ liệu SinhVien x mà ta tự định nghĩa!

2.3 Hàm kiểm tra rỗng trong stack

Khi sử dụng các thao tác lấy phần tử trong stack ra thì việc trước tiên ta cần kiểm tra xem stack đó có rỗng hay không? Nếu rỗng thì không thể lấy các phần tử ngược lại thì được phép lấy các phần tử. Vì vậy ta cần một hàm kiểm tra xem stack có rỗng hay không?

Hàm int IsEmpty(STACK s) sẽ thực hiện kiểm tra phần tử top của stack, nếu stack cần kiểm tra không có phần tử top hay phần tử top bằng NULL thì stack đó rỗng và trả về true, ngược lại thì stack đó không rỗng và trả về false.

int IsEmpty(STACK s){
    if (s.top == NULL){
        return 1;
    }
    return 0;
}

3.Thao tác push và pop với stack bằng danh sách liên kết

3.1 Thao tác push trong stack

Thao tác push trong stack là thao tác đưa phần tử hay Node vào trong stack khi cài đặt bằng danh sách liên kết. Trường hợp nếu stack trống thì node đó sẽ được thêm vào phần tử top của stack. Nếu stack không trống thì sẽ thêm node đó lên đầu đỉnh stack.

Hàm void Push(STACK &s, int x) nhận tham số STACK &s là stack cần thêm phần tử vào và int x là dữ liệu cần thêm vào.

void Push (STACK &s, int x){
    //tao mot node moi va truyen vao du lieu x
    NODE *NewNode = CreateNode(x);
    //neu node moi khoi tao thanh cong
    if (NewNode != NULL){
        //neu stack ban dau dang rong 
        if (IsEmpty(s)){
            // s.top = NewNode
            s.top = NewNode;
        } 
        else{ //nguoc lai them NewNode vao dinh cua stack
            NewNode->next = s.top;
            s.top = NewNode;
        }
    }
}

3.2 Thao tác pop trong stack

Thao tác pop với stack khi cài đặt bằng danh sách liên kết chính là việc lấy các node tử trong top của stack đó ra và đồng thời thực hiện xóa node đó khỏi stack.

Hàm int Pop(STACK &s) nhận tham số STACK &s là stack cần lấy dự liệu ra sau đó thực hiện xóa đi node vừa lấy và đồng thời cũng trả về dữ liệu của node đó.

int Pop (STACK &s){
    //tao node p 
    NODE *p;
    //tao bien x de gan bang du lieu cua node
    int x;
    //neu stack khong rong
    if (!IsEmpty(s)){
        //gan node p bang phan tu top cua stack
        p = s.top;
        //thay doi lai top cua stack
        s.top = p->next;
        //gan du lieu cua node p vao x
        x = p->data;
        //xoa di node p vua lay
        delete p;
        //tra ve x
        return x;
    }
}

Vì stack trên lưu trữ kiểu dữ liệu là int nên hàm trả về có kiểu là int Pop(), trong một số trường hợp kiểu dữ liệu ta lưu trữ trong node là gì thì ta sẽ trả về kiểu dữ liệu đó cho hàm Pop.

4.Nhập xuất node vào stack

Việc nhập xuất node vào stack đều sử dụng lại hai hàm đó là push và pop ở trên. Ta có thể xây dựng một hàm cho việc nhập N phần tử (hay node) vào stack như sau:

void Input(STACK &s, int n){
    //duyen tu 0 den N
    for(int i = 0; i < n; i++){
        //tao bien x va nhan gia tri tu ban phim
        int x;
        printf("NHAP SO THU %d: ",i);
        scanf("%d", &x);
        printf("\n");
        //truyen stack va x vua nhap vao ham Push de dua vao stack
        Push(s,x);
    }
}

Tiếp theo, ta có thể xây dựng một hàm cho việc xuất N phần tử trong stack ra như sau:

void Output(STACK s)
{
    //tao node p
    NODE *p;
    //duyet tu phan tu tren dinh top den phan tu cuoi stack
    for(p = s.top; p != NULL; p=p->next){
        //hien thi du lieu 
        printf("%d",p->data);
    }
}

5.Chương trình cài đặt stack bằng danh sách liên kết hoàn chỉnh

Trước tiên, khi cài đặt stack bằng danh sách liên kết hay đảm bảo rằng ta đã nhập vào 2 thư viện đó là:

#include<stdio.h>
#include<stdlib.h>

Chương trình dưới đây là chương trình sử dụng tất cả các hàm ở trên để cài đặt stack bằng danh sách liên kết, vì vậy nếu bạn còn chưa rõ về hàm nào ở trên thì vui lòng đọc kỹ lại trước khi đến phần này!

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    node *next;
};
typedef struct node NODE;
struct stack
{
    NODE *top;
};
typedef struct stack STACK;
void Init (STACK &s){
    //gan top cua stack ve NULL
    s.top = NULL;
}
NODE* CreateNode (int x) {
    NODE *p;
    p = new NODE;
    //neu p = NULL thi ko du bo nho cap phat
    if (p==NULL) {
        printf ("KHONG DU BO NHO!");
        return NULL;
    }
    //gan data bang X
    p->data=x;
    //gan con tro next bang NULL
    p->next=NULL;
    //tra ve node p
    return p;
}
int IsEmpty(STACK s){
    if (s.top == NULL){
        return 1;
    }
    return 0; 
}
void Push (STACK &s, int x){
    //tao mot node moi va truyen vao du lieu x
    NODE *NewNode = CreateNode(x);
    //neu node moi khoi tao thanh cong
    if (NewNode != NULL){
        //neu stack ban dau dang rong 
        if (IsEmpty(s)){
            // s.top = NewNode
            s.top = NewNode;
        } 
        else{ //nguoc lai them NewNode vao dinh cua stack
            NewNode->next = s.top;
            s.top = NewNode;
        }
    }
}
int Pop (STACK &s){
    //tao node p 
    NODE *p;
    //tao bien x de gan bang du lieu cua node
    int x;
    //neu stack khong rong
    if (!IsEmpty(s)){
        //gan node p bang phan tu top cua stack
        p = s.top;
        //thay doi lai top cua stack
        s.top = p->next;
        //gan du lieu cua node p vao x
        x = p->data;
        //xoa di node p vua lay
        delete p;
        //tra ve x
        return x;
    }
}
void Input(STACK &s, int n){
    //duyen tu 0 den N
    for(int i = 0; i < n; i++){
        //tao bien x va nhan gia tri tu ban phim
        int x;
        printf("NHAP SO THU %d: ",i);
        scanf("%d", &x);
        //truyen stack va x vua nhap vao ham Push de dua vao stack
        Push(s,x);
    }
}
void Output(STACK s)
{
    //tao node p
    NODE *p;
    //duyet tu phan tu tren dinh top den phan tu cuoi stack
    for(p = s.top; p != NULL; p=p->next){
        //hien thi du lieu 
        printf("%d \n",p->data);
    }
}

int main(){
    STACK s;
    //khoi tao stack
    Init(s);
    //nhap so n
    int n; 
    printf("NHAP N: ");
    scanf("%d",&n);
    //nhap n phan tu vao stack
    Input(s,n);
    //hien thi cac phan tu vua nhap vao stack
    printf("DANH SACH CAC PHAN TU VUA NHAP VAO STACK\n");
    Output(s);
    //push phan tu vao stack
    int x = 66;
    Push(s,x);
    //hien thi lai stack sau khi push
    printf("STACK SAU KHI PUSH PHAN TU %d\n",x);
    Output(s);
    //thuc hien lay phan tu top trong stack ra va xoa di
    int p = Pop(s);
    printf("PHAN TU VUA DUOC LAY RA VA XOA DI LA %d",p);
    //stack sau khi pop
    printf("\nSTACK SAU KHI POP LA\n");
    Output(s);
}

Khi thực hiện các thao tác push phần tử x = 66 và pop trong stack ta nhận thấy rằng stack sẽ chỉ làm việc với phần tử top của nó. Vì vậy stack mà khi nhắc đến stack người ta nghĩ đến cơ chế làm việc LIFO (Last In First Out) hay dịch sang tiếng việt là vào cuối thì lại được xử lý đầu tiên.