Thuat Toan RadixSort

Ý tưởng: 

 Thuật giải sắp xếp theo phương pháp cơ số không quan tâm đến việc so sánh giá trị
của các phần tử như các thuật giải trước. RadixSort sử dụng cách thức phân loại các con
số trong dãy và thứ tự phân loại con con số này để tạo ra thứ tự cho các phần tử. Đây là
cách tiếp cận khác so với các phương pháp sắp xếp trước là so sánh các giá trị của các
phần tử. Thuật giải dựa trên ý tưởng chính là sắp xếp từng con số của một dãy các số.

 Để sắp xếp dãy a[1], a[2],..., a[n] giải thuật RadixSort thực hiện như sau:
 Xem mỗi phần tử a[i] trong dãy a[1]...a[n] là một số nguyên có tối đa m chữ số
 Lần lượt phân loại các chữ số theo hàng đơn vị, hàng chục, hàng trăm...Tại mỗi
bước phân loại ta sẽ nối các dãy con từ danh sách đã phân loại theo thứ tự 0 ® 9.
Sau khi phân loại xong ở hàng thứ m cao nhất ta sẽ thu được danh sách các phần
tử được sắp.
Thuật toán :

Bước 1 : k = 0; // k là chữ số phân loại, k = 0 hàng đơn vị, k = 1 hàng chục...
 Bước 2 : // Tạo các dãy chứa phần tử phân loại B[0]...B[9]
Khởi tạo B[0]...B[9] rỗng, chưa chứa phần tử nào, B[i] sẽ chứa các phần tử có chữ
số thứ k là i.
 Bước 3 :
o For i=1 to n do
 Đặt a[i] vào dãy B[j] với j là chữ số thứ k của a[i].
o Nối B[0], B[1],..., B[9] lại theo đúng trình tự thành a.
 Bước 4 :
o k = k +1
o Nếu k < m: Þ Bước 2. // m là số lượng chữ số tối đa của các số
trong mảng
o Ngược lại: Þ Dừng.

 Mảng a[MAX] chứa các phần tử của mảng cần sắp tăng.
 Mảng B[10][MAX] chứa các dãy số được phân tạm thời theo các
con số. Ví dụ B[0] chứa các phần tử có con số ở hàng đơn vị .Khi đó với mỗi dòng của B thì sẽ phân các phần tử có con số ở hàng thứ i (i từ 0 - 9), các giá trị cột j sẽ lần lượt chứa các phần tử có cùng con số ở hàng thứ i.
 Mảng Len[10] chứa số lượng các phần tử của các dòng B[i].  Tại mỗi bước
trước khi phân các phần tử vào mảng B thì các Len[i] được khởi tạo là 0.
 Ví dụ : Cho dãy:



Phân lô theo hàng đơn vị:

12	0701
11	1725
10	0999
9	9170
8	3252
7	4518
6	7009
5	1424
4	0428
3	1239										0999
2	8425						1725			4518	7009
1	7013	9170	0701	3252	7013	1424	8425			0428	1239
CS	A	0	1	2	3	4	5	6	7	8	9
		Các lô B dùng để phân loại

Phân lô theo hàng chục:

12	0999
11	7009
10	1239
9	4518
8	0428
7	1725
6	8425
5	1424
4	7013			0428
3	3252			1725
2	0701	7009	4518	8425
1	9170	0701	7013	1424	1239		3252		9170		0999
CS	A	0	1	2	3	4	5	6	7	8	9

Phân lô theo hàng trăm:

12	0999
11	9170
10	3252
9	1239
8	0428
7	1725
6	8425
5	1424
4	4518
3						0428
2	7009	7013		3252		8425			1725
1	0701	7009	9170	1239		1424	4518		0701		0999
CS	A	0	1	2	3	4	5	6	7	8	9

Phân lô theo hàng ngàn:

12	0999
11	1725
10	0701
9	4518
8	0428
7	8425
6	1424
5	3252
4	1239
3	9170	0999	1725
2	7013	0701	1424						7013
1	7009	0428	1239		3252	4518			7009	8425	9170
CS	A	0	1	2	3	4	5	6	7	8	9

