Trang 1 trên tổng số 5 123... Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 47 kết quả

Đề tài: Ngăn xếp và hàng đợi (Stack and Queue) - Nguyên tắc và cài đặt trên C++

  1. #1
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    169

    Unhappy Ngăn xếp và hàng đợi (Stack and Queue) - Nguyên tắc và cài đặt trên C++

    Thứ nhất về stack.

    Stack là gì: stack là một kiểu dữ liệu trừu tượng, một cấu trúc có nhiều nút giống như List vậy (Danh sách liên kết) nhưng chúng ta chỉ được phép thêm nút mới vào đỉnh stack (tác vụ push) hoặc xóa nut ở đỉnh stack (tác vụ Pop), hay chúng ta còn gọi cơ chế của stack là cơ chế Lifo (vào trước ra sau). Bạn cứ hình dung stack như một cái băng đạn mỗi nút là một viên đạn, viên đạn nào vào trước thì ra sau, viên nào vào sau thì ra trước. OK
    Còn stack để làm gì ư. Stack để giải quyết những vấn đề theo cơ chế LIFO như chuyển một biểu thức dạng trung tố về hậu tố.

    Sau đây là mô hình cho Stack-ADT
    1. Mô tả dữ liệu:
    • Có nhiều nút cùng một kiểu
    • Có đỉnh stack (top)

    2. Mô tả các tác vụ trên stack

    initialize

    Chức năng: Khởi động stack
    Dữ liệu nhập: Không
    Dữ liệu xuất: stack top về vị trí khởi đầu.

    empty:

    Chức năng kiểm tra stack có bị rỗng không.
    Dữ liệu nhập: Không
    Dữ liệu xuất: True or False (True: khi stack rỗng, False: stack không bị rỗng).

    pusth
    Chức năng: thêm nút mới tại đỉnh stack
    Dữ liệu nhập: nút mới.
    Dữ liệu xuất: không

    pop

    Chức năng: xóa nút tại đỉnh stack.
    Dữ liệu nhập: Không.
    Điều kiện: stack không bị rỗng.
    Dữ liệu xuất: nút bị xóa.

    Stacktop:

    Chức năng: truy xuất nút tại đỉnh stack.
    Dữ liệu nhập: Không.
    Điều kiện: stack không bị rỗng.
    Dữ liệu xuất: nút tại đỉnh stack.

    Stacksize

    Chức năng: xác định số nút hiện có trong stack.
    Dữ liệu: Không.
    Dữ liệu xuất: số nút hiện có trong stack.

    Clearstack:

    Chức năng: xóa tất cả các nút ở trong stack.
    Dữ liệu nhập: không.
    Dữ liệu xuất:stack top về vị trí khởi đầu.

    copystack:

    Chức năng: copystack thành stack thành stack mới.
    Dữ liệu nhập: stack nguồn.
    Dữ liệu xuất: stack đích giống stack nguồn.

    Phương pháp cài đặt stack

    Có rất nhiều cách cài đặt một stack nhưng đơn giản cũng như để dễ hình dung nhất là cài đặt bằng mảng hay còn gọi là cài đặt theo kiểu kế tiếp. Ngoài ra còn nhiều cách cài đặt khác như cài đặt bằng Danh sách liên kết (DSLK đơn, DSLK vòng, DSLK kép, DSLK vòng+kép mình thấy cài đặt bằng DSLK vòng +kép là hay nhất)

    Sau đây mình sẽ giới thiệu cho bạn về cách cài đặt một stack theo kiểu kế tiếp (bằng mảng đó) minh họa bằng ngôn ngữ C++
    C++ Code:
    1. const int Max = 100;
    2. class stack
    3. {
    4.       private:
    5.        int top;
    6.       int nodes[Max];
    7.    public:
    8.        stack()  // khoi tao stack
    9.       {
    10.            top = -1; // gan top = -1
    11.       }
    12.        bool empty()// Kiem tra xem stack co rong hay khong
    13.       {
    14.            if(top == -1)
    15.              return true;
    16.          else
    17.              return false;
    18.       }
    19.       void push(int data)
    20.       {
    21.          if(top == Max-1)
    22.              cout<<"Stack bi day";  // truong hop stack bi day
    23.          else
    24.                nodes[++top] = data;
    25.       }
    26.       int pop()
    27.       {
    28.            if(empty())  //truong hop stack bi rong
    29.              cout<<"Stack bi rong ";
    30.          else
    31.              return(nodes[top--]);
    32.       }
    33.       int stacktop()
    34.       {
    35.            if(empty())
    36.               cout<<"Stack bi rong ";
    37.              //su ly truong hop stack bi rong
    38.          else
    39.              return(nodes[top]);
    40.       }
    41. };

    Không hiểu gì thì cứ post bài ở tại topic này hoặc liên hệ qua nick Yahoo của mình.
    Còn Queue (hay còn gọi là hàng đợi) để tối mình viết nốt. Giờ bận xíu

  2. #2
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    169

    Mặc định Hàng đợi (Queue)

    Hàng đợi (Queue)

    [/B]Cũng tương tự như stack, Quêu là một cấu trúc có nhiều nút trải dài từ đầu hàng đợi đến cuối hàng đợi - với hàng đợi chúng ta chỉ được phép thêm nút vào cuối hàng đợi và xóa nút ở đầu hàng đợi nghĩa là việc truy xuất các nút trên hàng đợi xảy ra ở cả hai đầu. Vì nút thêm vào trước sẽ được lấy ra trước nên cấu trúc hàng đợi còn được gọi là cấu trúc FIFO (Firt In First Out). Ví dụ như bạn đi mua vé xem phim với người iu chẳng hạn thì người mua xếp hàng trước sẽ được mua vé trước còn người mua xếp hàng sau thì sẽ mua vé sau.

    Và hàng đợi để làm gì ???: Hàng đợi để giải quyết những vấn đề có cơ chế FIFO như dịch vụ quản lý kho, dịch vụ ngân hàng ....

    Và sau đây là mô hình Queue-ADT

    1. Mô tả dữ liệu:
    Có nhiều nút cùng kiểu dữ liệu.
    Có đầu hàng đợi (front) và cuối hàng đợi (tail)

    2. Mô tả các tác vụ trên hàng đợi:

    initialize:
    Chức năng: Khởi động hàng đợi.
    Dữ liệu nhập: không.
    Dữ liệu xuất: front và tail được gán giá trị phù hợp.

    empty:

    Chức năng: Kiểm tra hàng đợi có bị rỗng không.
    Dữ liệu nhập: không.
    Dữ liệu xuất True or False. (true khi hàng đợi rỗng, false khi hàng đợi không rỗng)
    insert:
    Chức năng: thêm nút mới vào cuối hàng đợi.
    Dữ liệu nhập: nút mới.
    Điều kiện: hàng đợi không bị đầy.
    Dữ liệu xuất: không.
    remove:
    Chức năng: xóa nút ở đầu hàng đợi.
    Dữ liệu nhập: không.
    Điều kiện: hàng đợi không bị rỗng.
    Dữ liệu xuất: nút bị xóa.
    queuefront:
    Chức năng truy xuất nút ở đầu hàng đợi.
    Dữ liệu nhập: không.
    Điều kiện: hàng đợi không bị rỗng.
    Dữ liệu xuất: nút tại đầu hàng đợi.
    queuetail:
    Chức năng truy xuất nút tại cuối hàng đợi.
    Dữ liệu nhập: không.
    Điều kiện: hàng đợi không bị rỗng.
    Dữ liệu xuất: nút tại cuối hàng đợi.

    queue size:
    Chức năng: xác định số nút hiện có trong hàng đợi.
    Dữ liệu nhập: không.
    Dữ liệu xuất:số nút có trong hàng đợi.

    clearqueue:

    Chức năng: xóa tất cả các nút có trong hàng đợi.
    Dữ liệu nhập: không.
    Dữ liệu xuất: front và tail với giá trị phù hợp.

    Các phương pháp cài đặt Queue-ADT

    Cũng như stack chúng ta cài đặt hàng đợi theo hai cách là cài đặt kiểu kế tiếp (dùng mảng 1 chiều hoặc dùng mảng vòng) và cài đặt kiểu liên kết (dùng DSLK đơn, vòng, kép, kép+vòng và giống như stack thì cài đặt bằng DSLK kép+vòng là hay nhất).
    Để đơn giản và dễ hiểu nhất thì tớ sẽ cài đặt bằng mảng 1 chiều. Minh họa bằng ngôn ngữ C++

    C++ Code:
    1. const Max = 100;
    2. class queue
    3. {
    4.       private:
    5.        int front,tail; //dau va cuoi hang doi
    6.       int nodes[Max];
    7.    public:
    8.        queue()   // cau tu khoi dong hang doi
    9.       {
    10.            front = 0;
    11.          tail = -1;
    12.       }
    13.       int empty();  // kiem tra hang doi bi rong khong
    14.       int full(); // kiem tra hang doi co bi day chua
    15.       void insert(int x); // them mot nut vao cuoi hang doi
    16.       int remove(); // xoa nut o dau hang doi
    17.       int queuesize(); // xac dinh so nut co trong hang doi
    18. };
    19. int queue::empty()
    20. {
    21.      return ((tail < front) ? true : false);
    22. }
    23. int queue::full()
    24. {
    25.     return ((tail == Max-1) ? true : false);
    26. }
    27. void queue::insert(int x)
    28. {
    29.      if(full())
    30.        cout<<"Hang doi bi day";
    31.    else
    32.         nodes[++tail] = x;
    33. }
    34. int queue::remove()
    35. {
    36.      if(empty())
    37.        cout<<"hang doi bi rong";
    38.    else
    39.        return(nodes[front++]);
    40. }
    41. int queue::queuesize()
    42. {
    43.     return(tail - front + 1);
    44. }
    Đã được chỉnh sửa lần cuối bởi iamvtn : 23-11-2007 lúc 11:01 PM.

  3. #3
    Ngày gia nhập
    10 2007
    Bài viết
    6

    Mình có chút thắc mắc:
    Giả sử stack có a[0],a[1].......................a[n] phần tử.
    Khi bạn gắn: top=-1; có phải nó tương ứng với a[1]?
    Mình thấy khi check stack của bạn là: top=max -1; => danh sách đầy.
    Nếu mình gắn: top=1; thì khi: top=max; => danh sách đầy???
    Giải thích giúp mình nhá
    Đã được chỉnh sửa lần cuối bởi iamvtn : 24-11-2007 lúc 01:29 PM.

  4. #4
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    169

    Trích dẫn Nguyên bản được gửi bởi chuonggio_mailaniemdau Xem bài viết
    Mình có chút thắc mắc:
    Giả sử stack có a[0],a[1].......................a[n] phần tử.
    Khi bạn gắn: top=-1; có phải nó tương ứng với a[1]?
    Mình thấy khi check stack của bạn là: top=max -1; => danh sách đầy.
    Nếu mình gắn: top=1; thì khi: top=max; => danh sách đầy???
    Giải thích giúp mình nhá.
    Thực sự bạn vẫn chưa hiểu về mảng, mảng ở đây số phần tử sẽ bắt đầu = 0, và top ở đây là để chỉ số phần tử đầu tiên trong mảng. Do vậy mình gán top = -1 tức là trường hợp mảng chưa có phần tử nào, và top = 0 tức là phần tử đầu tiên trong mảng và top = Max - 1 = 100 - 1 = 99 mảng đã đầy 100 phần tử. Còn nếu bạn gán top = 1 tức là bạn đã bỏ qua mất phần tử đầu tiên của mảng đó là phần tử a[0] và top = max = 100 thì sẽ bị vượt quá một phần tử của mảng. Nếu bạn khai báo mảng có 100 phần tử thì mảng sẽ bắt đầu từ a[0] cho đến a[99], chắc đến đây bạn hiểu rồi chứ. Tớ nghĩ bạn hãy xem lại lý thuyết về mảng để nắm rõ hơn, rất là cơ bản đấy.
    Đã được chỉnh sửa lần cuối bởi iamvtn : 27-11-2007 lúc 10:25 AM.

  5. #5
    Ngày gia nhập
    01 2007
    Nơi ở
    Somewhere I belong
    Bài viết
    169

    Mặc định Sử dụng stack để đổi cơ số.

    Sử dụng stack để đổi cơ số.

    C++ Code:
    1. class List;
    2. class Node
    3. {
    4.     private:
    5.     int data;
    6.       Node *next;
    7.    public:
    8.     Node(int d = 0,Node *p = NULL)
    9.     {
    10.         data = d;
    11.         next = p;
    12.       }
    13.       int get()
    14.       {
    15.         return data;
    16.       }
    17.       friend class List;
    18. };
    19. class List
    20. {
    21.     private:
    22.     Node *head;
    23.    public:
    24.     List() {head = NULL;}
    25.       ~List()
    26.       {
    27.         head = NULL;
    28.       }
    29.       int get()
    30.       {
    31.         return head->data;
    32.       }
    33.       void chen_dau(int d)
    34.       {
    35.         Node *p = new Node(d);
    36.          if(head == NULL)
    37.                 head=p;
    38.          else
    39.          {
    40.             p->next = head;
    41.             head = p;
    42.          }
    43.       }
    44.       void xoa_dau()
    45.       {
    46.         if(head)
    47.         {
    48.             Node *p = head;
    49.             head = head->next;
    50.             p->next = NULL;
    51.             delete p;
    52.         }
    53.       }
    54.       void chen_cuoi(int d)
    55.       {
    56.         Node *p = new Node(d);
    57.         Node *q = head;
    58.          if(head == NULL)
    59.         head=p;
    60.         else
    61.         {
    62.             while(q->next)
    63.             q = q->next;
    64.             q->next = p;
    65.         }
    66.       }
    67.       void xoa_cuoi()
    68.       {
    69.         if(head)
    70.         if(head->next == NULL)
    71.         {
    72.             delete head;
    73.             head=0;
    74.         }
    75.         else
    76.         {
    77.             Node *p,*q;
    78.             p=head;
    79.             p=p->next;
    80.             while(q->next)
    81.             {
    82.                 p = q;
    83.                 q = q->next;
    84.             }
    85.             delete q;
    86.             p->next = NULL;
    87.         }
    88.       }
    89.       bool empty()
    90.       {
    91.         if(head == NULL)
    92.             return true;
    93.          else
    94.             return false;
    95.       }
    96.       void hienthi()
    97.       {
    98.         Node *p = head;
    99.             while(p)
    100.         {
    101.             cout<<p->data<<"\t";
    102.             p = p ->next;
    103.         }
    104.       }
    105. };
    106. class stack
    107. {
    108.     private:
    109.         List a;
    110.    public:
    111.     void push(int d)
    112.       {
    113.         a.chen_dau(d);
    114.       }
    115.       int get()
    116.       {
    117.         return a.get();
    118.       }
    119.       void pop()
    120.       {
    121.         a.xoa_dau();
    122.       }
    123.       void hienthi()
    124.       {
    125.          a.hienthi();
    126.       }
    127.       bool empty()
    128.       {
    129.         if(a.empty() == true)
    130.             return true;
    131.          else
    132.             return false;
    133.       }
    134. };
    135.  
    136. void main()
    137. {
    138.     stack a;
    139.    int so,coso;
    140.    float sodu;
    141.    cout<<"Nhap vao so: ";
    142.    cin>>so;
    143.     cout<<"Co so la bao nhieu (2 or 4 or 8): ";
    144.    cin>>coso;
    145.    while(so != 0)
    146.    {
    147.     sodu = so % coso;
    148.       a.push(sodu);
    149.       so = so / coso;
    150.    }
    151.    cout<<"So vua chuyen la: ";
    152.    for(int i = 0;;i++)
    153.    {
    154.         cout<<a.get();
    155.       a.pop();
    156.       if(a.empty())
    157.       break;
    158.    }
    159.    getch();
    160. }

  6. #6
    Ngày gia nhập
    08 2008
    Nơi ở
    homeless
    Bài viết
    15

    Mặc định Ngăn xếp và hàng đợi (Stack and Queue) - Nguyên tắc và cài đặt trên C++

    Cho em hỏi nếu mình khai báo stack như sau:

    C Code:
    1. class stack
    2. {
    3.           int size;
    4.           int top;
    5.           int* stackPtr;
    6.       public:
    7.           stack(){};
    8.           stack(int s):size(s),top(0){stackPtr = new int [size];}
    9.            ......................
    10. }

    thì destructor mình viết hàm inline
    C Code:
    1. ~stack(){delete [] stackPtr;}

    hay là viết như vầy: (em nghĩ viết như cách này mới đúng)
    C Code:
    1. stack::~stack()
    2. {
    3.             while(! IsEmpty())
    4.             {
    5.                         delete [] stackPtr;
    6.                         top--;
    7.             }
    8. }

    Chúc mừng anh zkday lên chức
    Đã được chỉnh sửa lần cuối bởi trunkthai : 23-09-2008 lúc 11:57 AM.

  7. #7
    Ngày gia nhập
    10 2007
    Nơi ở
    /root
    Bài viết
    317

    Đây là stack tớ cài, chắc sẽ giải quyết được vấn đề của cậu :
    C++ Code:
    1. // stack.h
    2. #ifndef _STACK_H_
    3. #define _STACK_H_
    4.  
    5. template <class T>
    6. class Stack
    7. {
    8. private:
    9.     T *Item;
    10.     int Size;
    11.     int Top;
    12. public:
    13.     Stack(int s = 1);
    14.     ~Stack();
    15.     void Push(T obj);
    16.     T & Pop();
    17.     T & GetTop() const;
    18.     bool IsEmpty()const;
    19.  
    20. };
    21.  
    22. template <class T>
    23. Stack<T>::Stack(int s)
    24. {
    25.     Size = s;
    26.     Item = new T[s];
    27.     Top = -1;
    28. }
    29.  
    30. template <class T>
    31. Stack<T>::~Stack()
    32. {
    33.     delete [] Item;
    34. }
    35.  
    36. template <class T>
    37. void Stack<T>::Push(T obj)
    38. {
    39.     if(Top == Size - 1) // Stack đầy
    40.     {
    41.         Size *= 3;
    42.         T *NewItem = new T[Size]; // Mở rộng stack
    43.         for (int i = 0 ; i < Size ; i ++)
    44.         {
    45.             NewItem[i] = Item[i];
    46.         }
    47.  
    48.         delete [] Item;
    49.  
    50.         Item = NewItem;
    51.     }
    52.     Item[++Top] = obj;
    53. }
    54.  
    55. template <class T>
    56. T & Stack<T>::Pop()
    57. {
    58.     return Item[Top--];
    59. }
    60.  
    61. template <class T>
    62. T & Stack<T>::GetTop()const
    63. {
    64.     return Item[Top];
    65. }
    66.  
    67. template <class T>
    68. bool Stack<T>::IsEmpty() const
    69. {
    70.     if(Top == -1){
    71.         return true;
    72.     }
    73.     return false;
    74. }
    75.  
    76.  
    77. #endif //_STACK_H_

    Đã được chỉnh sửa lần cuối bởi Tab : 23-09-2008 lúc 12:12 PM.
    What you see is never what you get...

  8. #8
    Ngày gia nhập
    08 2008
    Nơi ở
    homeless
    Bài viết
    15

    Cám on anh void main,giờ mới thấy mình bị điên,con trỏ stack chỉ cấp phat 1 lần lúc khởi động để làm nhiệm vụ truy cập các phtu của stack thôi.
    Không hiểu sao mình dám viết destructor thế kia...Cám ơn mấy anh

  9. #9
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,918

    Code voidmain() có rất nhiều lỗi logic, code không safe. Ví dụ constructor chẳng hạn.
    Cấp phát size = s nhưng nội dung = undefined. -> giả nếu r2 gọi Pop() thì sao ?
    Cả pop lẫn top đều phải bắt buộc kiểm tra range.
    Hàm push mắc lỗi nghiêm trọng : DANGLING POINTER !

  10. #10
    Ngày gia nhập
    10 2007
    Nơi ở
    /root
    Bài viết
    317

    Tất nhiên , đây là code tớ phác thử , với việc gọi Pop , đúng ra phải kiểm tra Empty , nếu không kiểm tra Empty , giá trị trả về sẽ là 1 giá trị chưa được định nghĩa .
    Còn hàm Push, tớ ko hiểu lỗi RR nói , có thể chỉ rõ hơn đc ko ?
    What you see is never what you get...

Các đề tài tương tự

  1. Trả lời: 0
    Bài viết cuối: 20-05-2011, 10:39 PM
  2. Bài tập C++ Sử dụng cấu trúc dữ liệu Queue thực hiện trên DSLK ĐƠN để lưu trữ 1 dãy các số nguyên
    Gửi bởi kaner1111 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 2
    Bài viết cuối: 18-05-2011, 10:42 AM
  3. Stack, ngăn xếp - Thiết lập và ứng dụng stack trong C
    Gửi bởi PoPoPoPo trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 8
    Bài viết cuối: 15-11-2010, 11:24 PM
  4. Nhược điểm của ngăn xếp stack trên C?
    Gửi bởi gianghien1404 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 26
    Bài viết cuối: 24-07-2010, 12:45 PM
  5. Stack và Queue trên C++. Mọi người cùng góp ý nhé!
    Gửi bởi hoangedward trong diễn đàn Thảo luận, góp ý code C/C++ của bạn
    Trả lời: 7
    Bài viết cuối: 29-03-2010, 08:44 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn