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

[iamvtn]

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:

Lựa chọn code | Ẩn/Hiện code

const int Max = 100;
class stack
{
      private:
       int top;
      int nodes[Max];
   public:
       stack()  // khoi tao stack
      {
           top = -1; // gan top = -1
      }
       bool empty()// Kiem tra xem stack co rong hay khong
      {
           if(top == -1)
             return true;
         else
             return false;
      }
      void push(int data)
      {
         if(top == Max-1)
             cout<<"Stack bi day";  // truong hop stack bi day
         else
               nodes[++top] = data;
      }
      int pop()
      {
           if(empty())  //truong hop stack bi rong
             cout<<"Stack bi rong ";
         else
             return(nodes[top--]);
      }
      int stacktop()
      {
           if(empty())
              cout<<"Stack bi rong ";
             //su ly truong hop stack bi rong
         else
             return(nodes[top]);
      }
};

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

[iamvtn]

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:

Lựa chọn code | Ẩn/Hiện code

const Max = 100;
class queue
{
      private:
       int front,tail; //dau va cuoi hang doi
      int nodes[Max];
   public:
       queue()   // cau tu khoi dong hang doi
      {
           front = 0;
         tail = -1;
      }
      int empty();  // kiem tra hang doi bi rong khong
      int full(); // kiem tra hang doi co bi day chua
      void insert(int x); // them mot nut vao cuoi hang doi
      int remove(); // xoa nut o dau hang doi
      int queuesize(); // xac dinh so nut co trong hang doi
};
int queue::empty()
{
     return ((tail < front) ? true : false);
}
int queue::full()
{
    return ((tail == Max-1) ? true : false);
}
void queue::insert(int x)
{
     if(full())
       cout<<"Hang doi bi day";
   else
        nodes[++tail] = x;
}
int queue::remove()
{
     if(empty())
       cout<<"hang doi bi rong";
   else
       return(nodes[front++]);
}
int queue::queuesize()
{
    return(tail - front + 1);
}

[chuonggio_mailaniemdau]

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á

[iamvtn]

Trích dẫn:

Nguyên bản được gửi bởi chuonggio_mailaniemdau

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.

[iamvtn]

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

C++ Code:

Lựa chọn code | Ẩn/Hiện code

class List;
class Node
{
    private:
    int data;
      Node *next;
   public:
    Node(int d = 0,Node *p = NULL)
    {
        data = d;
        next = p;
      }
      int get()
      {
        return data;
      }
      friend class List;
};
class List
{
    private:
    Node *head;
   public:
    List() {head = NULL;}
      ~List()
      {
        head = NULL;
      }
      int get()
      {
        return head->data;
      }
      void chen_dau(int d)
      {
        Node *p = new Node(d);
         if(head == NULL)
                head=p;
         else
         {
            p->next = head;
            head = p;
         }
      }
      void xoa_dau()
      {
        if(head)
        {
            Node *p = head;
            head = head->next;
            p->next = NULL;
            delete p;
        }
      }
      void chen_cuoi(int d)
      {
        Node *p = new Node(d);
        Node *q = head;
         if(head == NULL)
        head=p;
        else
        {
            while(q->next)
            q = q->next;
            q->next = p;
        }
      }
      void xoa_cuoi()
      {
        if(head)
        if(head->next == NULL)
        {
            delete head;
            head=0;
        }
        else
        {
            Node *p,*q;
            p=head;
            p=p->next;
            while(q->next)
            {
                p = q;
                q = q->next;
            }
            delete q;
            p->next = NULL;
        }
      }
      bool empty()
      {
        if(head == NULL)
            return true;
         else
            return false;
      }
      void hienthi()
      {
        Node *p = head;
            while(p)
        {
            cout<<p->data<<"\t";
            p = p ->next;
        }
      }
};
class stack
{
    private:
        List a;
   public:
    void push(int d)
      {
        a.chen_dau(d);
      }
      int get()
      {
        return a.get();
      }
      void pop()
      {
        a.xoa_dau();
      }
      void hienthi()
      {
         a.hienthi();
      }
      bool empty()
      {
        if(a.empty() == true)
            return true;
         else
            return false;
      }
};

void main()
{
    stack a;
   int so,coso;
   float sodu;
   cout<<"Nhap vao so: ";
   cin>>so;
    cout<<"Co so la bao nhieu (2 or 4 or 8): ";
   cin>>coso;
   while(so != 0)
   {
    sodu = so % coso;
      a.push(sodu);
      so = so / coso;
   }
   cout<<"So vua chuyen la: ";
   for(int i = 0;;i++)
   {
        cout<<a.get();
      a.pop();
      if(a.empty())
      break;
   }
   getch();
}

[trunkthai]

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

C Code:

Lựa chọn code | Ẩn/Hiện code

class stack
{
          int size;
          int top;
          int* stackPtr;
      public:
          stack(){};
          stack(int s):size(s),top(0){stackPtr = new int [size];}
           ......................
}

thì destructor mình viết hàm inline

C Code:

Lựa chọn code | Ẩn/Hiện code

~stack(){delete [] stackPtr;}

hay là viết như vầy: (em nghĩ viết như cách này mới đúng)

C Code:

Lựa chọn code | Ẩn/Hiện code

stack::~stack()
{
            while(! IsEmpty())
            {
                        delete [] stackPtr;
                        top--;
            }
}

Chúc mừng anh zkday lên chức

[Tab]

Đây là stack tớ cài, chắc sẽ giải quyết được vấn đề của cậu :

C++ Code:

Lựa chọn code | Ẩn/Hiện code

// stack.h
#ifndef _STACK_H_
#define _STACK_H_

template <class T>
class Stack
{
private:
    T *Item;
    int Size;
    int Top;
public:
    Stack(int s = 1);
    ~Stack();
    void Push(T obj);
    T & Pop();
    T & GetTop() const;
    bool IsEmpty()const;

};

template <class T>
Stack<T>::Stack(int s)
{
    Size = s;
    Item = new T[s];
    Top = -1;
}

template <class T>
Stack<T>::~Stack()
{
    delete [] Item;
}

template <class T>
void Stack<T>::Push(T obj)
{
    if(Top == Size - 1) // Stack đầy
    {
        Size *= 3;
        T *NewItem = new T[Size]; // Mở rộng stack
        for (int i = 0 ; i < Size ; i ++)
        {
            NewItem[i] = Item[i];
        }

        delete [] Item;

        Item = NewItem;
    }
    Item[++Top] = obj;
}

template <class T>
T & Stack<T>::Pop()
{
    return Item[Top--];
}

template <class T>
T & Stack<T>::GetTop()const
{
    return Item[Top];
}

template <class T>
bool Stack<T>::IsEmpty() const
{
    if(Top == -1){
        return true;
    }
    return false;
}


#endif //_STACK_H_

[trunkthai]

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

[rox_rook]

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 !

[Tab]

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 ?