Lấy các phần tử từ các lô B0, B1, ., B9 nối lại thành a:

12	9170
11	8425
10	7013
9	7009
8	4518
7	3252
6	1725
5	1424
4	1239
3	0999
2	0701
1	0428
CS	A	0	1	2	3	4	5	6	7	8	9

Cài đặt:

void RadixSort(long a[], int n)

{

int i, j, d;

int h = 10; // biến để lấy các con số, bắt đầu từ hàng đơn vị

long B[10][MAX]; // mảng hai chiều chứa các phần tử phân lô

int Len[10]; // kích thước của từng mảng B[i]

// MAXDIGIT là số con số tối đa của các phần tử a[i]

for(d = 0; d < MAXDIGIT; d++)

{

// khởi tạo kích thước các dãy B[i] là 0

for( i = 0; i < 10; i++)

Len[i] = 0;

// thực hiện phân lô các phần tử theo con số hàng thứ d tính từ cuối

for(i = 0; i < n; i++) // duyệt qua tất cả các phần tử của mảng

{

digit = (a[i] % h) / (h/ 10); // lấy con số theo hàng h

// đưa vào dãy (lô) B[digit] ở cột Len[digit]

B[digit][Len[digit]++] = a[i];

}// end for i

// thực hiện nối lại tuần tự từ B[0] – đến B[9] vào mảng a[] ban đầu

num = 0; // chỉ số bắt đầu cho mảng a[]

for(i = 0; i < 10; i++) // duyệt qua các dãy từ B[0] – đến B[9]

{

// lấy từng phần tử của từng dãy B[i]

for(j =0; j < Len[i]; j++)

a[num++] = B[i][j];

}// end for i

h *= 10; // qua hàng kế tiếp.

}// end for d

}// end RadixSort

Thuat Toan QuickSort

Ý tưởng:

Đây là một phương pháp sắp xếp tốt do C.A.R Hoare đề xuất. Thuật toán này có
tốc độ trung bình nhanh hơn các thuật toán sắp xếp tổng quát khác. Do đó Hoare dùng
chữ “Quick” để đặt tên cho thuật toán này. Để sắp dãy a[1] ... a[n], ta thực hiện sắp xếp dãy a từ chỉ số 1 đến chỉ số n. QuickSort dựa trên phân hoạch dãy ban đầu thành hai phần dựa vào giá trị x, x là giá
trị của một phần tử tùy ý trong dãy ban đầu:
 Dãy thứ 1 : gồm các phần tử a[1]..a[i] có giá trị không lớn hơn x.
 Dãy thứ 2 : gồm các phần tử a[i]..a[n] có giá trị không nhỏ hơn x.
Sau khi phân hoạch thì dãy ban đầu được phân thành ba phần:
1. a[k] < x, với k = 1..i
2. a[k] = x, với k = i..j
3. a[k] > x, với k = j..n
Thuật toán :

 Bước 1 : Chọn tùy ý một phần tử a[k] trong dãy là giá trị mốc, left £ k £ right,
o Cho x = a[k], i = left, j = right.
 Bước 2 : Tìm và hoán vị cặp phần tử a[i] và a[j] không đúng thứ tự đang sắp.
o Bước 2-1 : Trong khi a[i] < x Þ i++;
o Bước 2-2 : Trong khi a[j] > x Þ j--;
o Bước 2-3 : Nếu i < j Þ Swap(a[i], a[j]) // a[i], a[j] sai thứ tự
 Bước 3 :
o Nếu i < j: Þ Bước 2; // chưa hết mảng dừng
o Nếu i ³ j: Þ Dừng.

Ví dụ : cho dãy : 6 , 5,  3 ,  1 ,  8 ,  7 ,  4

Ví dụ. Cho dãy: 1, 12, 5, 26, 7, 14, 3, 7, 2

Cài đặt:

