Bộ nhớ động ứng dụng của stack

Việc thiết kế stack, queue sử dụng mảng để lữu trữ dữ liệu thì ta luôn gặp phải một số rắc rối sau: - Lãng phí bộ nhớ: giả sử bạn khai báo mảng số nguyên gồm 100 phần tử int array_entry[100], khi đó bạn sẽ có 1 vùng nhớ cho 100 phần tử, nhưng chương trình của bạn chỉ thường xuyên dùng có 10, 20, và chỉ một vài lần là sử dụng đến 100 phần tử thì tức là bạn đã phí phạm tới 90 phần tử không được sử dụng tới. - Thiếu bộ nhớ: vì tiết kiệm, bạn chỉ khai báo có 10 phần tử int array_entry[10], nhưng nếu bạn cần dùng hơn thế, con số 15 chẳng hạn thì khi đó xảy ra hiện tượng tràn (stack, queue). Chưa hết, array cần một vùng nhớ liên tục, giả sử máy của bạn vẫn còn nhiều bộ nhớ, nhưng không có vùng nhớ trống liên tục nào đủ lớn cho mảng của bạn. Thế là vẫn .. thiếu bộ nhớ. Khi đó, để khắc phục tình trạng này thì một cách hữu hiệu là sử dụng cấu trúc trên kết hợp với danh sách liên kết (đơn). Lúc này, ta xây dựng một danh sách liên kết. Xem con trỏ nắm giữ danh sách này đang trỏ vào đỉnh của stack, stack cạn khi danh sách là rỗng . .(đối với queue thì cần có 2 con trỏ, một trỏ tới đầu của danh sách(lối trước), một trỏ tới cuối danh sách(lối sau)). Một phần tử của danh sách có thể được biểu diễn qua cấu trúc như sau: (mỗi phần tử được coi là một node) struct Node { // data members Node_entry entry; Node *next; // constructors Node(); Node(Node_entry item, Node *add_on = null); }; Node_entry là kiểu dữ liệu để chứa data của phần tử, entry chính là nơi data của phần tử được lưu. Ở trong hình vẽ trên thì node đầu tiên chứa Fred, 367-2205 và Jan. 28 Và các hàm khởi tạo cho nó như sau: Node::Node() { next = NULL; } Node::Node(Node_entry item, Node *add_on) { entry = item; next = add_on; } Như vậy, khi ta khai báo Node* data và khởi tạo xong cho data thì data->entry sẽ là phần dữ liệu của node đó, và data->next sẽ là đường dẫn tới node tiếp theo. Như thế thì ta có thể duyệt hết toàn bộ data mà ta đã lưu trong danh sách rồi. Để rõ hơn, ta hãy xem một ví dụ qua đoạn code nhỏ sau. Chú ý: khi data->next == NULL thì tức là node này là phần tử cuối cùng. enum Error_code {underflow, success, overflow}; typedef int Stack_entry; class Stack { public: Stack(); Bool empty() const; Stack_entry push(const Stack_entry &item); Stack_entry top(Stack_entry &item) const; Error_code pop(); protected: Node *top_node; } Các hàm Push, Pop của Stack thì ta thực hiện như sau: Stack_entry Stack::push(const Stack_entry &item) { Node *new_top = new Node(item, top_node); if (new_top == NULL) return 0; top_node = new_top; return item; } /********************************************************************/ Error_code Stack::pop() { Node *old_top = top_node; if (top_node == NULL) return underflow; top_node = old_top->next ; delete old_top; count--; return success; } /*******************************************************************/ Stack_entry Stack::top(Stack_entry &item) const { if (top_node == NULL) return 0; item = top_node->entry; return item; } /*******************************************************************/ bool Stack::empty() const { if (top_node == NULL) return true; return false; } /*******************************************************************/ Stack::Stack() { top_node = NULL; count = 0; }