ປີ້ນກັບກະເປົາໂດຍບໍ່ໃຊ້ພື້ນທີ່ພິເສດໃນ O (n)


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ປັດໃຈ Infosys MAQ
ບັນຊີທີ່ເຊື່ອມໂຍງ Stack

ຖະແຫຼງການບັນຫາ

ບັນຫາ“ ປີ້ນກັບກັນໂດຍບໍ່ໃຊ້ພື້ນທີ່ພິເສດໃນ O (n)” ລະບຸວ່າທ່ານຖືກກ stack ໂຄງສ້າງຂໍ້ມູນ. ດ້ານກົງກັນຂ້າມທີ່ມອບໃຫ້ໂດຍບໍ່ຕ້ອງໃຊ້ພື້ນທີ່ເພີ່ມເຕີມ O (n).

ປີ້ນກັບກະເປົາໂດຍບໍ່ໃຊ້ພື້ນທີ່ພິເສດໃນ O (n)

ຍົກຕົວຢ່າງ

5 4 3 2 1
1 2 3 4 5
80 60 10 20
20 10 60 80

ສູດການຄິດໄລ່ເພື່ອປີ້ນກັບກະເປົາໂດຍບໍ່ຕ້ອງໃຊ້ພື້ນທີ່ພິເສດໃນ O (n)

  1. ສ້າງ node class ທີ່ມີຕົວເລກ integer ແລະຕົວຊີ້ຕໍ່ໄປ. ສ້າງຜູ້ສ້າງຫ້ອງຮຽນທີ່ຍອມຮັບເອົາ integer ເປັນພາລາມິເຕີ. ມອບຄ່າພາລາມິເຕີໃຫ້ກັບຕົວແປຕົວເລກແລະ ກຳ ນົດຕົວຊີ້ຕໍ່ໄປເປັນ null ໃນຜູ້ສ້າງ.
  2. ຫລັງຈາກນັ້ນ, ສ້າງຫ້ອງຮຽນ stack ແລະເລີ່ມຕົ້ນຈຸດເທິງຂອງຕົວຊີ້ປະເພດຢູ່ໃນນັ້ນ.
  3. ສ້າງຕົວຊຸກຍູ້ການເຮັດວຽກ () ທີ່ຍອມຮັບເລກເຕັມເປັນພາລາມິເຕີ. ກວດເບິ່ງວ່າດ້ານເທິງເທົ່າກັບ null ສ້າງ node ໃໝ່ ທີ່ມີຕົວເລກທີ່ໃຫ້ໄວ້ເປັນຂໍ້ມູນແລະເກັບຂໍ້ມູນ ໃໝ່ ຢູ່ເທິງແລະກັບຄືນ.
  4. ອື່ນສ້າງ node ໃຫມ່ s ດ້ວຍ ຈຳ ນວນທີ່ຖືກມອບໃຫ້ເປັນຂໍ້ມູນ. ປັບປຸງຕໍ່ໄປຂອງ s ເປັນທາງເທີງແລະທາງເທິງແມ່ນເທົ່າກັບ s.
  5. ເຊັ່ນດຽວກັນ, ສ້າງ pop ໜ້າ ທີ່ (). ສ້າງ node ໃຫມ່ແລະເກັບຮັກສາທາງເທິງໃນນັ້ນ. ປັບປຸງ ໃໝ່ ເປັນອັນດັບຕໍ່ໄປແລະສົ່ງຄືນ node s ໃໝ່.
  6. ຫລັງຈາກນັ້ນ, ສ້າງ ໜ້າ ທີ່ປີ້ນກັບກັນ (). ສ້າງສາມຂໍ້ທີ່ເປັນຕົວແທນຂອງປະຈຸບັນ, ປັດຈຸບັນແລະປະສົບຜົນ ສຳ ເລັດຕາມ ລຳ ດັບ. ອັບເດດ node ປັດຈຸບັນແລະກ່ອນ ໜ້າ ນີ້ເປັນ node ຊັ້ນ ນຳ.
  7. ປັບປຸງ node ປັດຈຸບັນເປັນ node ຕໍ່ໄປແລະ node ຕໍ່ໄປເປັນ null.
  8. ໃນຂະນະທີ່ node ປັດຈຸບັນບໍ່ແມ່ນ null, ປັບປຸງ node ທີ່ປະສົບຜົນ ສຳ ເລັດເປັນ node ຕໍ່ໄປ, node ຕໍ່ໄປຄື node previos, node ກ່ອນ ໜ້າ ນີ້ເປັນ node ແລະ node ປະຈຸບັນເປັນ node ທີ່ປະສົບຜົນ ສຳ ເລັດ.
  9. ອັບເດດ node ເທິງເປັນ node ທີ່ຜ່ານມາ.
  10. ສຸດທ້າຍສ້າງການສະແດງ ໜ້າ ທີ່ () ເພື່ອສະແດງ stack ທີ່ປ່ຽນຄືນ. ສ້າງ node ໃຫມ່ແລະເກັບຮັກສາທາງເທິງໃນນັ້ນ. ໃນຂະນະທີ່ s ບໍ່ເທົ່າກັບ null, ພິມຂໍ້ມູນຂອງ s ແລະປັບປຸງ s ເປັນ ໜ້າ ຕໍ່ໄປຂອງ s.