void QuickSort(int a[], int left, int right)
{
int i, j;

int x;
x = a[(left+right)/2]; // chọn phần tử giữa làm gốc
i = left;
j = right;
do{
while (a[i] < x)
i++; // lặp đến khi a[i] >= x
while (a[j] > x)
j--; // lặp đến khi a[i] <= x
if ( i <= j) // nếu có 2 phần tử a[i] và a[j] ko theo thứ tự
{
Swap(a[i], a[j]);
i++; // qua phần tử kế tiếp
j--; // qua phần tử đứng trước
}
} while (i<j);
if (left < j) // phân hoạch đoạn bên trái
QuickSort(a, left, j);
if (right > i) // phân hoạch đoạn bên phải
QuickSort(a, i, right);
}

Thuat Toan ShellSort

Ý tưởng:
Trong phương pháp sắp xếp kiểu chèn nếu ta luôn phải chèn một khóa vào vị trí
đầu dãy thì dẫn đến hạn chế của thuật toán này. Để khắc phục trong trường hợp này thì
người ta đưa ra một phương pháp sắp xếp là ShellSort.
 Xét một dãy a[1]...a[n], cho một số nguyên h (1 £ h £ n), ta có thể chia
dãy đó thành h dãy con như sau:
 Dãy con 1 : a[1], a[1+ h], a[1+2h]...
 Dãy con 2 : a[2], a[2+h], a[2+2h]...
 Dãy con 3 : a[3], a[3+h], a[3+2h]...
 ...
 Dãy con h : a[h], a[2h], a[3h]...
Thuật toán :
 Bước 1 : chọn k khoảng cách h[1], h[2],.., h[k], và i = 1.
 Bước 2 : Chia dãy ban đầu thành các dãy con có bước nhảy là h[i]. Thực hiện sắp xếp
từng dãy con bằng phương pháp chèn trực tiếp.
 Bước 3 : i = i+1
o Nếu i > k: Þ Dừng

o Ngược lại: Þ Bước 2.
Ví dụ: cho dãy : 6,5,3,2, 8, 7, 1, 4

Cài đặt ShellSort: sắp xếp dãy a[] tăng, với h[] là mảng chứa các độ dài (bước nhảy) đãchọn sẵn:

void ShellSort(int a[], int n, int h[], int k)
{
     int step, i, j;
     int x, len;
    for(step = 0; step < k; step++) // duyệt qua từng bước nhảy
       {
          len = h[step]; // chiều dài của bước nhảy
         for(i = len; i < n; i++) // duyệt các dãy con
             {    // lưu phần tử cuối để tìm vị trí thích hợp trong dãy con
              x = a[i];  // a[j] đứng trước a[i] trong cùng dãy con
               j = i – len;
                 while ((x < a[j]) && (j>= 0))
                  // sắp xếp dãy con chứa x dùng pp chèn
                    {
                           a[j+len] = a[j]; // dời về sau theo dãy con
                          j = j – len; // qua phần tử trước trong dãy con
                    }
             a[j+len] = x;// đưa x vào vị trí thích hợp trong dãy con
             }
         }
}

Thuat Toan InterchangeSsort

Ý tưởng:
 Ý tưởng chính của giải thuật là xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế. Lặp lại xử lý trên với các phần tử tiếp theo trong dãy. Các bước tiến hành như sau :
Thuật toán:
* Bước 1 : i = 1;// bắt đầu từ đầu dãy
* Bước 2 : j = i+1;//tìm các phần tử a[j] < a[i], j>i
* Bước 3 :
Trong khi j < N thực hiện
Nếu a[j]<a[i]:a[i]=a[j]// hoán vị (a[i] a[j])
j = j+1;
* Bước 4 : i = i+1;
Nếu i < n: Lặp lại Bước 2.
Ngược lại: Dừng.

* Ví dụ: Cho dãy số a: 12    2    8    5    1    6    4    15

Cài đặt:

Cài đặt thuật toán sắp xếp theo kiểu đổi chỗ trực tiếp thành hàm InterchangeSort:

void InterchangeSort(int a[], int N )

{

int i, j;

for (i = 0 ; i<N-1 ; i++)

for (j =i+1; j < N ; j++)

if(a[j ]< a[i]) // nếu có sự sai vị trí thì đổi chỗ

Hoanvi(a[i],a[j]);

}

