സിംഗിൾ ക്യൂ ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് നടപ്പിലാക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫോർകൈറ്റുകൾ ഗൂഗിൾ ഇൻഫോസിസ് MAQ മൈക്രോസോഫ്റ്റ്
വരി കൂനകൂട്ടുക

പ്രശ്നം പ്രസ്താവന

“സിംഗിൾ ക്യൂ ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് നടപ്പിലാക്കുക” എന്ന പ്രശ്നം ഒരു ക്യൂ (ഫിഫോ) ഡാറ്റാ ഘടന ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് (ലിഫോ) ഡാറ്റാ ഘടന നടപ്പിലാക്കാൻ ആവശ്യപ്പെടുന്നു.

ഇവിടെ LIFO എന്നാൽ അവസാനത്തെ ഫസ്റ്റ് Out ട്ട് എന്നാൽ FIFO എന്നാൽ ഫസ്റ്റ് ഇൻ ഫസ്റ്റ് .ട്ട് എന്നാണ് അർത്ഥമാക്കുന്നത്.

സിംഗിൾ ക്യൂ ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് നടപ്പിലാക്കുക

ഉദാഹരണം

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

വിശദീകരണം

നമുക്ക് ഒരു ക്യൂ ഉണ്ടെന്ന് കരുതുക, ഇപ്പോൾ ഞങ്ങൾ അതിൽ ഘടകങ്ങൾ ചേർക്കാൻ ആരംഭിക്കുന്നു. അതിനാൽ ഘടകങ്ങൾ ചേർക്കുന്നതിനോ ചേർക്കുന്നതിനോ. ഞങ്ങൾ വിളിക്കും പുഷ് ഫംഗ്ഷൻ.

push (1) —————> ക്യൂവിന്റെ നിലവിലെ അവസ്ഥ -> 1

push (2) —————> ക്യൂവിന്റെ നിലവിലെ അവസ്ഥ -> 2,1

ഇത് ചെയ്യുന്നതിന്, മുമ്പ് ക്യൂവിലുള്ള എല്ലാ ഘടകങ്ങളും ഞങ്ങൾ നീക്കംചെയ്യും. തുടർന്ന് ഞങ്ങളുടെ പുതിയ ഘടകം ശൂന്യമായ ക്യൂവിൽ ചേർക്കുന്നു. നീക്കംചെയ്ത ഘടകങ്ങളെ അതേ ക്രമത്തിൽ ഞങ്ങൾ വീണ്ടും തള്ളുന്നു.

ക്യൂവിന്റെ മുകളിൽ / മുൻവശത്തേക്ക് നോക്കുന്നത് ഫലമായി 2 നൽകുന്നു.

q.top () = 2

മുകളിലെ ഘടകം നീക്കംചെയ്യാം. അതിനാൽ ഞങ്ങൾ 2 ക്യൂവിൽ നിന്ന് നീക്കംചെയ്യുന്നു.

അതിനാൽ നീക്കം ചെയ്തതിനുശേഷം, ക്യൂവിന്റെ നിലവിലെ അവസ്ഥ = 1.

സിംഗിൾ ക്യൂ ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് നടപ്പിലാക്കാനുള്ള അൽഗോരിതം

  1. A ഉപയോഗിച്ച് ക്ലാസ് സ്റ്റാക്ക് സമാരംഭിക്കുക വരി ന്റെ ഡാറ്റ ഘടന പൂർണ്ണസംഖ്യ ഒരു സ്വകാര്യ അംഗമായി ടൈപ്പുചെയ്യുക. ഞങ്ങൾ നിർവചിക്കുന്നു പുഷ്, പോപ്പ്, ടോപ്പ്, ഒപ്പം ശൂന്യമാണ് ഇത് പബ്ലിക് മെംബർ ഫംഗ്ഷനുകൾ ആയതിനാൽ.
  2. ശൂന്യമായ പ്രവർത്തനം സൃഷ്ടിക്കുക (). ക്യൂ ശൂന്യമാണെങ്കിൽ‌ തെറ്റായി മടങ്ങുക.
  3. പുഷ് () ഒരു സംഖ്യ മൂല്യം സ്വീകരിക്കുന്നു. ഒരു ഇൻറിജർ വേരിയബിൾ സൃഷ്ടിച്ച് ക്യൂവിന്റെ വലുപ്പം വേരിയബിളിൽ സംഭരിച്ച് ക്യൂവിൽ ഇൻറിജർ വേരിയബിൾ പുഷ് / തിരുകുക.
  4. 0 മുതൽ ക്യൂവിലെ മുമ്പത്തെ വലുപ്പം വരെ സഞ്ചരിക്കുക. ക്യൂവിന്റെ നിലവിലെ മുൻ‌ഭാഗം സ്വയം ചേർത്ത് നീക്കംചെയ്യുന്നത് തുടരുക.
  5. ക്യൂവിൽ ഒരു ഘടകവുമില്ലേ എന്ന് പരിശോധിക്കുന്ന പോപ്പ് () ഫംഗ്ഷൻ സൃഷ്ടിക്കുക, തുടർന്ന് “ഘടകങ്ങളൊന്നുമില്ല” അച്ചടിച്ച് -1 മടങ്ങുക. ടോപ്പ് / ഫ്രണ്ട് എലമെൻറ് പോപ്പ് ചെയ്യുക / നീക്കംചെയ്യുക.
  6. ക്യൂവിൽ ഒരു ഘടകവും ഇല്ലെങ്കിൽ -1 മടക്കിനൽകുന്ന ഫംഗ്ഷൻ ടോപ്പ് () ഞങ്ങൾ സൃഷ്ടിക്കുന്നു.

കോഡ്

സിംഗിൾ ക്യൂ ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് നടപ്പിലാക്കുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

#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

സിംഗിൾ ക്യൂ ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് നടപ്പിലാക്കുന്നതിനുള്ള ജാവ പ്രോഗ്രാം

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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

പുഷ് () ഫംഗ്ഷൻ എടുക്കുന്നു O (n) പോപ്പ് (), ടോപ്പ് () ഫംഗ്ഷനുകൾക്ക് സ്ഥിരമായ സമയം മാത്രം ആവശ്യമാണ് O (1). കാരണം ഒരു മൂലകം തള്ളുന്നതിനായി ഞങ്ങൾ ഇതിനകം തന്നെ അതിൽ ഉണ്ടായിരുന്ന ഘടകങ്ങളുടെ എണ്ണം നീക്കം ചെയ്യുകയും ചേർക്കുകയും ചെയ്യുന്നു. ഇത് പോളിനോമിയൽ സമയത്ത് പ്രവർത്തിക്കാൻ സഹായിക്കുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) കാരണം n ഘടകങ്ങളുടെ എണ്ണം സംഭരിക്കാൻ ഞങ്ങൾ സ്ഥലം ഉപയോഗിക്കുന്നു.