Ngăn xếp Stack là gì ?

Tên đầy đủ Abstract Data Type – viết tắt là ADT là một ngăn xếp là một cấu trúc dữ liệu trừu tượng, hầu hết mọi ngôn ngữ lập trình hầu như sử dụng chúng. Nó hoạt động như một ngăn xếp trong đời sống thực, chính vì vậy được đặt tên là ngăn xếp, chẳng hạn như xếp quần áo, chồng đĩa, hoặc bộ bài.

Ngăn xếp stack bộ bài

Ngăn xếp chỉ cho phép các hoạt động tại vị trí trên cùng của ngăn xếp trong đời sống thực tế. Chẳng hạn như: trên cùng của ngăn xếp chúng ta chỉ có thể đặt hoặc thêm một cái đĩa, một bộ bài vào. Cho nên, ngăn xếp chỉ cho phép các thao tác dữ liệu tại vị trí trên cùng theo cấu trúc dữ liệu trừu tượng. Chúng ta chỉ có thể truy cập phần tử trên cùng của ngăn xếp ở bất kỳ thời điểm nào.

Cấu trúc dữ liệu LIFO là viết tắt của Last-In-First-Out từ các đặc điểm nêu trên. Trên thực tế, phần tử được đặt vào (được thêm vào, được chèn) cuối cùng sẽ được truy cập đầu tiên trong chuỗi. Hoạt động chèn được gọi là hoạt động PUSH và hoạt động xóa được gọi là hoạt động PUSH trong thuật ngữ ngăn xếp.

Trình bày cấu trúc dữ liệu ngăn xếp Stack

Theo dõi hình minh họa bên dưới

Stack Representation

Ngăn xếp có thể là ngăn xếp có thể thay đổi kích cỡ hay ở dạng kích cỡ cố định. Hầu hết một ngăn xếp có thể được triển khai theo phương thức của Mảng (Array), Danh sách liên kết (Linked List), Cấu trúc (Struct), Con trỏ (Pointer).

Tìm hiểu hoạt động cơ bản trên cấu trúc dữ liệu ngăn xếp

Những hoạt động cơ bản trên stack có thể liên quan tới việc khởi tạo ngăn xếp, sử dụng nó và cuối cùng xóa nó. Một ngăn xếp có hai hoạt động nguyên sơ liên quan tới khái niệm, bên cạnh những hoạt động cơ bản này:

  • Hoạt động pop(): xóa một phần tử từ ngăn xếp.
  • Hoạt động push(): lưu trữ một phần tử trên ngăn xếp.

Tiếp theo đó, sau khi dữ liệu đã được PUSH lên trên ngăn xếp. Chúng ta cũng cần kiểm tra trạng thái của ngăn xếp, để sử dụng ngăn xếp một cách hiệu quả. Tìm hiểu một số tính năng của ngăn xếp

  • Hoạt động isEmpty(): kiểm tra xem ngăn xếp là trống hay không.
  • Hoạt động peek(): lấy phần tử dữ liệu ở trên cùng của ngăn xếp, mà không xóa phần tử này.
  • Hoạt động isFull(): kiểm tra xem ngăn xếp đã full hay chưa.

Chúng ta duy trì một con trỏ tới phần tử dữ liệu vừa được PUSH cuối cùng vào trên ngăn xếp, tại mọi thời điểm. Con trở top luôn biểu diễn vị trí trên cùng của ngăn xếp chính vì vậy mới có cái tên như vậy. Không cần phải thực hiện hoạt động xóa ở trên (hoạt động pop), con trỏ top cung cấp cho chúng ta giá trị của phần tử trên cùng của ngăn xếp mà.

Tìm hiểu phương thức peek() của ngăn xếp stack

Chi tiết giải thuật của hàm peek():

Khởi động hàm peek

   return stack[d];
   
Kết thúc hàm peek

Tìm hiểu triển khai của hàm peek() trong ngôn ngữ lập trình C:

char peek() {
   return stack[d];
}

Tìm hiểu phương thức isFull() của cấu trúc dữ liệu ngăn xếp

Chi tiết giải thuật của hàm isFull():

Bt đầu hàm isfull

   nếu d bằng MAXSIZE
      trả về true;
   ngược lại
      trả lại false;
   kết thúc if
   
kết thúc hàm isfull

Chi tiết triển khai của hàm isFull() trong ngôn ngữ lập trình C:

bool IsFull() {
   if(d == MAXSIZE)
      return true;
   else
      return false;
}

Tìm hiểu phương thức isEmpty() của stack

Chi tiết giải thuật của hàm isEmpty():