Thuat Toan InsertionSort

Ý tưởng:
Giả sử có dãy a0, a1,…,ai-1 đã được sắp xếp. Ý tưởng của thuật toán là chèn thêm phần tử mới ai vào vị trí thích hợp của đoạn a1…ai-1 sao cho được dãy mới a1…ai đã được sắp xếp
Nguyên tắc sắp xếp như sau: đoạn gồm phần tử a0 đã được sắp xếp, thêm a1 vào được a0,a1 đã được sắp xếp, tiếp tục thêm a2 vào được a0, a1, a2 đã sắp xếp…tiếp tục để thêm an vào để được a0,a1,…,an đã sắp xếp.

Thuật toán:
Đầu vào: n – số phần tử mảng
a – mảng chứa các phần tử bất kỳ
Đầu ra: a- mảng đã được sắp xếp tăng dần
Bước 1: i=1 //giả sử a[0] đã được sắp xếp
Bước 2: tìm vị trí pos thích hợp trong đoạn từ a[0] đến a[i-1] để chèn a[i] vào
Bước 3: đổi chỗ các phần tử từ a[pos] đến a[i-1] sang phải một vị trí để được vị trí chèn a[i] vào
Bước 4: chèn a[i] vào vị trí pos tìm được bằng cách gán a[pos]=a[i]
Bước 5: i=i+1
Nếu i lặp lại bước 2
Ngược lại => Dừng thuật toán

Ví dụ: Cho dãy số a = 12 , 2 , 8 , 5 , 1 ,  6 , 4 , 15
Mô tả các bước chạy khi thực hiện thuật toán với dãy trên :
i=1 => Cần chèn phần tử a[1] vào dãy a[0] => pos=-1
Vi tri so pos=pos+1

i=2 => Cần chèn phần tử a[2] vào dãy a[0],a[1] => pos=1

i=3 => Cần chèn phần tử a[3] vào dãy a[0],a[1],a[2]=> pos = 1

i=4 => Cần chèn phần tử a[4] vào dãy a[0],a[1],a[2],a[3] => pos = 0

i=5 => Cần chèn phần tử a[5] vào dãy a[0],a[1],a[2],a[3],a[4] => pos = 3

i=6 => Cần chèn phần tử a[6] vào dãy a[0],a[1],a[2],a[3],a[4],a[5] => vi tri 2

i=7 => Cần chèn phần tử a[7] vào dãy a[0],a[1],a[2],a[3],a[4],a[5],a[6] => pos = 7

=> dừng
Vậy dãy đã sắp xếp là a = 1 2 4 5 6 8 12 15


Cài đặt:
void InsertionSort(float a[],int n)
{
 float temp;
 for(int i=2;i<=n;i++)
  {
   temp=a[i];
   int vt=i;
   while ((a[vt-1]>temp)&&(vt>1))
    {
     a[vt]=a[vt-1];
     vt=vt-1;
    }
   a[vt]=temp;
  }
}

Thuat Toan BubbleSort

Ý tưởng:
Sắp xếp nổi bọt (tiếng Anh: bubble sort) là một thuật toán sắp xếp đơn giản, với thao tác cơ bản là so sánh hai phần tử kề nhau, nếu chúng chưa đứng đúng thứ tự thì đổi chỗ (swap). Có thể tiến hành từ trên xuống (bên trái sang) hoặc từ dưới lên (bên phải sang). Sắp xếp nổi bọt còn có tên là sắp xếp bằng so sánh trực tiếp. Nó sử dụng phép so sánh các phần tử nên là một giải thuật sắp xếp kiểu so sánh.
Thuật toán:

Bước 1 : i = 1; // xuất phát từ đầu dãy
 Bước 2 : j = i+1; // tìm các phần tử phía sau i
 Bước 3 :
o While j £ n do
 Nếu a[j]< a[i] Þ Swap(a[i], a[j]);
 j = j+1;
 Bước 4 : i = i+1;
o Nếu i < n: Þ Bước 2
o Ngược lại Þ Kết thúc


