In ngược danh sách liên kết dùng Stack

Cho một danh sách liên kết, chương trình phải in danh sách từ cuối về đầu sử dụng cấu trúc dữ liệu Stack.

Input : 10 → 5 → 3 → 1 → 7 → 9
Output: 9 → 7 → 1 → 3 → 5 → 10

Ở đây người dùng có thể dùng cách tiếp cận lấy phần tử từ stack trỏ top tại vị trí stack[0] rồi đi đến stack[n].

Thuật toán

START
Step 1 -> tạo cấu trúc Linked_list
  Khai báo int data
  Khai báo struct linked_list *next
End
Step 2 -> khai báo int stack[30], top = -1
Step 3 -> khai báo struct linked_list* head = NULL
Step 4 -> tạo function int printfromstack(int stack[])
  Vòng lặp While top>=0
    Print stack[--top]
  End
Step 5 -> tạo function int push(struct linked_list** head, int n)
  khai báo struct linked_list* newnode = (struct linked_list*)malloc(sizeof(struct linked_list))
  set newnode->data = n
  set newnode->next = (*head)
  set (*head) = newnode
Step 6 -> tạo function int intostack(struct linked_list* head)
  Vòng lặp While head!=NULL
    Print head->data
    Set stack[++top] = head->data
    Set head = head->next
  End
End
Step 7 -> goto main()
  Call push(&head, 10)
  Call push(&head, 20)
  Call push(&head, 30)
  Call push(&head, 40)
  Call intostack(head)
  Call printfromstack(stack)
STOP

Ví dụ

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

struct linked_list {
  int data;
  struct linked_list *next;
};

int stack[30], top = -1;
struct linked_list* head = NULL;

int printfromstack(int stack[]) {
  printf("\nStack:\n");
  while(top>=0) {
    printf("%d ", 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) {
  printf("Linked list:\n");
  while(head!=NULL) {
    printf("%d ", head->data);
    stack[++top] = head->data;
    head = head->next;
  }
}

int main(int argc, char const *argv[]) {
  push(&head, 10);
  push(&head, 20);
  push(&head, 30);
  push(&head, 40);
  intostack(head);
  printfromstack(stack);
  return 0;
}

Kết quả

Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra đầu ra sau

Linked list: 40 30 20 10
Stack: 10 20 30 40