Bài 8: Các hàm cơ bản và bài tập minh họa về STACK - Sử dụng thư viện chuẩn STL cho C/C++

Đăng bởi: Admin | Lượt xem: 7889 | Chuyên mục: C/C++

Một số hàm quan trọng trong Stack :

Push : Thêm một phần tử vào đỉnh của ngăn xếp, số phần tử của ngăn xếp tăng lên 1.
Pop: Xóa bỏ phần tử đầu tiên ở đỉnh của ngăn xếp, số phần tử của ngăn xếp giảm đi 1.
Top: Lấy giá trị của phần tử đầu tiên ở đỉnh của ngăn xếp, số phần tử của ngăn xếp không thay đổi.
IsEmpty: Kiểm tra ngăn xếp trống hay không. Ngăn xếp trống là ngăn xếp không có phần tử nào.
IsFull: Kiểm tra ngăn xếp đã đầy hay chưa. Thao tác này không phải lúc nào cũng có.
Size: Lấy số lượng phần tử stack đang có.

Cú pháp sử dụng các hàm :

Kiểm tra stack đầy(IsFull) :

Hàm này sẽ kiểm tra xem stack hiện tại đã đầy hay chưa. Nếu chỉ số top của stack đang bằng với capacity - 1, tức stack đã đầy.

bool IsFull(int capacity){
    if(top >= capacity - 1){
        return true;
    }else{
        return false;
    }
}

Kiểm tra stack rỗng(IsEmpty)

Nếu như stack đang không có phần tử nào, ta sẽ gán chỉ số top = -1 để đánh dấu. Như vậy, để kiểm tra stack có đang rỗng hay không rất đơn giản. Ta chỉ cần so sánh giá trị top có phải -1 hay không mà thôi.

bool IsEmpty(){
    if(top == -1){
        return true;
    }else{
        return false;
    }
}

Thêm phần tử vào đỉnh stack(Push) :

Chúng ta sẽ chỉ có thể push(thêm phần tử) vào đỉnh stack khi stack chưa đầy. Nếu stack đầy, chúng ta sẽ đưa ra thông báo và không thực hiện push. Ngược lại, ta sẽ tăng top lên một đơn vị và gán giá trị cho phần tử tại chỉ số top.

void Push(int stack[], int value, int capacity){
    if(IsFull(capacity) == true){
        printf("\nStack is full. Overflow condition!");
    }else{
        ++top;
        stack[top] = value;
    }
}

Xóa phần tử khỏi đỉnh stack(Pop)

Chúng ta sẽ chỉ có thể pop(xóa phần tử) khỏi đỉnh stack khi stack không trống. Nếu stack trống, chúng ta sẽ đưa ra thông báo và không thực hiện pop. Ngược lại, ta sẽ giảm giá trị top đi một đơn vị.

void Pop(){
    if(IsEmpty() == true){
        printf("\nStack is empty. Underflow condition!");
    }else{
        --top;
    }
}

Lấy giá trị phần tử ở đỉnh stack(Top) :

Để lấy giá trị phần tử ở đỉnh stack, ta có thao tác rất đơn giản:

int Top(int stack[]){
    return stack[top];
}

Lấy số lượng phần tử stack đang có(Size)

Biến top lưu chỉ số lớn nhất của stack. Như vậy, việc lấy size của stack cực kỳ đơn giản:

int Size(){
    return top + 1;
}

Và cuối cùng, chúng ta sẽ có 1 chương trình cài đặt stack hoàn thiện như sau:

#include <stdio.h>
 
int top = -1;
 
bool IsFull(int capacity){
    if(top >= capacity - 1){
        return true;
    }else{
        return false;
    }
}
 
bool IsEmpty(){
    if(top == -1){
        return true;
    }else{
        return false;
    }
}
 
void Push(int stack[], int value, int capacity){
    if(IsFull(capacity) == true){
        printf("\nStack is full. Overflow condition!");
    }else{
        ++top;
        stack[top] = value;
    }
}
 
