О (n) ашыкча орун колдонбостон, стекти тескери буруңуз.


Кыйынчылык деңгээли жеңил
Көп суралган Factset Infosys MAQ
Байланышкан тизме чөмөлө

Маселени билдирүү

"O (n) 'де ашыкча орун колдонбостон стекти артка кайтаруу" маселеси сизге a берилгендигин билдирет чөмөлө маалыматтардын структурасы. Берилген стекти кошумча O (n) боштукту колдонбостон тескери буруңуз.

О (n) ашыкча орун колдонбостон, стекти тескери буруңуз.

мисал

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

O (n) ашыкча орун колдонбостон, стекти кайтаруу алгоритми

  1. Бүтүн өзгөрмөнү жана кийинки көрсөткүчтү камтыган класс түйүнүн түзүү. Кабыл алган класс конструкторун түзүңүз бүтүн параметр катары. Параметрдин маанисин бүтүн өзгөрмөгө ыйгарып, кийинки көрсөткүчтү конструктордо нөл деп белгилеңиз.
  2. Андан кийин, класс түзүү чөмөлө жана андагы типтеги түйүндүн көрсөткүчүнүн үстүн инициализациялаңыз.
  3. Бүтүн санды параметр катары кабыл алган push () функциясын түзүңүз. Top нөлгө барабар экендигин текшерип, бүтүндөй сандын жаңы түйүнүн маалымат катары түзүңүз жана жаңы түйүндү жогору жагына сактап, кайра кайтыңыз.
  4. Башкасы жаңы түйүн түзөт s маалымат катары берилген бүтүн сан менен. Кийинкилердин жаңыртуусу s жана барабар s деп барабар.
  5. Ошо сыяктуу эле, pop () функциясын түзүңүз. Жаңы түйүндөрдү түзүп, анын чокусун сактап коюңуз. Жогору жакты кийинки жаңыртып, жаңы түйүндөрдү кайтарыңыз.
  6. Андан кийин reverse () функциясын жаратыңыз. Мурунку, учурдагы жана ийгиликтүү көрсөтүлгөн үч түйүндү түзүңүз. Учурдагы жана мурунку түйүндү жогорку түйүн катары жаңыртыңыз.
  7. Учурдагы түйүндү учурдагы түйүндүн кийинки катары, ал эми кийинки түйүндү нөл катары жаңыртыңыз.
  8. Учурдагы түйүн нөл болбогондо, кийинки түйүндү учурдагы түйүндүн, учурдагы түйүндүн прессиос түйүнү катары, мурунку түйүндү учурдагы түйүн жана учурдагы түйүндү кийинки түйүн катары жаңыртыңыз.
  9. Мурунку түйүн сыяктуу жогорку түйүндү жаңыртыңыз.
  10. Акыры, тескери стекти көрсөтүү үчүн, дисплей функциясын () түзүңүз. Жаңы түйүндөрдү түзүп, анын чокусун сактап коюңуз. 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

O (n) ашыкча орун колдонбостон, стекти артка кайтаруу үчүн Java программасы

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 - маалымат структурасынын стегиндеги элементтердин саны. Стектин элементтеринин үстүнөн чуркап өтүү үчүн бирден цикл колдондук. Убакыттын татаалдыгы сызыктуу.

Космостун татаалдыгы

O (1) анткени биз туруктуу кошумча мейкиндикти колдонуп жатабыз. Киргизүүнү сактоо үчүн алынган орун алгоритм үчүн эсептелбейт. Ошентип космостогу татаалдык туруктуу. Бирок программа жалпысынан сызыктуу космостук татаалдыкты талап кылат.