HÀNG ĐỢI QUEUE
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

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.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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.

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ả:

queue baitap PNG

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 !!!

Cùng chuyên mục:

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Tìm kiếm phần tử k trong danh sách liên kết đôi

Tìm kiếm phần tử k trong danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu cách tìm kiếm một phần tử k trong…

Top