#include <iostream>
using namespace std;

template <class T>
struct Node {
    T data;
    Node<T> *next = NULL;
};

template <class T>
struct Stack {
    Node<T> *top = NULL;
    int size = 0;
};

template <class T>
bool isEmptyStack(Stack<T> *s) {
    return (s->size == 0);
}

template <class T>
void push(Stack<T> *&s, T newData) {
    Node<T> *newNode = new Node<T>;
    newNode->data = newData;
    newNode->next = s->top;
    s->top = newNode;
    s->size += 1;
    return;
}

template <class T>
bool pop(Stack<T> *&s, T &dataOut) {
    if (isEmptyStack(s)) return false;
    dataOut = s->top->data;
    Node<T> *temp = s->top;
    s->top = temp->next;
    s->size -= 1;
    delete temp; temp = NULL;
    return true;
}

template <class T>
void printStack(Stack<T> *s) {
    Node<T> *temp = s->top;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}

template <class T>
void freeMemoryStack(Stack<T> *&s) {
    Node<T> *temp = s->top;
    while (temp != NULL) {
        Node<T> *next = temp->next;
        delete temp;
        temp = next;
    }
    s->top = NULL;
    s->size = 0;
}

template <class T>
struct Queue {
    Node<T> *front = NULL;
    Node<T> *rear = NULL;
    int size = 0;
};

template <class T>
bool isEmptyQueue(Queue<T> *q) {
    return (q->size == 0);
}

template <class T>
void enqueue(Queue<T> *q, T newData) {
    Node<T> *newNode = new Node<T>;
    newNode->data = newData;
    if (isEmptyQueue(q)) {
        q->front = newNode;
    }
    else q->rear->next = newNode;
    q->rear = newNode;
    q->size += 1;
    return;
}

template <class T>
bool dequeue(Queue<T> *q, T &dataOut) {
    if (isEmptyQueue(q)) return false;
    dataOut = q->front->data;
    Node<T> *temp = q->front;
    if (q->size == 1) q->rear = NULL;
    q->front = temp->next;
    q->size -= 1;
    delete temp; temp = NULL;
    return true;
}

template <class T>
void printQueue(Queue<T> *q) {
    if (isEmptyQueue(q)) return;
    Node<T> *temp = q->front;
    while (temp != NULL) {
        cout << temp->data << endl;
        temp = temp->next;
    }
    cout << endl;
}

template <class T>
void freeMemoryQueue(Queue<T> *&q) {
    Node<T> *temp = q->front;
    while (temp != NULL) {
        Node<T> *next = temp->next;
        delete temp;
        temp = next;
    }
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}


void Sort(Stack<int> *&stack) {
    Queue<int> *queue = new Queue<int>;
    int sizeStack = stack->size;
    int valueStack;
    for (int i = 0; i < sizeStack; i++) {
        pop(stack, valueStack);
        int sizeQueue = queue->size;
        int valueQueue;
        for (int j = 0; j < sizeQueue; j++) {
            dequeue(queue, valueQueue);
            if (valueStack < valueQueue) {
                enqueue(queue, valueStack);
                valueStack = valueQueue;
            }
            else {
                enqueue(queue, valueQueue);
            }

        }
        enqueue(queue, valueStack);
    }
    while (!isEmptyQueue(queue)) {
        int value;
        dequeue(queue, value);
        push(stack, value);
    }
    delete queue; queue = NULL;
}

int main() {
    const int n = 6;
    int arr[n] = { 23,78,45,8,32,56 };
    Stack<int> *stack = new Stack<int>;
    for (int i = 0; i < n; i++) {
        push(stack, arr[i]);
    }
    cout << "Danh sach ban dau: ";
    printStack(stack);

    Sort(stack);
    cout << "Danh sach sau khi sap xep: ";
    printStack(stack);

    freeMemoryStack(stack);
    delete stack; stack = NULL;

    system("pause");
    return 0;
}