NGĂN XẾP STACK
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
MỚI CẬP NHẬT

Cài đặt Stack bằng danh sách liên kết

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách cài đặt cấu trúc Stack trong danh sách liên kết. Đây là một trong hai cách được sử dụng để cài đặt cấu trúc Stack.

test php

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh sách liên kết để cài đặt: Push, Pop, Top(), isEmpty().

1. Cấu trúc dữ liệu của Stack

Trong phần này mình sử dụng danh sách liên kết để cài đặt cho Stack vì vậy cấu trúc dữ liệu chính của nó chính là danh sách liên kết. Ta sẽ có cấu trúc của một Node trong Stack.

//khai báo cấu trúc Node
struct Node {
	int data;
	Node *next;
};
typedef struct Node *stack;

Tiếp đến ta sẽ có cấu trúc của Stack, để quản lý Stack ta sử dụng con trỏ đầu để quản lý.

Bài viết này được đăng tại [free tuts .net]

//khai báo cấu trúc stack
struct Stack{
	Node *head;
	Node *tail;
};

Sau khi đã khởi tạo cấu trúc của một Node và cấu trúc của Stack, ta sẽ tạo một Node mới.

//tạo Node
Node *createNode(int data) {
	Node *p = new Node();
	if (p == NULL) {
		return NULL;
	}
	p->data = data;
	p->next = NULL;

	return p;
}

Như vậy là ta dã có cấu trúc cần thiết trong Stack cũng như đã khởi tạo cho nó, bây giờ chúng ta đã có thể thực hiện các thao tác trên Stack vừa được tạo.

2. Hàm isEmpty

Việc đầu tiên khi muốn thực hiện một thao tác nào đó trong Stack thì ta phải kiểm tra xem trong Stack có tồn tại phẩn tử hay không, Nếu Stack rỗng thì ta không thể thực hiện các thao tác đó trên Stack được.

//kiểm tra stack rỗng
bool isEmpty(stack s) {
	return (s == NULL);
}

3. Hàm Push

Khi thêm một phần tử vào Stack, trước tiên ta cần kiểm tra xem danh sách có rỗng hay không, nếu danh sách rỗng thì phần tử đầu tiên thêm vào chính là Node p. Ngược lại nếu danh sách đã tồn tại phần tử thì ta cho con trỏ của Node p trỏ đến Node đầu của danh sách để tạo liên kết.

Sau khi tạo liên kết cho Node p vừa được thêm vào, ta cập nhật là Node đầu cho danh sách.

void push(stack &s, int data) {
  // tạo một Node mới
	Node *ptr = createNode(data);
  // kiểm tra stack rỗng
	if (isEmpty(s)) {
		s = ptr;
	}
  //nếu tồn tại phần tử ta trỏ đến phần tử đầu danh sách
	else {
		ptr->next = s;
		s = ptr;
	}
}

4. Hàm Pop

Việc xóa một phần tử khỏi Stack được thực hiện khá đơn giản, đầu tiên ta cũng sẽ phải kiểm tra xem danh sách có tồn tại phần tử hay không. Nếu danh sách rỗng thì ta thực hiện return và kết thúc hàm, ngược lại nếu danh sách có tồn tại phần tử thì ta bắt đầu thực hiện các bước sau:

  • Gán giá trị của Node đầu Stack vào biến x.
  • Cập nhập Node đầu Stack và Node tiếp theo.
  • Xóa Node đầu Stack vừa lấy chính là Node x.
int pop(stack &s) {
	if (!isEmpty(s)) {
    //tạo một biến data
		int data = s->data;
    //tạo Node x và gán cho bằng s
		Node *x = s;
    // cho s = s trỏ đến next
		s = s->next;
    // thực hiện xóa node x
		delete(x);
    cout<<"Xóa thành công !!";
		return data;
	}
	else {
		cout << "Stack rỗng!" << endl;
	}
}

5. Hàm Top

Hàm Top() có chức năng hiển thị phần tử và không xóa nó khỏi Stack, không giống như Pop sau khi lấy phần tử từ Stack ra nó sẽ thực hiện xóa luôn phần tử đó khỏi Stack.