ລະຫັດ

ໂຄງການ C ++ ເພື່ອປີ້ນກັບກະເປົາໂດຍບໍ່ຕ້ອງໃຊ້ພື້ນທີ່ພິເສດໃນ O (n)

#include<bits/stdc++.h> 
using namespace std; 
  
class Node { 
    public: 
        int data; 
        Node *next; 
          
        Node(int data){ 
            this->data = data; 
            this->next = NULL; 
        } 
}; 
  
class Stack{ 
      
    Node *top; 
      
    public: 
      
        void push(int data){ 
            if (top == NULL) { 
                top = new Node(data); 
                return; 
            } 
            Node *s = new Node(data); 
            s->next = top; 
            top = s; 
        } 
          
        Node* pop(){ 
            Node *s = top; 
            top = top->next; 
            return s; 
        } 
      
        void display(){ 
            Node *s = top; 
            while (s != NULL) { 
                cout << s->data << " "; 
                s = s->next; 
            } 
            cout << endl; 
        } 
      
        void reverse(){ 
            Node *prev, *cur, *succ; 
            cur = prev = top; 
            cur = cur->next; 
            prev->next = NULL; 
            while (cur != NULL) { 
                succ = cur->next; 
                cur->next = prev; 
                prev = cur; 
                cur = succ; 
            } 
            top = prev; 
        } 
}; 
  
int main(){ 
    Stack *s = new Stack(); 
    
    s->push(1); 
    s->push(2); 
    s->push(3); 
    s->push(4);
    s->push(5);
    
    s->reverse(); 
  
    s->display(); 
      
    return 0; 
}
1 2 3 4 5

Java Program ເພື່ອປີ້ນກັບກັນ stack ໂດຍບໍ່ຕ້ອງໃຊ້ພື້ນທີ່ພິເສດໃນ O (n)

class Node{ 
    int data; 
    Node next; 
    
    public Node(int data){ 
        this.data = data; 
        this.next = null; 
    } 
} 
  
class Stack{ 
    Node top; 
  
    public void push(int data){ 
        if (this.top == null){ 
            top = new Node(data); 
            return; 
        } 
        
        Node s = new Node(data); 
        s.next = this.top; 
        this.top = s; 
    } 
    
    public Node pop(){ 
        Node s = this.top; 
        this.top = this.top.next; 
        return s; 
    } 
  
    public void display(){ 
        Node s = this.top; 
        
        while (s != null){ 
            System.out.print(s.data + " "); 
            s = s.next; 
        } 
        
    } 
  
    public void reverse(){
        
        Node prev, cur, succ; 
        
        cur = prev = this.top; 
        cur = cur.next; 
        prev.next = null; 
        
        while(cur != null){ 
            succ = cur.next; 
            cur.next = prev; 
            prev = cur; 
            cur = succ; 
        } 
        
        this.top = prev; 
    } 
} 
  
class reverseStack{ 
    
    public static void main(String[] args){ 
        
        Stack s = new Stack(); 
        
        s.push(1); 
        s.push(2); 
        s.push(3); 
        s.push(4);
        s.push(5);
        
        s.reverse(); 
  
        s.display(); 
    } 
}
1 2 3 4 5

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

O (n) ບ່ອນທີ່ n ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນໂຄງສ້າງຂໍ້ມູນ. ເນື່ອງຈາກວ່າພວກເຮົາໄດ້ໃຊ້ວົງແຫວນດຽວເພື່ອແລ່ນຜ່ານອົງປະກອບຂອງ stack. ຄວາມສັບສົນຂອງເວລາແມ່ນເປັນເສັ້ນ.

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງໃຊ້ພື້ນທີ່ເພີ່ມເຕີມທີ່ຄົງທີ່. ເນື່ອງຈາກວ່າພື້ນທີ່ໃຊ້ໃນການເກັບຮັກສາວັດສະດຸປ້ອນເຂົ້າຈະບໍ່ຖືກນັບເຂົ້າໃນຂັ້ນຕອນການຄິດໄລ່. ດັ່ງນັ້ນຄວາມສັບສົນໃນພື້ນທີ່ແມ່ນຄົງທີ່. ແຕ່ໂປແກຼມລວມທັງ ໝົດ ຕ້ອງການຄວາມສັບສົນໃນອະວະກາດ.