Tạo queue bằng danh sách liên kết đơn

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   main.cpp
 * Author: KHOA
 *
 * Created on August 26, 2016, 9:10 AM
 */

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

struct Node {
    int data;
    Node *next;
};

struct List {
    Node *head;
    Node *tail;
};

// khoi tao queue

void Init(List &q) {
    q.head = q.tail = NULL; // gan con tro head va tail cua queue bang NULL
}

// tao Node trong queue

Node *creat_Node(int x) {
    Node *p = new Node;
    if (p != NULL) {
        p->data = x; // dua gia tri cua x vao trong data
        p->next = NULL; // gan phan tu ke tiep bang NULL
        return p; // tra ve con tro p trong queue
    } else {
        return NULL; // neu cap phat khong thanh cong thi tra ve NULL
    }

}

// kiem tra xem queue co rong khong

bool isEmpty(List &q) {
    Node *p = q.head;
    if (p == NULL) return true; // neu phan tu dau bang NULL thi queue rong
    else return false; // neu khong thi khong phai rong
}

// push Node vao trong queue

void push(List &q, int x) {
    Node *r = creat_Node(x);
    if (isEmpty(q)) q.head = q.tail = r;
    else {
        r->next = q.head; // đưa phần tử mới vào trỏ tới next là phần tử đầu
        q.head = r; // cập nhật phần tử mới đưa vào đó là phần tử đầu
    }
}

// pop Node ra khoi queue

void pop(List &q) {
    Node *p = q.head;
    while (p->next->next != NULL) { // tim vi tri phan tu thu 2 tu duoi len
        p = p->next;
    }
    // p la phan tu o vi tri 2 tu duoi len
    Node *r = p->next; // r la phan tu cuoi cung cua queue
    p->next = NULL;
    delete r; // xoa phan tu r
}

// nhap phan tu vao trong queue

void nhap(List &q) {
    int n;
    cout << "Nhap so luong Node trong queue: ";
    cin>>n;
    for (int i = 1; i <= n; i++) {
        int x;
        cout << "Phan tu thu " << i << ": ";
        cin>>x;
        push(q, x); // dua phan tu vao trong queue
    }
}

// xuat cac phan tu ra man hinh

void xuat(List &q) {
    Node *p = q.head;
    while (p != NULL) {
        cout << " " << p->data;
        p = p->next;
    }
}

// tim Node trong queue

Node *search_Node(List &q, int x) {
    Node *p = q.head;
    while (!isEmpty(q)) {
        if (p->data == x) return p; // tra ve con tro p khi tim thay phan tu trong queue
        else p = p->next; // khong thi tim tiep
    }
    return NULL; // neu khong tim duoc tra ve NULL
}

int main() {
    List q;
    Init(q);
    nhap(q);
    xuat(q);
    int lc, x;

    do {
        cout << "\n _ _ _CHUONG TRINH QUEUE_ _ _"
                << "\n 1. Push queue "
                << "\n 2. Pop queue "
                << "\n 3. Tim phan tu trong queue "
                << "\n 0. Thoat ";
        cout << endl;
        cout << "Nhap lua chon: ";
        cin>>lc;
        switch (lc) {
            case 1:
            {
                cout << "Nhap phan tu can push: ";
                cin>>x;
                push(q, x);
                break;
            }
            case 2:
            {
                cout << "Ban da dua 1 phan tu ra khoi queue! ";
                pop(q);
                break;
            }
            case 3:
            {
                cout << "Nhap phan tu can tim kiem: ";
                cin>>x;
                if (search_Node(q, x) != NULL) cout << "Tim thay phan tu trong queue! ";
                else cout << "Khong tim thay phan tu do trong queue! ";
            }
            case 0: break;
        }
        xuat(q);
        cout << "\n";
    } while (lc != 0);

    return 0;
}