Khởi động hàm IsEmpty

   nếu d < 1
      trả về true;
   ngược lại
      trả về false;
   kết thúc if
   
kết thúc hàm IsEmpty

Sự triển khai trong ngôn ngữ C của hàm isEmpty() khác hơn một chút. Tiến hành khởi tạo top tại -1, giống như chỉ mục của mảng bắt đầu từ 0. Cho nên, tiến hành kiểm tra nếu top là -1 hoặc <0 thì ngăn xếp là trống. Chi tiết bên dưới

bool IsEmpty() {
   if(d == -1)
      return true;
   else
      return false;
}

Chi tiết hoạt động PUSH trong cấu trúc ngăn xếp Stack

Stack Push Operation

Hoạt động PUSH chính là tiến trình đặt (thêm) một phần tử dữ liệu mới vào trên ngăn xếp. Chi tiết các hoạt động push:

  • Bước 1: Thực hiện việc kiểm tra xem ngăn xếp đã đầy hay chưa?
  • Bước 2: Trong trường hợp nếu ngăn xếp là đầy, tiến trình bị lỗi và thoát ra.
  • Bước 3: Ngược lại, nếu ngăn xếp chưa đầy, tăng top để trỏ tới phần bộ nhớ trống tiếp theo.
  • Bước 4: Tiến hành thêm phần tử dữ liệu vào vị trí nơi mà top đang trỏ đến trên ngăn xếp.
  • Bước 5: return về success.

Chi tiết giải thuật cho hoạt động PUSH của cấu trúc dữ liệu ngăn xếp

Chi tiết giải thuật

Khởi động hot động push: data, stack

   nếu stack là đầy
      trả về null
   kết thúc if
   
   d  d + 1
   
   stack[d]  data

kết thúc hàm

Tham khảo cách triển khai của giải thuật này trong ngôn ngữ C là:

void push(char data) {
   if(!IsFull()) {
      d = d + 1;   
      stack[d] = data;
   }else {
      printf("Stack is Full.\n");
   }
}

Khám phá hoạt động POP của cấu trúc dữ liệu ngăn xếp

Đối với hoạt động POP thì việc truy cập nội dung phần tử trong khi xóa nó từ ngăn xếp Stack. Phần tử dữ liệu không thực sự bị xóa, thay vào đó top sẽ bị giảm về vị trí thấp hơn trong ngăn xếp để trỏ tới giá trị tiếp theo, trong sự triển khai Mảng của hoạt động pop().Hoạt động pop() thực sụ xóa phần tử dữ liệu và xóa nó khỏi không gian bộ nhớ trong sự triển khai List liên kết.

Điểm qua các bước của hoạt động POP

  • Bước 1: Tiến hành kiểm tra xem ngăn xếp là trống hay không?
  • Bước 2: Trường hợp nếu ngăn xếp là trống, tiến trình bị lỗi và thoát ra.
  • Bước 3: Ngược lại nếu ngăn xếp là không trống, truy cập phần tử dữ liệu tại top đang trỏ tới.
  • Bước 4: Xử lý giảm giá trị của top đi 1.
  • Bước 5: return về success.

Chi tiết giải thuật cho hoạt động POP

Tìm hiểu giải thuật chi tiết cho hoạt động POP

bt đầu hàm pop: [stack]

   nếu stack là trng
      return null
   kết thúc if
   
   data  stack[t]
   
   d  d - 1
   
   trả về data

kết thúc hàm

Khám phá triển khai giải thuật trong ngôn ngữ lập trình C:

int Pop(char data) {

   if(!IsEmpty()) {
      data = stack[d];
      d = d - 1;   
      return data;
   }else {
      printf("Stack is null\n");
   }
}

Tìm hiểu ứng dụng của ngăn xếp

  • Xử lý gọi hàm trong C/C++
  • Trong các chương trình biên dịch
  • Sử dụng để tính giá trị biểu thức, xử lý ngắt trong máy tính
  • Trình soạn thảo văn bản trong trình duyệt web
  • Định giá biểu thức: ( Biểu thức tiền tố : toán tử đứng trước toán hạng – Biểu thức trung tố: toán tử hai ngôi đứng giưã hai toán hạng, toán tử một ngôi đứng trước toán hạng – Biểu thức hậu tố : toán tử đứng sau toán hạng )

Với bài viết ngày hôm nay, Zephyrfalcon hy vọng sẽ giúp bạn có một cái nhìn thực tế về cấu trúc dữ liệu ngăn xếp Stack, chúc bạn thành công với cấu trúc dữ liệu. Để là bước đệm vững chắc cho con đường IT sau này.

Xem thêm: Cấu trúc dữ liệu là gì?