Ví dụ:  Cho dãy : 6 , 5 , 3 , 1 , 8 , 7 , 2 , 4

Ví dụ : Cho dãy 5, 1, 12, -5, 16

Ví dụ: Cho dãy :6 , 5 , 3 , 1 , 8 , 7 , 2 , 4

................................................................

Ví dụ: Cho dãy : 3 , 1 , 2 , 4

Cài dặt:
void BubbleSort(float a[],int n)
{
 float temp;
 for(int i=1;i<n;i++)
 for(int j=n;j>i;j--)
 if(a[j]<a[j-1])
  {
   temp=a[j];
   a[j]=a[j-1];
   a[j-1]=temp;
  }
}

Thuat Toan SelectionSort

Ý tưởng :
Chọn phần tử nhỏ nhất trong n phần tử ban đầu, đưa phần tử này về vị trí đúng là đầu tiên của dãy hiện hành. Sau đó không quan tâm đến nó nữa, xem dãy hiện hành chỉ còn n-1 phần tử của dãy ban đầu, bắt đầu từ vị trí thứ 2. Lặp lại quá trình trên cho dãy hiện hành đến khi dãy hiện hành chỉ còn 1 phần tử. Dãy ban đầu có n phần tử, vậy tóm tắt ý tưởng thuật toán là thực hiện n-1 lượt việc đưa phần tử nhỏ nhất trong dãy hiện hành về vị trí đúng ở đầu dãy.
Thuật giải:
Bước 1: i=1
Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] đến a[n]
Bước 3: Hoán vị a[min] và a[i]
Bước 4: Nếu i<=n-1 thì i=i+1; Lặp lại bước 2
Ngược lại: Dừng. n-1 phần tử đã nằm đúng vị trí.
Ví dụ: Cho dãy a = (12,2,8,5,1,6,4,15)
12 2 8 5 1 6 4 15
Bước 1: 1 2 8 5 12 6 4 15
Bước 2: 1 2 8 5 12 6 4 15
Bước 3: 1 2 4 5 12 6 8 15
Bước 4: 1 2 4 5 12 6 8 15
Bước 5: 1 2 4 5 6 12 8 15
Bước 6: 1 2 4 5 6 8 12 15
Bước 7: 1 2 4 5 6 8 12 15

Ví dụ. Cho dãy: {5, 1, 12, -5, 16, 2, 12, 14}

Cài đặt:
Void SelectionSort(int a[], int n)
{
   int min;
   for(int i=0;i<n-1;i++)
   {
      min=i;
      for(int j=i+1;j<n;j++)
         if(a[j]<a[min]) min=j;
      HoanVi(a[min],a[i]);
   }
}

Hang Doi Mua Ve

// Hang Doi Mua Ve.cpp : Defines the entry point for the console application.
// So nguoi mua ve duoc bieu dien ban ky tu A B C D ...
// Nguoi dau tien la A, sau moi 1s thi ban  ve duoc 1 nguoi
#include "stdafx.h"                                                                                          
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<dos.h>
#include <windows.h>
// Ham gotoxy (lenh:gotoxy(x,y), thu vien:windows.h)
   void gotoxy(short x, short y)
   {
     HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
      COORD pos;
      pos.X=x-1;
     pos.Y=y-1;
    SetConsoleCursorPosition(hCon, pos);
  }
void sleep( clock_t wait )
{
clock_t goal;
goal = wait + clock();
while( goal > clock() )
;
}
//KHOI TAO DSLK QUEUE
struct tagnode{
        char Data;
        struct tagnode *next;
};
typedef tagnode *node;
typedef struct taglist{
        node head;
        node tail;
}linkedlist;
typedef linkedlist Queue;
void initQueue(Queue &q){
        q.head=q.tail=NULL;
}
int isempty(Queue q)   //kiem tra q rong hay khong
{
        return(q.head==NULL);
}
void enQueue(Queue &q,char x)   //them x vao cuoi q
{   node p= new tagnode;
        if(p==NULL) return;
        p->Data=x;
        p->next=NULL;
        if(isempty(q)){
                  q.head=q.tail=p;
                }
        else
                {        q.tail->next=p;
                  q.tail=p;
                }
}
void deQueue(Queue &q)  //xoa phan tu dau cua q
{   node p=q.head;
        if(isempty(q))
                return;
        q.head=p->next;
        if(q.head==NULL)
                q.tail=NULL;
        p->next=NULL;
        delete p;
}
void insertQueue(Queue &q,int n) //nhap phan tu cua q(nhap nguoi mua ve)
{   char j=65;
           initQueue(q);
           for(int i=0;i<n;i++)
                enQueue(q,j++);
}

