Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Tìm các số chẵn lẻ bằng Queue và Stack
Trong hướng dẫn này mình sẽ viết một chương trình sử dụng Queue và Stack để lưu trữ các dữ liệu nhập vào từ bàn phím. Đây là một bài tập áp dụng các hàm cơ bản trong Queue và Stack.
Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue và Stack, các bạn có thể xem lại các bài trước mình đã hướng dẫn.
1. Đề bài và gợi ý cách thực hiện
Trong phần này chúng ta sẽ cùng nhau tìm hiểu để bài toán và gợi ý cách thực hiện bài toán như thế nào nhé.
Đề bài
Thực hiện một chương trình nhận dữ liệu từ bàn phím. Tạo cấu trúc Queue và Stack sau đó thêm các phần tử là số chẵn vào ngăn xếp Stack và các phần tử số lẻ vào hàng đợi Queue. Hiển thị danh sách ngăn xếp và hàng đợi ra màn hình.
Bài viết này được đăng tại [free tuts .net]
Gợi ý cách thực hiện
Trong bài toán này ta cần hai cấu trúc lưu trữ là Queue và Stack, vậy nên ta sẽ tạo cấu trúc và các hàm cơ bản của nó.
- Cấu trúc dữ liệu của Queue và Stack (danh sách kiên kết hoặc mảng một chiều).
- Hàm Push: thêm phần tử vào Stack.
- Hàm Pop: xóa phần tử khỏi Stack.
- Hàm PushQ: thêm phần tử vào Queue.
- Hàm PopQ: xóa phần tử khỏi Queue.
- Hàm Input: thêm phần tử chẵn vào Stack và phần tử lẻ vào Queue.
- Hàm Print: hiển thị danh sách Queue và Stack ra màn hình.
Trên đây là các hàm cần thiết cho bài toán, chúng ta không nên tạo các hàm không sử dụng trong bài toán, vì như vậy sẽ tốn thời gian và bộ nhớ. Ở các bài trước mình đã hướng dẫn các bạn thực hiện các hàm này rồi, các bạn có thể xem lại hoặc tham khảo code mình sẽ viết dưới đây.
2. Chương trình nhập xuất các số chẵn lẻ trong Queue và Stack
Chúng ta sẽ tạo lần lượt các hàm cần thiết theo như gợi ý ở trên, đầu tiên ta sẽ tạo cấu trúc dữ liệu cho Queue và Stack, trong phần này mình sử dụng mảng để cài đặt cho Stack và danh sách liên kết để cài đặt cho Queue.
/* khởi tạo biến toàn cục m */
#define m 100
/* khởi tạo cấu trúc Stack sử dụng mảng*/
struct stack
{
int data[m];
int top;
};
/* khởi tạo cấu trúc Queue sử dụng danh sách liên kết */
struct Queue
{
int Head,Tail;
int Data[m];
};Sau khi đã có cấu trúc dữ liệu của Stack, ta sẽ bắt đầu tạo hai hàm cơ bản nhất trong Stack đó chính là hàm Push() và hàm Pop() để thêm và lấy phần tử trong Stack.
/* hàm thêm phần tử vào Stack */
void Push(stack &a, int c)
{
if(a.top==m-1)
{
cout<<"\n Ngăn xếp Stack rỗng!!!";
exit(0);
}
else
{
a.data[++a.top]=c;
}
}
/* hàm xóa phần tử khỏi Stack */
int Pop(stack &a)
{
if(a.top==-1)
{
cout<<"\n Ngăn xếp Stack rỗng!!!";
return 0;
}
else
return a.data[a.top--];
}Tương tư như Stack, ta cũng sẽ tạo hai hàm PushQ() và hàm PopQ() để thêm và xóa các phần tử trong Queue. Kèm theo đó ta sẽ tạo thêm một hàm IsEmpty() để kiểm tra hàng đơi rỗng.
/* hàm thêm phần tử vào trong Queue */
void PushQ(Queue &q,int x)
{
int vt;
vt=(q.Tail+1)%m;
if(vt==q.Head)
{
cout<<"\n Hàng đợi đã đầy!!!";
exit(1);
}
else
{
q.Data[vt]=x;
q.Tail=vt;
}
}
/* hàm kiểm tra hàng đợi rỗng */
int IsEmpty(Queue &q)
{
return (q.Head==q.Tail?1:0);
}
/* hàm xóa phần tử khỏi hàng đợi */
int PopQ(Queue &q)
{
int vt;
int iteam;
while(!IsEmpty(q))
{
vt=(q.Head+1)%m;
iteam=q.Data[vt];
q.Head=vt;
return iteam;
}
return -1;
}Và cuối cùng là hàm Input() để thêm các phần tử là số chẵn vào Stack và các phần tử là số lẻ vào Queue. Ta sẽ sử dụng vòng lặp While để lặp hết các phần tử được nhập từ bàn phím, nếu là số chẵn thì ta Push nó vào Stack, nếu là số lẻ thì ta PushQ nó vào Queue.
/* hàm đưa phần tử vào Stack và Queue theo yêu cầu của bài toán
số chẵn vào Stakc và số lẻ vào Queue
*/
void Input(Queue &q, stack &p)
{
int x;
while(1)
{
cout<<"\n Nhập giá trị x, nhập -1 để thoát:";
cin>>x;
if(x==-1)break;
if(x%2==1)
{
PushQ(q,x);
}
else
{
Push(p,x);
}
}
}Như vậy là chúng ta đã viết xong hàm Input các phần tử vào hai cấu trúc dữ liệu, bây giờ chỉ cần sử dụng hàm Pop() và PopQ() để lấy các phần tử trong Stack và Queue ra để kiểm tra.
/* hàm in các phần tử trong Queue và Stack */
void Print(Queue &q, stack &p){
cout<<"Danh sách ngăn xếp Stack (các số chẵn): "<<"\n";
while(p.top!=-1)
{
cout<<Pop(p)<<" ";
}
cout<<"\n";
int t=PopQ(q);
cout<<"Danh sách hàng đợi Queue (các số lẻ): "<<"\n";
while(t!=-1)
{
cout<<t<<" ";
t=PopQ(q);
}
cout<<"\n";
}Các bạn có thể tham khảo chương trình hoàn chỉnh mình đã viết dưới đây.
Full code:
#include<iostream>
/* khởi tạo biến toàn cục m */
#define m 100
using namespace std;
/* khởi tạo cấu trúc Stack sử dụng mảng*/
struct stack
{
int data[m];
int top;
};
/* khởi tạo cấu trúc Queue sử dụng danh sách liên kết */
struct Queue
{
int Head,Tail;
int Data[m];
};
/* hàm thêm phần tử vào Stack */
void Push(stack &a, int c)
{
if(a.top==m-1)
{
cout<<"\n Ngăn xếp Stack rỗng!!!";
exit(0);
}
else
{
a.data[++a.top]=c;
}
}
/* hàm xóa phần tử khỏi Stack */
int Pop(stack &a)
{
if(a.top==-1)
{
cout<<"\n Ngăn xếp Stack rỗng!!!";
return 0;
}
else
return a.data[a.top--];
}
/* hàm thêm phần tử vào trong Queue */
void PushQ(Queue &q,int x)
{
int vt;
vt=(q.Tail+1)%m;
if(vt==q.Head)
{
cout<<"\n Hàng đợi đã đầy!!!";
exit(1);
}
else
{
q.Data[vt]=x;
q.Tail=vt;
}
}
/* hàm kiểm tra hàng đợi rỗng */
int IsEmpty(Queue &q)
{
return (q.Head==q.Tail?1:0);
}
/* hàm xóa phần tử khỏi hàng đợi */
int PopQ(Queue &q)
{
int vt;
int iteam;
while(!IsEmpty(q))
{
vt=(q.Head+1)%m;
iteam=q.Data[vt];
q.Head=vt;
return iteam;
}
return -1;
}
/* hàm đưa phần tử vào Stack và Queue theo yêu cầu của bài toán
số chẵn vào Stakc và số lẻ vào Queue
*/
void Input(Queue &q, stack &p)
{
int x;
while(1)
{
cout<<"\n Nhập giá trị x, nhập -1 để thoát:";
cin>>x;
if(x==-1)break;
if(x%2==1)
{
PushQ(q,x);
}
else
{
Push(p,x);
}
}
}
/* hàm in các phần tử trong Queue và Stack */
void Print(Queue &q, stack &p){
cout<<"Danh sách ngăn xếp Stack (các số chẵn): "<<"\n";
while(p.top!=-1)
{
cout<<Pop(p)<<" ";
}
cout<<"\n";
int t=PopQ(q);
cout<<"Danh sách hàng đợi Queue (các số lẻ): "<<"\n";
while(t!=-1)
{
cout<<t<<" ";
t=PopQ(q);
}
cout<<"\n";
}
/* hàm main để gọi các hàm đã viết */
int main()
{
stack p;
Queue q;
p.top=-1;
q.Head=q.Tail=0;
Input(q,p);
Print(q, p);
cout<<"\n-------------------------------\n";
cout<<"chương trình này được đăng tại Freetuts.net";
}Kết quả:
3. Kết luận
Như vậy là chúng ta đã thực hiện xong chương trình nhập xuất các số chẵn, lẻ trong Stack và Queue. Các bạn có thể áp dụng bài toán này để luyện tập với các thuật toán khác như số nguyên tố, số chính phương,... . Hãy luyện tập thật nhiều để thành thạo các cấu trúc dữ liệu này nhé, chúc các bạn thực hiện thành công !!!
