Trước tiên các bạn hãy ghi nhớ rằng hầu hết trong các cuộc phỏng vấn thì cấu trúc dữ liệu trong lập trình không thể bỏ qua. Và cụm từ Stack và Queue cũng được các PM nhắc tới. Cụm từ cấu trúc dữ liệu (Stack và Queue) các bạn cũng nghe cũng nhiều ở trường học ở công ty và ở đâu đó xung quanh về lĩnh vực tin học. Và các bạn cũng biết tầm quan trọng của cấu trúc dữ liệu nó như thế nào trong thực tế hay hay trước mắt mỗi lập trình viên. Hôm nay tôi sẽ gợi ý cho các bạn để lục lọi lại trí nhớ của bạn về Stack và Queue. Show Tham gia và đồng hành cùng mọi thành viên khác. Facebook: Cộng đồng lập trình javascript Facebook Cộng đồng giới thiệu bài viết, website, sản phẩm tăng traffic. 1 - Stack là gì?
Thật ra các bạn học theo định nghĩa này là tôi đoán gãy răng luôn. Khó hiểu và trừu tượng vl =]]. Để tôi nói theo cách hiểu của cá nhân tôi cho các bạn dễ hình dung. Cơ chế FILO dạng như là thằng nào đến sau mà ăn trước, bất công cho cuộc đời. Ví dụ, tôi có một chồng dĩa. Khi người rửa dĩa xong họ xếp lại một chồng, thằng nào rửa sau được xếp lên top và đương nhiên ông nào đến lấy dĩa để ăn buffet thì dĩa xếp top sử dụng.. Tôi thấy các định nghĩa này đi ngược với cuộc đời :D Bây giờ chúng ta đã biết cách Stack hoạt động, và cách triển khai nó trong JavaScript như thế nào thì các bạn cùng tôi xem đoạn code phía dưới. Những method cơ bản của stack đó chính là pop, push, peek. #1 class Stack {
constructor() {
this.stack = []
}
// đẩy các phẩn tử vào một mảng để tạo dữ liệu stack
push(element) {
this.stack.push(element)
}
// Xoá phần tử top của stack và trả về gia tri top
pop() {
if (this.isEmpty()) return 'Stack is empty!'
return this.stack.pop()
}
// Trả về giá trị top của stack
peek() {
if (this.isEmpty()) return 'Stack is empty'
return this.stack[this.stack.length - 1]
}
// check
isEmpty() {
return !this.stack.length
}
}Các bạn có thể check trên https://jsfiddle.net/ copy paste vào và check. 2 - Queue là gì?Mới nói Stack là bất công với cuộc đời, thì Queue cũng dạng xếp hàng như vậy nhưng nó trả lại sự công bằng cho cuộc đời =]]. và ở Stack thì có cụm từ thì ở Queue cũng vậy, đó là FIFO (First In First Out). Đợi trước ăn trước, or ăn trước về trước. Ví dụ: Xếp hàng ở các cửa hàng trà sữa vậy. Ai đến xếp trước thì ắn trước. Chứ ko phải như stack, xếp sau ăn trước. Có ngày phù mỏ: Giờ chúng ta xem cách triển khai nó như thế nào trong javascript. #2 class Queue {
constructor() {
this.queue = []
}
enqueue(element) {
this.queue.push(element)
}
dequeue() {
if (this.isEmpty()) return 'Queue is empty'
return this.queue.shift()
}
peek() {
if (this.isEmpty()) return 'Queue is empty'
return this.queue[0]
}
// helper method
isEmpty() {
return !this.queue.length
}
}Tượng tự cũng như Stack thôi. Chạy và check lại nhé devjs. 3 - Tóm lại.Nói chung các cấu trúc dữ liệu này rất quen thuộc hằng ngày trong các lập trình viên, vì hầu hết các thư viện bây giờ đã hỗ trợ tận răng với các câu trúc thế này thay vì chúng ta tự làm. Nhưng cấu trúc dữ liệu là một chủ đề rất quan trọng thường được hỏi trong các cuộc phỏng vấn của các công ty. Vì thế các bạn cần thật sự nắm kỹ những cụm từ này để có thể bước sâu hơn với những cụm từ cao hơn. Chúc các bạn thành công! Tham gia và đồng hành cùng mọi thành viên khác. Facebook: Cộng đồng lập trình javascript Facebook Cộng đồng giới thiệu bài viết, website, sản phẩm tăng traffic. Tài liệu tham khảo:https://stackoverflow.com/questions/1590247/how-do-you-implement-a-stack-and-a-queue-in-javascripthttps://morioh.com/p/37bd6912a1a7/what-are-stack-and-queue-in-javascript 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.  Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức. Để 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ệnTrong 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àiThự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ệnTrong 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ó.
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à StackChú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ậnNhư 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 !!! |