void drawQueue(int x,int y)   //ve phong cho mua ve
{   int i,j;
           for(i=0;i<4;i++)
          if(i==0 || i==3)
                   for(j=0;j<16;j++)
                   {     gotoxy(x+j,y+i);
                         putchar(196);
                   }
          else
                   for(j=0;j<17;j+=3)
                   {     gotoxy(x+j,y+i);
                         putchar(221);
                   }
}
void putoutQueue(Queue q,int x,int y)   //in hang doi mua ve xem phim ra man hinh
{   node p=q.head;
        int i=1;    
        gotoxy(20,1);
        printf(" \n MO PHONG HANG DOI MUA VE XEM PHIM \n");
        drawQueue(x,y);
        if(isempty(q))
                return;
        else
                while(p)
                {          gotoxy(x+i,y+2);
                   putchar(p->Data);
                   p=p->next;
                   i+=3;
               }
}
void out_Queue(Queue q,int n) //quan ly so nguoi cho mua ve
{   int x=29,y=4;
           insertQueue(q,n);
           putoutQueue(q,x,y);
           gotoxy(25,10);
       
           sleep(4000);
           for(int i=0;i<n;i++)
           {     deQueue(q);
                 putoutQueue(q,x,y);
                 if(i!=(n-1))
                 {        gotoxy(25,10);
                  printf("\n Con %d nguoi cho mua ve",((n-1)-i));
                 }
                 else
                 {      gotoxy(33,10);
               
                 }
                sleep(2000);
           }
}
//HAM MAIN
void main()
{   Queue q;int n, m ,k;
   
        printf("\n Nhap so nguoi muon mua ve: ");
           scanf("%d",&m);
printf("\n Nhap so  ve: ");
scanf("%d",&k);
if(k<=m)
{
n=k;
printf("\n Ban het ve");
out_Queue(q,n);
   printf("\n Con %d nguoi chua co ve", m-k);
}
else
{
n=m;
printf("\n Tat ca deu co ve !");
out_Queue(q,n);
printf("\n Con thua %d ve :",k-m );
}
        getch();
}

Nhap Xuat Them Xoa Hang Doi

// HangDoi.cpp : Defines the entry point for the console application.
//


#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>
struct Queue
{
   int  info;
   struct Queue *next;
};
typedef struct Queue *QUEUE;