void Pop(){
    if(IsEmpty() == true){
        printf("\nStack is empty. Underflow condition!");
    }else{
        --top;
    }
}
 
 
int Top(int stack[]){
    return stack[top];
}
 
int Size(){
    return top + 1;
}
 
int main(){
    int capacity = 3; 
    int top = -1; 
    int stack[capacity];
    
    // pushing element 5 in the stack .
    Push(stack, 5, capacity); 
    
    printf("\nCurrent size of stack is %d", Size());
    
    Push(stack, 10, capacity);
    Push(stack, 24, capacity);
    
    printf("\nCurrent size of stack is %d", Size());
    
    // As the stack is full, further pushing will show an overflow condition.
    Push(stack, 12, capacity); 
    
    //Accessing the top element
    printf("\nThe current top element in stack is %d", Top(stack));
    
    //Removing all the elements from the stack
    for(int i = 0 ; i < 3;i++)
        Pop();
    printf("\nCurrent size of stack is %d", Size());
    
    //As the stack is empty , further popping will show an underflow condition.
    Pop();  
}

Bài tập ứng dụng :

Bài 1 : chuyển từ thập phân sang nhị phân dùng stack trong :

#include <stdio.h>
#include <conio.h>
#include <memory.h>
#include <malloc.h>
#include <time.h>
 
 
class Stack
{
public:
    Stack(void);
    Stack(int size);
    virtual ~Stack(void);
    int Push(int number);
    int Pop(int& number);
    int SetSize(const int size);
    void Clear();
    int GetNumberElement() const;
 
private:
    Stack& operator=(const Stack& stack);
    Stack(const Stack& stack);
 
    int     m_index;
    int     m_size;
    int*    m_data;
};
 
 
Stack::Stack(void)
{
    m_size = 0;
    m_data = 0;
    m_index = -1;
}
 
Stack::Stack(int size)
{
    if(size > 0)
    {
        m_size = size;
        m_data = (int *)malloc(size * sizeof(int));
        memset(m_data, 0, size * sizeof(int));
    }
    else
    {
        m_size = 0;
        m_data = 0;
    }
    m_index = -1;
}
Stack::~Stack(void)
{
    Clear();
}
 
int Stack::SetSize(const int size)
{
    if(size > 0)
    {
        if(m_data)
        {
            free(m_data);
        }  
        m_index = -1;
        m_size = size;
        m_data = (int *)malloc(size * sizeof(int));
        memset(m_data, 0, size * sizeof(int));
    }
    return 0;
}
 
int Stack::Push(int number)
{
    if(m_index < m_size)
    {
        m_data[++m_index] = number;
        return 1;
    }
    return 0;
}
int Stack::Pop(int& number)
{
    if(m_index >= 0)
    {
        number = m_data[m_index--];
        return true;
    }  
    return false;
}
 
void Stack::Clear()
{
    if(m_data)
        free(m_data);
     m_data = 0;
    m_size = 0;
    m_index = -1;
}
 
int Stack::GetNumberElement() const
{
    return m_index + 1;
}
 
int main(int argc, char* argv[])
{      
    int number;
    printf("n = ");
    scanf("%d", &number);
        int k = number;
    Stack my_stack(200);
    while(number)
    {
        my_stack.Push(number % 2);
        number /= 2;
    }
    printf("\nConvert to binary:\n");
    printf("%d(10) = ", k);
    while(my_stack.GetNumberElement())
    {
        int number;
        my_stack.Pop(number);
        printf("%d", number);
    }
    printf("(2)\n");
    printf("\nDone!!!!!\n");
    getch();
    return 0;
}

Bài tiếp theo: Queue - Khái niệm cơ bản >>

Theo dõi VnCoder trên Facebook, để cập nhật những bài viết, tin tức và khoá học mới nhất!