STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ
    Nội dung
    0
    0
    Chia sẻ

    Stack – Ngăn Xếp

    Khái niệm Stack và các phương thức sử dụng trên Stack.
    30/08/2015 20/09/2020 3 phút đọc
    Stack – Ngăn Xếp

    Stack – Ngăn xếp là cấu trúc dữ liệu quan trọng , là kiến thức không thể thiếu trong khoa học máy tính và được ứng dụng rất nhiều trong lập trình. Nó là kiểu dữ liệu cơ bản để giải những bài toán từ đơn giản đến phức tạp, nhiều bài toán phức tạp đã được đơn giản hóa đi rất nhiều nhờ loại cấu trúc dữ liệu này.

    Stack là gì?

    Stack là một kiểu cấu trúc dữ liệu và cơ chế của nó là LIFO (Last In First Out) nghĩa là vào sau ra trước, có thể hình dung Stack như một chồng đĩa, chỉ có thể lấy chiếc đĩa ra hoặc thêm một chiếc đĩa khác vào trên đỉnh của nó và chiếc đĩa nằm trên đỉnh đó được gọi là Top.

    Stack

    Các phương thức của Stack

    Cài đặt cấu trúc stack

    Sử dụng struct để tạo cấu trúc stack.

    struct Number
    {
    	int number;
    	Number *pNextNum;
    };
    Number *top;

    Struct tên là Number, trong struct này gồm có một field kiểu int để lưu trữ giá trị của một phần tử và con trỏ kiểu Number để trỏ tới phần tử kế tiếp trên nó trong stack. Con trỏ top kiểu Number dùng để trỏ tới phần tử trên cùng của stack.

    isEmpty()

    Phương thức isEmpty() này giúp kiểm tra stack có rỗng hay không, nếu rỗng sẽ trả về true nếu không rỗng sẽ trả về false.

    int isEmpty()
    {
        if (top == NULL)
            return true;
        return false;
    }

    Push()

    Phương thức Push() dùng để thêm một phần tử vào trên cùng của stack.

    void pushNum(int value)
    {
        Number *ptr = new Number;//tạo mới một phần tử
        ptr->number = value;     //gán giá trị cho phần tử
        ptr->pNextNum = top; //phần tử này trỏ tới phần tử dưới nó trong stack
        top = ptr;    //đánh dấu phần tử này hiện đang nằm trên đỉnh của stack
    }

    Tạo ra một con trỏ mới kiểu Number và gán giá trị cho phần tử này. Cho phần tử này liên kết đến phần tử nằm ngay dưới nó bằng cách sử dụng field pNextNum trỏ tới phần tử đó. Cuối cùng dùng con trỏ top trỏ tới phần tử vừa được thêm vào stack để có thể lấy phần tử đó ra.

    Pop()

    Phương thức Pop() là lấy một phần tử nằm trên đỉnh của stack.

    int popNumber()
    {
    	int result = 0;
    	if (isEmpty())
    	{
    		return NULL; //nếu stack rỗng thì return về NULL
    	}
    	else
    	{
    		Number *ptr = top; //dùng một con trỏ trỏ tới phần tử đầu tiên của stack
    		result = top->number; //lấy giá trị 
    		top = top->pNextNum; //gán con trỏ top cho phần tử ngay dưới nó
    		delete ptr;		//delete phần tử vừa được lấy
    		return result;	// trả kết quả
    	}
    }

    Nhiệm vụ của phương thức này là lấy một phần tử ở trên đỉnh của stack và trả về giá trị của phần tử đó. Ngay sau khi lấy một phần tử ra thì phải xóa phần tử đó đi để tránh memory leak.

    Có thể hình dung stack được xây dựng bằng linked list qua sơ đồ sau:

    Sơ đồ xây dựng Stack bằng Linked list
    0 Bình luận
    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021