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

em mới tìm hiểu về stack , anh chị cho em hỏi cài stack bằng mảng có gì khác với danh sách liên kết đơn vậy ạ , ưu và nhược điểm của mỗi loại là gì vậy ạ .
em cảm ơn

Thế bạn đã biết mảng và dslk đơn khác gì nhau chưa

3 Likes

Cuong_Nguyen_Huu:

mảng có gì khác với danh sách liên kết đơn

Kết quả ở trang đầu tiên

2 Likes

Home Categories FAQ/Guidelines Terms of Service Privacy Policy

Yêu cầu:

Minh họa cài đặt stack bằng danh sách liên kết. Mỗi phần tử của stack sẽ chứa 1 số nguyên. Do vậy mỗi node của danh sách liên kết sẽ gồm 1 trường dữ liệu kiểu int, 1 con trỏ next. Thao tác loại bỏ (pop()) hay bổ sung (push()) sẽ thực hiện với ô đầu tiên của danh sách liên kết.

Các phép toán cơ bản: 1. Khởi tạo 2. Kiểm tra ngăn xếp rỗng: 3. Nạp vào : nạp phần tử vào đầu ngăn xếp 4. Lấy ra : trả lại giá trị của phần tử ở đầu ngăn xếp và xóa bỏ phần tử đó khỏi ngăn xếp

5. Hiển thị các phần tử của ngăn xếp

/*  * To change this license header, choose License Headers in Project Properties.  * To change this template file, choose Tools | Templates  * and open the template in the editor.  */ /*  * File:   khoa.cpp  * Author: KHOA  *  * Created on August 26, 2016, 9:16 AM  */ #include <iostream> #include<stdio.h> #include<stdio.h> using namespace std; struct Node {     int data;     Node *next; }; struct List {     Node *head;     Node *tail; }; // khoi tao stack void Init(List &s) {     s.head = s.tail = NULL; } // kiem tra stack co rong khong bool isEmpty(List &s) {     if (s.head == NULL) return true;     else return false; } // tao Node Node *creat_Node(int x) {     Node *p = new Node;     if (p != NULL) {         p->data = x;         p->next = NULL;     } else return NULL; } // Push vao stack void push(List &s, int x) {     Node *p = creat_Node(x);     if (isEmpty(s)) {         s.head = s.tail = p; // neu stack rong thi ta gan p la phan tu dau va cuoi     } else {         p->next = s.head; // cho phan tu ke tiep bang phan tu dau         s.head = p; // cap nhat phan tu dau la phan tu moi them vao     } } // Pop phan tu ra khoi stack void pop(List &s) {     Node *p = s.head;     if (!isEmpty(s)) {         s.head = p->next;         delete p;     } else {         cout << "\nDanh sach da rong! ";     } } // tim kiem phan tu trong stack Node *search_Node(List &s, int x) {     Node *q = s.head;     while (q != NULL) {         if (q->data == x) {             return q;         } else {             q = q->next;         }     }     return NULL; } // Nhap du lieu cho Stack void nhap(List &s) {     int n;     cout << "nhap so luong phan tu cho stack: ";     cin>>n;     for (int i = 1; i <= n; i++) {         int x;         cout << "Phan tu " << i << ": ";         cin>>x;         push(s, x);     } } // xuat cac phan tu trong stack void xuat(List &s) {     Node *p = s.head;     while (p != NULL) {         cout << " " << p->data;         p = p->next;     } } int main() {     List s;     Init(s);     nhap(s);     xuat(s);     int x;     int lc;     do {         cout << "\n_ _ _CHUONG TRINH STACK_ _ _";         cout << endl;         cout << " 1.Push Stack"                 << "\n 2.Pop Stack"                 << "\n 3.Tim phan tu"                 << "\n 4.Thoat";         cout << "\nNhap thong tin can kiem tra: ";         cin>>lc;         switch (lc) {             case 1: cout << "Nhap phan tu can Push: ";                 cin>>x;                 push(s, x);                 break;             case 2: cout << "Pop phan tu trong Stack ";                 pop(s);                 cout << "\n";                 break;             case 3: cout << "Nhap phan tu can tim kiem: ";                 cin>>x;                 if (search_Node(s, x) != NULL) cout << "Tim thay phan tu!\n";                 else cout << "khong tim thay!\n";                 break;             case 4: break;             default: cout << "Ban nhap sai ";         }         xuat(s);         cout << "\n";     } while (lc != 4);     return 0; }

STACK - HÀNG ĐỢI a)Khái niệm nNgăn xếp là một danh sách tuyến tính trong đó phép bổ sung và phép loại bỏ phần tử được thực hiện ở một đầu gọi là đỉnh (Top). n Ngăn xếp là một danh sách kiểu LIFO (Last In - Firts Out). n Hai phép toán chính của stack: push() - thêm một nút ở đỉnh pop() - lấy đi một nút ở đỉnh nCấu trúc dữ liệu của ngăn xếp: //Khai báo kiểu Item (nếu cần) struct node{ Item infor; node *next; } struct node *s;//khai báo stack S là con trỏ trỏ và đỉnh stack (1) Khởi tạo ngăn xếp rỗng void create(struct node *s){ s = NULL; } (2) Kiểm tra ngăn xếp rỗng int Empty(struct node *s){ return (s == NULL); } (3) Thêm một phần tử x vào đỉnh ngăn xếp: void Push(struct node *s, item x){ struct node *p; p= new node; p->infor= x; p->next= NULL; if (s==NULL) s= p; else{ p->next = s; s= p; } } (4) Loại bỏ một phần tử ở đỉnh ngăn xếp: int Pop(struct Stack *s, item &x){ else{ p= s; x= s->infor; delete p; return 1; } struct node *p; if (Empty(s) ) return 0; p= new node; s= s->next; } QUEUE - HÀNG ĐỢI:\ a)Khái niệm - Hàng đợi là kiểu danh sách tuyến tính, trong đó phép bổ sung một phần tử được thực hiện ở một đầu gọi là lối sau (rear) và phép loại bỏ một phần tử được thực hiện ở đầu kia gọi là lối trước (front) của hàng đợi. - Hàng đợi là kiểu danh sách dạng FIFO (First In-First Out). nCấu trúc dữ liệu của hàng đợi: //Khai báo kiểu Item (nếu cần) struct node{ Item infor; struct node *rear; struct queue q; node *next; }; struct queue{ struct node *front; }; (1) Khởi tạo hàng đợi rỗng: void create(struct queue *q){ q->front = NULL; q->rear= NULL; } (2) Kiểm tra hàng đợi rỗng: int Empty(struct queue q){ return (q.front == NULL) ; } (3) Thêm một phần tử x vào lối sau của hàng đợi: void Push(struct queue *q, item x){ struct node *p; p= new node; p->infor= x; p->next= NULL; if (Empty(*q)){ q->front= p; q->rear=p; } else{ q->rear->next = p; q->rear= p; delete p; } } (4) Loại bỏ một phần tử ở lối trước của hàng đợi: int Pop(struct queue *q, item &x){ struct node *p; if (Empty(*q)) return 0; else{ p= new node; p= q->front; x= q->front->infor; q->front= q->front->next; delete p; return 1; } } Ngoài ra các bạn có thẻ tham khảo code mấu, bài tập và slide ở dưới CHU HẢI ĐĂNG Học viện công nghẹ bưu chính viễn thông Hà Nội. Phone: 01658991973 Email: Facebook://www.facebook.com/HaiDangChu y! : chu.haidang