#include <iostream>
#include <queue>
#include <stack>
#include <cctype> // for tolower
#include <string>
using namespace std;

#define SIZE 5

// -------------------------
// Circular Queue Class
// -------------------------
class CircularQueue {
private:
    int items[SIZE], front, rear;

public:
    CircularQueue() {
        front = -1;
        rear = -1;
    }

    bool isFull() {
        return (front == 0 && rear == SIZE - 1) || (rear == (front - 1 + SIZE) % SIZE);
    }

    bool isEmpty() {
        return front == -1;
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is Full\n";
            return;
        }

        if (front == -1) {
            front = rear = 0;
        } else if (rear == SIZE - 1 && front != 0) {
            rear = 0;
        } else {
            rear++;
        }

        items[rear] = value;
    }

    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is Empty\n";
            return;
        }

        cout << "Removed element: " << items[front] << endl;

        if (front == rear) {
            front = -1;
            rear = -1;
        } else if (front == SIZE - 1) {
            front = 0;
        } else {
            front++;
        }
    }

    void display() {
        if (isEmpty()) {
            cout << "Queue is Empty\n";
            return;
        }

        cout << "Queue elements: ";
        if (rear >= front) {
            for (int i = front; i <= rear; i++)
                cout << items[i] << " ";
        } else {
            for (int i = front; i < SIZE; i++)
                cout << items[i] << " ";
            for (int i = 0; i <= rear; i++)
                cout << items[i] << " ";
        }
        cout << endl;
    }
};

// -------------------------
// Palindrome Checker Function
// -------------------------
void checkPalindrome(const string& input) {
    // Reject input with spaces
    if (input.find(' ') != string::npos) {
        cout << "Please enter only one word without spaces.\n";
        return;
    }

    stack<char> s;
    queue<char> q;

    // Insert characters into stack and queue
    for (char c : input) {
        char lower = tolower(c); // تحويل الحرف إلى صغير
        s.push(lower);
        q.push(lower);
    }

    bool isPalindrome = true;
    while (!s.empty()) {
        if (s.top() != q.front()) {
            isPalindrome = false;
            break;  // إذا حدث اختلاف، لا داعي لاستكمال المقارنة
        }
        s.pop();
        q.pop();
    }

    if (isPalindrome)
        cout << "Palindrome\n";
    else
        cout << "Not palindrome\n";
}

// -------------------------
// Main
// -------------------------
int main() {
    // ------------------------
    // Test Circular Queue
    // ------------------------
    CircularQueue cq;
    cq.enqueue(10);
    cq.enqueue(20);
    cq.enqueue(30);
    cq.enqueue(40);
    cq.enqueue(50);
    cq.display();
    cq.dequeue();
    cq.enqueue(60);
    cq.display();

    // ------------------------
    // Palindrome Check
    // ------------------------
    string word;
    cout << "\nEnter a word to check if it's a palindrome: ";
    cin.ignore(); // مهم علشان نتفادى مشكلة getline بعد cin
    getline(cin, word);

    checkPalindrome(word);

    return 0;
}