CÀI ĐẶT CHI TIẾT STACK VÀ HÀNG ĐỢI BẰNG NGÔN NGỮ C

[ductam]

Stack:
Khi học về stack bạn thử tưởng tượng rằng Stack như một chồng đĩa và dựng chồng đĩa thẳng đứng lên.
Mỗi thao tác thêm một phần tử vào stack tương ứng bỏ một đĩa vào chồng đĩa, lúc này chiều cao của đĩa tăng thêm một đơn vị. Như vậy ta có thao tác Push(yourtype x) : nghĩa là thêm phần tử x vào stack (yourtype là kiểu dữ liệu cần thiết cho bài toán của bạn)
Mỗi thao tác lấy một phần tử ra khỏi satck tương ứng lấy một đĩa ra khỏi chồng đĩa, lúc này chiều cao của chồng đĩa giảm đi một đơn vị. Như vậy ta có thao tác Pop().
Đấy là hai thao tác cơ bản và rất cần thiết cho Stack. Ngoài ra ta có thể có thêm thao tác Init Stack, thao tác này có thể nói không gì đơn giản hơn.
Để cài đặt chi tiết ta dùng màng một chiều stack[maxN] trong đó maxN là số phần tử tối đa của stack. Trong nhiều bài toán khi số phần tử trong stack rất lớn ta có thể kết hợp cấu trúc vòng (Tâm sẽ trao đổi vấn đề này sau).
Khi thao tác Pop và Push(yourtype x) thì chiều cao của stack thay đồi. Để đại diện cho chiều cao của stack ta có biến top, biến này có ý nghĩa cho biết đỉnh stack hiện tại.
Như vậy ban đầu stack rỗng thì top=-1. Vì phần tử đầu tiên trong mảng ở ngôn ngữ C là 0 --> khi stack rỗng thì ta nên để top=-1. Tuy nhiên nếu thích ta có thể qui định top=0 thì stack rỗng cũng được, lúc đó ta thay đổi chỉ số cho phù hợp.

Code:


#include<stdio.h>
#include<conio.h>

#define maxN 100000

long int stack[maxN];
long int top;


void Init();
void Push(long int x);
long int Pop();

int main()
{
 //Ban co the cai dat de test cho nay
 getch();
 return 0;
}
void Init()
{
 top=-1;   
}
void Push(long int x)
{
 top++;
 stack[top]=x;   
}
long int Pop()
{
 long int x=stack[top];
 top--;
 return x;
}



Bạn có thể nhận xét rằng trong thao tác Push và Pop trên không có thao tác kiểm tra stack rỗng hay tràn vì hầu như khi giải bài chúng ta không cần thiết chỗ này lắm. Nếu các bạn thấy cần thiết cài thì hầu như cũng không phức tạo lắm.
Việc nắm rõ stack rất quan trọng. Bài sau mình sẽ viết về cách sử dụng stack để khử đệ quy trong bài toán tìm kiếm theo chiều sâu. Thân chào các bạn. Chúc các bạn học tập ngày tốt hơn

Hôm nay rãnh rỗi, mình viết tiếp cách cài đặt queue, Sau đó mình sẽ viết tiếp ứng dụng queue trong bài tìm đường ngắn nhất bằng thứ tự topo, cũng như các ứng dụng của stack và queue trong bài toán tìm kiếm theo chiều rộng và tìm kiếm theo chiều sâu bằng cách không đệ quy.

Cũng như stack lý thuyết về queue các bạn ít nhiều cũng đã nắm rõ trong phần cấu trúc dữ liệu do thầy Văn "hiền lành" của chúng ta giảng dạy.
Và trong bài viết này mình sẽ trình bày cài queue bằng mảng một chiều. Đối với queue để dễ hình dung, các bạn có hai biến first và last. Biến first cho biết nếu cần lấy một phần tử ra khỏi queue thì ta lấy phần tử queue[first]. Và để loại phần tử vừa lấy ra khỏi queue đơn giản ta chỉ tăng first lên một vị trí. (first++) --> Ta có thao tác x=Pop(), trong đó x là phần tử lấy ra khỏi queue.
Còn biến last sẽ cho ta vị trí của phần tử cuối cùng ra khỏi queue.Và để thêm một phần tử x vào queue thì đơn giản ta thực hiện hai thao tác:
Thao tác 1: tăng last lên một vị trí (last++)
Thao tác 2: queue[last]=x
Như vậy ta có thao tác Push(yourtype x).
Và các bạn hình dung kĩ thì sẽ thấy khi ban đầu queue rỗng (first=-1;last=0;)
Và trong nhiều bài toán ta cần phải kiểm tra queue rỗng hay có phần tử. Đối với thao tác này các bạn có thể viết riêng.

Code:


int IsNull()
{
    if(first<=last) return0;
    return 1;
}


IsNull trả về 0 nếu queue không rỗng.
IsNull trả về 1 nếu queue rỗng.
Code chi tiết:

Code:


#include<stdio.h>
#include<conio.h>

#define maxN 100000

long int queue[maxN];
long int first,last;

void Init();
long int Pop();
void Push(long int x);
int IsNull();



int main()
{
   
   
   
    return 0;
}
void Init()
{
 last=0;
 first=-1;   
}
void IsNull()
{
 if(first<=last) return 0;   
 return 1;
}
long int Pop()
{
 long int x=queue[first];
 first++;
 return x;   
}
void Push(long int x)
{
    queue[++last]=x;
}



Cài đặt trên chỉ mang tính tham khảo, và khi cài đặt thuần thục rồi thì ta có thể cài đặt gọn hơn, không cần phải viết khá chi tiết các thao tác như vậy.