Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ค้นหาค่าสูงสุดของ stack ใน O(1) โดยไม่ต้องใช้ stack เพิ่มเติมใน C++


สมมติว่าเราต้องการสร้างสแต็กที่สามารถเก็บองค์ประกอบสูงสุดไว้ในสแต็กได้ และเราสามารถทำได้ในเวลา O(1) ข้อจำกัดคือ ไม่ควรใช้พื้นที่เพิ่มเติม ดังนั้น O(1) พื้นที่เพิ่มเติม

เราสามารถสร้างสแต็กที่กำหนดโดยผู้ใช้ได้หนึ่งอัน ซึ่งจะเก็บค่าสูงสุดไว้ เมื่อดำเนินการอย่างใดอย่างหนึ่ง เช่น ป๊อปหรือแอบดู ค่าสูงสุดจะถูกส่งคืน สำหรับการดูข้อมูล ให้คืนค่าสูงสุดของ stack top และ max element สำหรับการทำงานแบบ pop เมื่อองค์ประกอบด้านบนมีขนาดใหญ่ขึ้น จากนั้นพิมพ์และอัปเดต max เป็น 2*max – top_element มิฉะนั้นให้ส่งคืน top_element สำหรับการดำเนินการแบบพุชให้อัปเดตองค์ประกอบสูงสุดเป็น x (ข้อมูลที่จะแทรก) 2*x – สูงสุด

ตัวอย่าง

#include <iostream>
#include <stack>
using namespace std;
class CustomStack {
   stack<int> stk;
   int stack_max;
   public:
   void getMax() {
      if (stk.empty())
         cout << "Stack is empty"<<endl;
      else
         cout << "Maximum Element in the stack is: "<< stack_max <<endl;
   }
   void peek() {
      if (stk.empty()) {
         cout << "Stack is empty ";
         return;
      }
      int top = stk.top(); // Top element.
      cout << "Top Most Element is: "<<endl;
      (top > stack_max) ? cout << stack_max : cout << top;
   }
   void pop() {
      if (stk.empty()) {
         cout << "Stack is empty"<<endl;
         return;
      }
      cout << "Top Most Element Removed: ";
      int top = stk.top();
      stk.pop();
      if (top > stack_max) {
         cout << stack_max <<endl;
         stack_max = 2 * stack_max - top;
      } else
         cout << top <<endl;
   }
   void push(int element) {
      if (stk.empty()) {
         stack_max = element;
         stk.push(element);
         cout << "Element Inserted: " << element <<endl;
         return;
      }
      if (element > stack_max) {
         stk.push(2 * element - stack_max);
         stack_max = element;
      } else
      stk.push(element);
      cout << "Element Inserted: " << element <<endl;
   }
};
int main() {
   CustomStack stk;
   stk.push(4);
   stk.push(6);
   stk.getMax();
   stk.push(8);
   stk.push(20);
   stk.getMax();
   stk.pop();
   stk.getMax();
   stk.pop();
   stk.peek();
}

ผลลัพธ์

Element Inserted: 4
Element Inserted: 6
Maximum Element in the stack is: 6
Element Inserted: 8
Element Inserted: 20
Maximum Element in the stack is: 20
Top Most Element Removed: 20
Maximum Element in the stack is: 8
Top Most Element Removed: 8
Top Most Element is:
6