Ninja IT

Stack sử dụng mảng

Ở phần trước chúng ta sử dụng linked-list để cài đặt stack, phần này thì chúng ta sử dụng mảng.

Cài đặt ngăn xếp sử dụng mảng

Cách này hiệu quả với ngăn xếp có kích thước cố định.

Ví dụ sau tạo stack với dữ liệu kiểu char. Với sức chứa (cap - viết tắt của capacity) là 5 chúng ta có thể tạo ngay được 5 phần tử giữ chỗ trước.

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

typedef struct {
  char* data; // mảng dữ liệu kiểu char
  int length; // độ dài của dữ liệu
  int cap;    // độ dài của mảng (sức chứa của stack)
} Stack;

Stack newStack() {
  Stack s;
  s.length = 0;
  s.cap = 5;
  s.data = (char*) malloc(s.cap * sizeof(char)); // khởi tạo mảng 5 phần tử
  if (s.data == NULL) {
    printf("Memory not allocated.\n"); 
    exit(EXIT_FAILURE);
  }
  return s;
}

Hàm pushStack đẩy các phần tử vào stack

Khi độ dài các phần tử là nhỏ hơn sức chứa (cap) của stack thì cứ thêm vào bình thường. Nếu các phần tử là nhiều hơn cap thì cần nhân đôi cap của stack lên và sẽ tạo ra dữ liệu là một mảng khác. Khi đó chúng ta sẽ copy dữ liệu cũ vào mảng mới này. Lưu ý là ta có thể sử dụng hàm realloc cấp phát bộ nhớ trên ô nhớ cũ.

 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

void pushStack(Stack* s, char c) {
  // trường hợp số lượng phần tử stack vượt quá sức chứa của stack
  if (s->length >= s->cap) {
    // nhân đôi sức chứa của stack
    s->cap = s->cap * 2;
    // tạo mảng dữ liệu mới
    char* newData = (char*) realloc(s->data, s->cap * sizeof(char));
    if (newData == NULL) {
      newData = (char*) malloc(s->cap * sizeof(char));
      if (newData == NULL) {
        printf("Memory not allocated.\n"); 
        exit(EXIT_FAILURE);
      }
      // copy dữ liệu cũ sang dữ liệu mới
      for (int i = 0 ; i < s->length; i++) {
        newData[i] = s->data[i];
      }
      free(s->data);
    }
    
    // gán mảng dữ liệu mới của stack là newData
    s->data = newData;
  }

  // thêm dữ liệu mới vào stack
  s->data[s->length] = c;
  s->length++;
}

Cài đặt các hàm pop, top, isEmpty và printStack

Đoạn code sau sẽ cài đặt các hàm pop, top, isEmpty và printStack.

 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

void popStack(Stack* s) {
  if (s->length == 0) { // nếu stack rỗng thì bỏ qua
    return;
  }
  s->length--; // giảm bớt độ dài của stack
}

char topStack(Stack* s) {
  if (s->length == 0) { // nếu stack rỗng thì trả về 0
    return 0;           // có thể in ra lỗi ở trường hợp này
  }
  return s->data[s->length - 1]; // trả về dữ liệu ở top stack
}

bool isEmptyStack(Stack* s) {
  return s->length == 0; // kiểm tra độ dài của dữ liệu có bằng 0
}

// in stack từ vị trí trên cùng đến vị trí thấp nhất
void printStack(Stack* s) { 
  printf("Stack length: %d \n", s->length);
  for (int i = s->length - 1; i >= 0; i--) {
    printf("%c -> ", s->data[i]);
  }
  printf("null\n");
}