O'rta element ustida operatsiyalar bilan stekni loyihalash o (1) vaqt murakkabligida

O'rta element ustida operatsiyalar bilan stekni loyihalash
O (1) vaqt murakkabligida quyidagi operatsiyalarni qo'llab-quvvatlaydigan stekni qanday amalga oshirish kerak ? 
1) stekning yuqori qismiga element qo'shadigan push(). 
2) stek tepasidan elementni olib tashlaydigan pop(). 
3) stekning o'rta elementini qaytaradigan findMiddle(). 
4) o'rta elementni o'chiradigan deleteMiddle(). 
Push va pop - bu standart stek operatsiyalari.
1-usul:
Muhim savol: stekni amalga oshirish uchun bog'langan ro'yxat yoki massivdan foydalanish kerakmi? 
Iltimos, biz o'rta elementni topishimiz va o'chirishimiz kerakligini unutmang. Elementni o'rtasidan o'chirish massiv uchun O (1) emas. Bundan tashqari, biz elementni bosganimizda o'rta ko'rsatgichni yuqoriga va ochilganda () pastga siljitishimiz kerak bo'lishi mumkin. Yagona bog'langan ro'yxatda o'rta ko'rsatgichni har ikki tomonga siljitish mumkin emas. 
G'oya ikki tomonlama bog'langan ro'yxat (DLL) dan foydalanishdir. O'rta ko'rsatkichni saqlab, O (1) vaqtida o'rta elementni o'chirishimiz mumkin. Oldingi va keyingi ko'rsatkichlar yordamida o'rta ko'rsatkichni ikkala yo'nalishda ham siljitishimiz mumkin. 
Quyida push(), pop() va findMiddle() operatsiyalari amalga oshiriladi. Agar stekda hatto elementlar bo'lsa, findMiddle() ikkinchi o'rta elementni qaytaradi. Misol uchun, agar stekda {1, 2, 3, 4} bo'lsa, findMiddle() 3 ni qaytaradi.

/* C++ Program to implement a stack that supports findMiddle() and deleteMiddle in O(1) time */ #include using namespace std; class myStack { struct Node { int num; Node* next; Node* prev; Node(int num) { this->num = num; } }; // Members of stack Node* head = NULL; Node* mid = NULL; int size = 0; public: void push(int data) { Node* temp = new Node(data); if (size == 0) { head = temp; mid = temp; size++; return; } head->next = temp; temp->prev = head; // update the pointers head = head->next; if (size % 2 == 1) { mid = mid->next; } size++; } int pop() { int data=-1; if (size != 0) { data=head->num; if (size == 1) { head = NULL; mid = NULL; } else { head = head->prev; head->next = NULL; if (size % 2 == 0) { mid = mid->prev; } } size--; } return data; } int findMiddle() { if (size == 0) { return -1; } return mid->num; } void deleteMiddle() { if (size != 0) { if (size == 1) { head = NULL; mid = NULL; } else if (size == 2) { head = head->prev; mid = mid->prev; head->next = NULL; } else { mid->next->prev = mid->prev; mid->prev->next = mid->next; if (size % 2 == 0) { mid = mid->prev; } else { mid = mid->next; } } size--; } } }; int main() { myStack st; st.push(11); st.push(22); st.push(33); st.push(44); st.push(55); st.push(66); st.push(77); st.push(88); st.push(99); cout <<"Popped : "<< st.pop() << endl; cout <<"Popped : "<< st.pop() << endl; cout <<"Middle Element : "<< st.findMiddle() << endl; st.deleteMiddle(); cout <<"New Middle Element : "<< st.findMiddle() << endl; return 0; } // This code is contributed by Nikhil Goswami // Updated by Amsavarthan LV