Ninja IT

Stack

Ngăn xếp

Ngăn xếp (tiếng Anh: stack) là một cấu trúc dữ liệu hoạt động theo nguyên lý vào sau ra trước (Last In First Out). Có hai hàm phổ biến là chồng lên đỉnh stack - hay được gọi là thao tác push(). Còn một hàm lấy dữ liệu ra khỏi đỉnh là pop(). Ngoài ra còn thường dùng hai hàm nữa là kiểm tra có phải stack rỗng không (isEmpty()) và hàm lấy nội dung từ đỉnh stack (hàm top()).

Ví dụ của ngăn xếp đó là một chồng sách, sách nào ở trên thì được lấy ra trước.

Cài đặt ngăn xếp sử dụng danh sách liên kết

Ví dụ sau sẽ khởi tạo stact và cài đặt hai hàm push() và pop().

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

typedef struct Node {
  int data;
  struct Node* next;
} Node;

typedef struct Stack {
  struct Node* top;
} Stack;

void push(Stack* s, int value) {
  // khởi tạo node với value
  Node* node = malloc(sizeof(Node));
  node->data = value;

  node->next = s->top; // chồng next lên trên top stack
  s->top = node; // stack top trỏ đến node mới
}

void pop(Stack* s) {
  if (s->top == NULL) { // nếu stack rỗng thì bỏ qua
    return;
  }
  Node* top = s->top; // lấy node top
  Node* next = top->next; // lấy node top cao thứ hai
  s->top = next; // trỏ stack top vào node cao thứ hai
  free(top); // xóa node top
}

int main() {
  Stack stack = {.top = NULL};
  Stack* s = &stack;

  push(s, 10); // thêm node giá trị 10 vào stack
  push(s, 12); // thêm node giá trị 12 vào stack
  pop(s); // xóa node top (node 12)
  pop(s); // xóa node top (node 10)
}

Hàm kiểm tra stack rỗng, hàm top và hàm in stack

Ví dụ sau đây kiểm tra stack rỗng, hàm top và hàm in stack. Hàm in sẽ in giá trị node trên cùng đến thấp nhất.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

int isEmpty(Stack* s) {
  return s->top == NULL; // xem node top có là null không
}

int getTopData(Stack* s) {
  if (s->top == NULL) { // nếu stack rỗng thì trả về 0
    return 0;           // hoặc có thể ném ra lỗi
  }
  return s->top->data;  // trả về dữ liệu của node top
}

void printStack(Stack* s) {
  Node* node = s->top; // lấy node top
  while(node != NULL) { // điều kiện dừng
    printf("%d -> ", node->data); // in node
    node = node->next; // đi đến node tiếp theo
  }
  printf("null");
}