//Khai Bao Prototype
void InitializeQ (QUEUE *pfirst, QUEUE *plast);
int  EmptyQ (QUEUE *pfirst);
QUEUE GetQueue();
void PushQ (QUEUE *pfirst, QUEUE *plast, int x);
int  PopQ (QUEUE *pfirst, QUEUE *plast);
void TopQ (QUEUE *pfirst);
//==============================
void main()
{
   QUEUE pfirst, plast;
   int x, y, vt, chon, n, i;
   char ch;
   InitializeQ (&pfirst, &plast);
   do
   {
   
      printf("\n\n\t CHUONG TRINH DEMO HANG DOI THAO TAC TREN DAY NGUYEN !");
      printf("\n\t1  : Khoi Tao Hang Doi !");
      printf("\n\t2  : Kiem Tra Hang Doi Rong !");
      printf("\n\t3  : Tao Hang Doi !");
      printf("\n\t4  : Xuat Va Huy Hang Hoi  !");
      printf("\n\t5  : Them 1 Phan Tu Vao Hang Doi !");
      printf("\n\t6  : Xoa 1 PTu Ra Khoi hang Doi !");
      printf("\n\t7  : Truy Xuat Noi Dung O Dinh Hang Doi !");
      printf("\n\t0  : THOAT KHOI CHUONG TRINH !");
      printf("\n\tBan Chon Chuc Nang Nao ? ");
      scanf ("%d", &chon);
      switch (chon)
      {
         case 1:
         {
            InitializeQ (&pfirst, &plast);
            printf("\n\t Hang Doi Da Duoc Khoi Tao !");
            getch();
            break;
         }
         case 2:
         {
            printf("\n\t Kiem Tra Hang Doi Rong !");
            if (EmptyQ (&pfirst))
               printf("\n\t Hang Doi Rong !");
            else
               printf("\n\t Hang Doi Khong Rong !");
            getch();
            break;
         }
         case 3:
         {
            printf("\n\t Tao Hang Doi !");
            InitializeQ (&pfirst, &plast);
            printf("\n\t Nhap SPTu Trong Hang Doi !");
            scanf ("%d", &n);
            printf("\n\t Tao Hang Doi !");
            for (i = 1; i <= n; i++)
            {
               printf("\t\t\n Nhap PTu Thu %d  :  ", i);
               scanf("%d", &x);
               //Neu La Cau Truc : x = Nhap1PTu();
               PushQ(&pfirst, &plast, x);
            }
            getch();
            break;
         }
         case 4:
         {
            printf("\n\t Xuat Va Huy Hang Doi !");
            if (EmptyQ (&pfirst))
               printf("\n\t Hang Doi Rong  !");
            else
            {
               printf("\n\t Noi Dung Hang Doi Vua Nhap !");
               while(EmptyQ (&pfirst) == 0)
               {
                  TopQ (&pfirst);
                  y = PopQ (&pfirst, &plast);
               }
            }
            getch();
            break;
         }
         case 5:
         {
            printf("\n\t Them 1 PTu Vao Hang Doi !");
            printf("\n\t Nhap Noi Dung X Can Them :  ");
            scanf ("%d", &x);
            PushQ(&pfirst, &plast, x);
            getch();
            break;
         }
         case 6:
         {
            printf("\n\t Xoa PTu Dinh !");
            y = PopQ (&pfirst, &plast);
            getch();
            break;
         }
         case 7:
         {
            printf("\n\t Truy Xuat Noi Dung PTu Dinh !");
            TopQ (&pfirst);
            getch();
            break;
         }
      }//KT Switch
   }while (chon > 0);
   getch();
}//KThuc Ham Main
//==============================
//Cai Dat Cac Prototype
//======================================
void InitializeQ (QUEUE *pfirst, QUEUE *plast)
{
   *pfirst = *plast = NULL;
}
//========================================
int  EmptyQ (QUEUE *pfirst)
{
   if (*pfirst == NULL)
      return 1; //Rong
   return 0; //Khong Rong
}
//========================================
QUEUE Getnode()//Cap Phat Vung Nho
{
   QUEUE p;
   p = (QUEUE) malloc (sizeof (struct Queue));
   p -> next = NULL;
   return p;
}
//========================================
int  PopQ (QUEUE *pfirst, QUEUE *plast)
{
   QUEUE p;
   int x;
   if (EmptyQ(pfirst))
      printf("\n\t DS Rong, Khong Xoa Duoc !");
   else
   {
      p = *pfirst;
      x = p -> info;
      if (p -> next == NULL) //DS Co 1 Phan Tu
         *pfirst = *plast = NULL;
      else
         *pfirst = p -> next;
      return x;
   }
}
//========================================
void PushQ (QUEUE *pfirst, QUEUE *plast, int x)
{
   QUEUE p;
   p = Getnode();
   p -> info = x;
   p -> next = NULL;
   if (EmptyQ (pfirst))
   {
      *pfirst = p;
      *plast = *pfirst;
   }
   else
   {
      (*plast) -> next = p;
      *plast = p;
   }
}
//========================================
void TopQ (QUEUE *pfirst)
{
   if (EmptyQ (pfirst))
      printf("\n\t Hang Doi Rong !");
   else
   {
      printf("%5d", (*pfirst) -> info);
      //Neu La Cau Truc In1PTu
   }

}