Đảo ngược danh sách liên kết bằng stack trong C++

Danh sách liên kết cấp phát bộ nhớ động, được dùng để triển khai stack. Chương trình này trình bày việc đảo ngược danh sách liên kết trong lập trình C++. Người học có thể áp dụng phương pháp sau để đạt kết quả mong đợi. Thuật toán như sau:

Thuật toán

BẮT ĐẦU
Bước 1: Tạo stack rỗng kiểu con trỏ node
Bước 2: Duyệt danh sách và đẩy tất cả node lên stack
Bước 3: Duyệt danh sách từ node head lần nữa
Bước 4: Lấy giá trị từ đỉnh stack
Bước 5: Nối chúng theo thứ tự ngược lại
Bước 6: IN
DỪNG

Dựa trên thuật toán trên, mã C++ sau được viết nơi thư viện stdlib đóng vai trò quan trọng cung cấp các phương thức liên quan đến stack như sau:

Ví dụ

#include <iostream>
#include <stdlib.h>
using namespace std;
struct linked_list {
    int data;
    struct linked_list *next;
};
int stack[30], top = -1;
struct linked_list* head = NULL;
int printfromstack(int stack[]) {
    cout << "\nStack sau khi đảo ngược::";
    while (top >= 0) {
        cout << stack[top--] << " ";
    }
}
int push(struct linked_list** head, int n) {
    struct linked_list* newnode = (struct linked_list*)malloc(sizeof(struct linked_list));
    newnode->data = n;
    newnode->next = (*head);
    (*head) = newnode;
}
int intostack(struct linked_list* head) {
    cout << "Danh sách liên kết::";
    while (head != NULL) {
        printf("%d ", head->data);
        stack[++top] = head->data;
        head = head->next;
    }
}
int main(int argc, char const *argv[]) {
    push(&head, 7);
    push(&head, 20);
    push(&head, 3);
    push(&head, 40);
    intostack(head);
    printfromstack(stack);
    return 0;
}

Như thấy trong mã trên, toàn bộ mã thao tác chuỗi được gói gọn trong phương thức retrieveChar(), sau đó được gọi trong hàm main() để thực thi.

Kết quả

Danh sách liên kết:: 40 3 20 7
Stack sau khi đảo ngược:: 7 20 3 40