ປະຕິບັດຂັ້ນຕອນໂດຍໃຊ້ແຖວດຽວ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ສີ່ພັນ ກູໂກ Infosys MAQ Microsoft
ຄິວ Stack

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

ບັນຫາ“ ປະຕິບັດຂັ້ນຕອນໂດຍໃຊ້ແຖວດຽວ” ຂໍໃຫ້ພວກເຮົາຈັດຕັ້ງໂຄງສ້າງຂໍ້ມູນ (LIFO) ໂດຍໃຊ້ໂຄງປະກອບຂໍ້ມູນແຖວ (FIFO).

ນີ້ແມ່ນ LIFO ໝາຍ ຄວາມວ່າ First In First Out ໃນຂະນະທີ່ FIFO ໝາຍ ຄວາມວ່າ First First First.

ປະຕິບັດຂັ້ນຕອນໂດຍໃຊ້ແຖວດຽວ

ຍົກຕົວຢ່າງ

push(10)
push(20)
top()
pop()
push(30)
pop()
top()
Top : 20
Pop : 20
Pop : 30
Top : 10
push(1)
push(2)
top()
pop()
Top : 2
Pop : 2

ຄໍາອະທິບາຍ

ໃຫ້ພວກເຮົາສົມມຸດວ່າພວກເຮົາມີແຖວ, ແລະຕອນນີ້ພວກເຮົາເລີ່ມຕົ້ນເພີ່ມອົງປະກອບເຂົ້າໃນມັນ. ສະນັ້ນ ສຳ ລັບການເພີ່ມຫລືໃສ່ອົງປະກອບຕ່າງໆເຂົ້າໃນນັ້ນ. ພວກເຮົາຈະໂທຫາ ການທໍາງານຂອງການຊຸກຍູ້.

ຍູ້ (1) —————> ປັດຈຸບັນແຖວຄິວ -> 1

ຍູ້ (2) —————> ປັດຈຸບັນແຖວຄິວ -> 2,1

ສຳ ລັບການເຮັດສິ່ງນີ້, ພວກເຮົາຈະ ກຳ ຈັດອົງປະກອບທັງ ໝົດ ທີ່ຢູ່ໃນແຖວກ່ອນ ໜ້າ ນີ້. ຫຼັງຈາກນັ້ນ, ພວກເຮົາໃສ່ອົງປະກອບ ໃໝ່ ຂອງພວກເຮົາໄວ້ໃນແຖວທີ່ຫວ່າງ. ຫລັງຈາກນັ້ນພວກເຮົາກະຕຸ້ນອົງປະກອບທີ່ຖືກຍ້າຍອອກໄປໃນລະບຽບດຽວກັນ.

ເບິ່ງດ້ານເທິງ / ດ້ານ ໜ້າ ຂອງແຖວ, ດັ່ງນັ້ນຈຶ່ງເຮັດໃຫ້ພວກເຮົາມີ 2 ອັນດັບ.

q.top () = 2

ໃຫ້ພວກເຮົາເອົາອົງປະກອບອັນດັບ ໜຶ່ງ ອອກ. ດັ່ງນັ້ນພວກເຮົາ ກຳ ລັງເອົາ 2 ຄົນອອກຈາກແຖວ.

ສະນັ້ນຫຼັງຈາກການປົດ ຕຳ ແໜ່ງ, ສະພາບຂອງແຖວໃນປະຈຸບັນ = 1.

ສູດການຄິດໄລ່ເພື່ອຈັດຕັ້ງປະຕິບັດຂັ້ນຕອນໂດຍໃຊ້ແຖວດຽວ

  1. ເລີ່ມຕົ້ນຂັ້ນຫ້ອງຮຽນດ້ວຍ a ຄິວ ໂຄງສ້າງຂໍ້ມູນຂອງ integer ພິມເປັນສະມາຊິກສ່ວນຕົວ. ພວກເຮົາຍັງ ກຳ ນົດ ຊຸກຍູ້, ປpopອບອັບ, ດ້ານເທິງ, ແລະ ຫວ່າງເປົ່າ ຍ້ອນວ່າມັນເປັນ ໜ້າ ທີ່ສະມາຊິກຂອງລັດ.
  2. ສ້າງ ໜ້າ ທີ່ໃຫ້ຫວ່າງ (). ກັບມາເປັນຄວາມຈິງຖ້າຄິວຢູ່ຫວ່າງແລ້ວກໍ່ກັບມາບໍ່ຖືກຕ້ອງ.
  3. push () ຍອມຮັບມູນຄ່າເລກເຕັມ. ສ້າງຕົວແປຕົວເລກແລະເກັບຮັກສາຂະ ໜາດ ຂອງແຖວໄວ້ໃນຕົວແປແລະກົດ / ໃສ່ຕົວແປເລກເຕັມໃນແຖວ.
  4. Traverse ຈາກ 0 ກັບຂະຫນາດທີ່ຜ່ານມາຂອງແຖວ. ສືບຕໍ່ເອົາແຖວ ໜ້າ ຂອງຄິວໃນປະຈຸບັນມາໃສ່ຕົວມັນເອງແລະຖອດມັນອອກ.
  5. ສ້າງ pop ໜ້າ ທີ່ () ທີ່ກວດເບິ່ງວ່າບໍ່ມີອົງປະກອບໃດຢູ່ໃນແຖວຫຼັງຈາກນັ້ນພິມ“ ບໍ່ມີອົງປະກອບ” ແລະກັບຄືນ -1. ອື່ນ pop / ເອົາອົງປະກອບດ້ານເທິງ / ທາງຫນ້າ.
  6. ພວກເຮົາສ້າງ ໜ້າ ທີ່ດ້ານເທິງ () ເຊິ່ງກັບຄືນ -1 ຖ້າບໍ່ມີອົງປະກອບໃດຢູ່ໃນແຖວອື່ນກໍ່ຈະສົ່ງຄືນ ໜ້າ ແຖວ.