Đầu tiên ta sẽ kiểm tra xem danh sách có phần tử hay không, nếu có thì ta mới thực hiện lấy giá trị x, nếu danh sách rỗng thì return và kết thúc hàm.

int top(stack s) {
        // kiểm tra stack tồn tại phần tử thì thực hiện hiển thị ra màn hình
	if (!isEmpty(s)) {
		return s->data;
	}
	else {
		cout << "Stack rỗng!" << endl;
	}
}

6. Ví dụ xây dựng một cấu trúc Stack hoàn chỉnh

Ta đã có lần lượt các hàm cần thiết cho một cấu trúc Stack, các bạn có thể tham khảo một chương trình mình đã viết sẵn dưới đây. Chương trình chỉ đơn giản là thêm phần tử, xóa phần tử và hiển thị phần tử và sử dụng danh sách liên kết để cài đặt cho Stack.

Full code:

#include<iostream>
using namespace std;
//khai báo cấu trúc Node
struct Node {
	int data;
	Node *next;
};
typedef struct Node *stack;
//khai báo cấu trúc stack
struct Stack{
	Node *head;
	Node *tail;
};

//kiểm tra stack rỗng
bool isEmpty(stack s) {
	return (s == NULL);
}

//tạo Node
Node *createNode(int data) {
	Node *p = new Node();
	if (p == NULL) {
		return NULL;
	}
	p->data = data;
	p->next = NULL;

	return p;
}

void push(stack &s, int data) {
  // tạo một Node mới
	Node *ptr = createNode(data);
  // kiểm tra stack rỗng
	if (isEmpty(s)) {
		s = ptr;
	}
  //nếu tồn tại phần tử ta trỏ đến phần tử đầu danh sách
	else {
		ptr->next = s;
		s = ptr;
	}
}

int top(stack s) {
	if (!isEmpty(s)) {
		return s->data;
	}
	else {
		cout << "Stack is empty!" << endl;
	}
}


int pop(stack &s) {
	if (!isEmpty(s)) {
    //tạo một biến data
		int data = s->data;
    //tạo Node x và gán cho bằng s
		Node *x = s;
    // cho s = s trỏ đến next
		s = s->next;
    // thực hiện xóa node x
		delete(x);
    cout<<"Xóa thành công !!";
		return data;
	}
	else {
		cout << "Stack rỗng!" << endl;
	}
}

int main() {
  int lc, k;
	stack s;
  push(s, 10);
  push(s, 11);
  push(s, 12);
  push(s, 13);
  push(s, 14);
  push(s, 15);
  push(s, 16);
  cout<<"danh sách các số bao gồm : 10, 11, 12, 13, 14, 15, 16";
do{
		cout << "\n\n\t\t ============== Menu ==============";
		cout << "\n\t1. Hiển thị phần tử đầu Stack";
		cout << "\n\t2. Xóa phần tử đầu Stack";
		cout << "\n\t0. Ket thuc";
		cout << "\n\n\t\t ============== End ==============";
    cout<<"\nNhập lựa chọn bạn muốn chọn: ";
		cin>> lc;
		switch(lc){
			case 0: break;
			case 1: 
      cout<<"Phần tử đầu tiên trong Stack: "<<top(s);
      break;
			case 2:
      pop(s);
      break;
			default: cout<<"\nNhập sai, vui lòng nhập lại!";
		}
	} while(lc);
  cout<<"Chương trình này được đang tại Freetuts.net";
}

Kết quả: Mình đã thực hiện thêm phần tử sẵn trước đó bao gồm các số: 10, 11, 12, 13 ,14, 15, 16.

stack dslk PNG

7. Kết luận

Như vậy là chúng ta đã tìm hiểu xong về cấu trúc dữ liệu của Stack và các thao tác cơ bản của nó. Trong bài này mình đã sử dụng danh sách liên kết để cài đặt cho Stack, ở bài tiếp theo mình sẽ sử dụng mảng một chiều để cài đặt cho Stack. Các bạn hãy chú ý theo dõi nhé !!!

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Tìm kiếm phần tử k trong danh sách liên kết đôi

Tìm kiếm phần tử k trong danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu cách tìm kiếm một phần tử k trong…

Top