ລະຫັດ

ໂຄງການ C ++ ເພື່ອຈັດຕັ້ງປະຕິບັດຂັ້ນໄດໂດຍໃຊ້ແຖວດຽວ

#include<bits/stdc++.h> 
using namespace std; 
  
class Stack{ 
    queue<int>q;
    
public: 
    void push(int val); 
    int pop(); 
    int top(); 
    bool empty(); 
}; 
  
void Stack::push(int val){ 
    int s = q.size(); 
  
    q.push(val); 
  
    for(int i=0; i<s; i++){ 
        q.push(q.front()); 
        q.pop(); 
    } 
} 
  
int Stack::pop(){ 
    if(q.empty()){ 
        cout<<"No elements\n";
        return -1;
    }    
    else{
        int x = q.front();
        q.pop();
        return x;
    }  
} 
  
int  Stack::top(){ 
    return (q.empty())? -1 : q.front(); 
} 
  
bool Stack::empty(){ 
    return (q.empty()); 
} 
  
int main(){ 
    Stack s;
    
    s.push(10); 
    s.push(20); 
    cout<<"Top : "<<s.top()<<endl; 
    cout<<"Pop : "<<s.pop()<<endl; 
    s.push(30); 
    cout<<"Pop : "<<s.pop()<<endl;
    cout<<"Top : "<<s.top()<<endl; 

    return 0; 
}
Top : 20
Pop : 20
Pop : 30
Top : 10

Java Program ເພື່ອປະຕິບັດຂັ້ນຕອນໂດຍໃຊ້ແຖວດຽວ

import java.util.LinkedList; 
import java.util.Queue; 
  
class stack{ 
    Queue<Integer> q = new LinkedList<Integer>(); 
      
    void push(int val){ 
        int size = q.size(); 
          
        q.add(val); 
          
        for(int i=0; i<size; i++){ 
            int x = q.remove(); 
            q.add(x); 
        } 
    } 
      
    int pop(){ 
        if (q.isEmpty()){ 
            System.out.println("No elements"); 
            return -1; 
        } 
        int x = q.remove(); 
        return x; 
    } 
      
    int top(){ 
        if (q.isEmpty()) 
            return -1; 
        return q.peek(); 
    } 
      
    boolean isEmpty(){ 
        return q.isEmpty(); 
    } 
  
    public static void main(String[] args){ 
        stack s = new stack(); 
        
        s.push(10); 
        s.push(20); 
        System.out.println("Top : " + s.top()); 
        System.out.println("Pop : " + s.pop()); 
        s.push(30); 
        System.out.println("Pop : " + s.pop()); 
        System.out.println("Top : " + s.top());
        
    } 
}
Top : 20
Pop : 20
Pop : 30
Top : 10

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

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

push () ໜ້າ ທີ່ ກຳ ລັງ ດຳ ເນີນຢູ່ O (n) ທີ່ໃຊ້ເວລາໃນຂະນະທີ່ pop () ແລະ top () ຟັງຊັນຮຽກຮ້ອງໃຫ້ມີເວລາຄົງທີ່ເທົ່ານັ້ນ O (1). ເນື່ອງຈາກວ່າ ສຳ ລັບການຊຸກຍູ້ອົງປະກອບ ໜຶ່ງ ພວກເຮົາ ກຳ ຈັດແລະເພີ່ມ ຈຳ ນວນຂອງອົງປະກອບທີ່ມີຢູ່ໃນນັ້ນ. ນີ້ເຮັດໃຫ້ການປະຕິບັດງານທີ່ຈະດໍາເນີນການໃນເວລາທີ່ມີ polynomial.

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

O (n) ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງໃຊ້ພື້ນທີ່ໃນການເກັບຮັກສາ ຈຳ ນວນຂອງອົງປະກອບ.