დანერგეთ სტეკი და რიგი Deque– ს გამოყენებით


Რთული ტური Easy
ხშირად ეკითხებიან ფანატიკა GE Healthcare MAQ მიტრა Qualcomm
დიქეიკი Queue დასტის

პრობლემის განცხადება

პრობლემა "დანერგეთ დასტისა და რიგის გამოყენებით დეკის გამოყენებით" აცხადებს ალგორითმის დაწერას სტეკისა და რიგის განსახორციელებლად Deque (ორმაგად დასრულებული რიგის) გამოყენებით.

მაგალითი (დასტის)

Push(1)
Push(2)
Push(3)
Pop()
isEmpty()
Pop()
Size()
3
false
2
1

მაგალითი (რიგი)

Enqueue(1)
Enqueue(2)
Enqueue(3)
Dequeue
isEmpty()
Size()
Dequeue()
1
false
2
2

 

ალგორითმი

A დეკი(ორმაგად დასრულებული რიგი) რიგის სპეციალური ტიპია, რომელშიც ჩასმა და წაშლა შეიძლება შესრულდეს ორივე ბოლოზე. Deque- ს ეს საინტერესო თვისება შეიძლება გამოყენებულ იქნას როგორც სტეკის, ისე მისგან რიგის განსახორციელებლად.
ქვემოთ მოცემულ სურათზე ნაჩვენებია Deque,

დანერგეთ სტეკი და რიგი Deque– ს გამოყენებით

დასტის

დასტის არის Last In First Out (LIFO) მონაცემთა სტრუქტურა, ანუ ელემენტები გამოდის იმავე მხრიდან, სადაც ისინი აიძულა. მოდით გამოვიყენოთ Deque– ს წინა მხარე სტეკისთვის ბიძგების და პოპ – ოპერაციის შესასრულებლად.

ბიძგი (x)

X ელემენტის დასტისკენ გასატანად, უბრალოდ დაამატეთ x ელემენტი Deque- ს წინა მხარეს.

დროის სირთულე = O (1)

პოპი ()

პოპ ოპერაცია ხდება იმავე მხარეს, როგორც Push, ანუ სტეკიდან ელემენტის ამოსვლა წაშალეთ ელემენტის წინ მდებარე ელემენტი და დააბრუნეთ იგი.

დროის სირთულე = O (1)

ცარიელია()

თუ Deque ცარიელია, სტეკი ცარიელია, ეს ასე არ არის. ასე რომ, დააბრუნეთ Deque- ს ცარიელი.

დროის სირთულე = O (1)

ზომა ()

დასტის ზომა იგივეა რაც Deque– ს ზომა, ასე რომ დააბრუნეთ deque– ს ზომა.

დროის სირთულე = O (1)

კოდი

JAVA კოდექსის დასტის განსახორციელებლად deque
import java.util.Deque;
import java.util.LinkedList;
class StackUsingDeque {
    // deque used to implement stack
    private static Deque<Integer> deque;

    private static void push(int x) {
        // Add the element x to the front of Deque
        deque.addFirst(x);
    }

    private static int pop() {
        // if deque is not empty remove an element from the front of deque
        if (!deque.isEmpty()) {
            return deque.removeFirst();
        }
        return -1;
    }

    private static boolean isEmpty() {
        // stack is empty if deque is empty
        return deque.isEmpty();
    }

    private static int size() {
        // size of stack is same as size of Deque
        return deque.size();
    }

    public static void main(String[] args) {
        deque = new LinkedList<>();

        // Example
        push(1);
        push(2);
        push(3);
        System.out.println(pop());
        System.out.println(isEmpty());
        System.out.println(pop());
        System.out.println(size());
    }
}
3
false
2
1
C ++ კოდი დეკის გამოყენებით დასტის განსახორციელებლად
#include <bits/stdc++.h>
using namespace std;

// deque used to implement stack
deque<int> dq;

void push(int x) {
    // Add the element x to the front of Deque
    dq.push_front(x);
}

int pop() {
    // if deque is not empty remove an element from the front of deque
    if (!dq.empty()) {
        int top = dq.front();
        dq.pop_front();
        return top;
    }
    return -1;
}

int size() {
    // size of stack is same as size of Deque
    return dq.size();
}

bool isEmpty() {
    // stack is empty if deque is empty
    return dq.empty();
}

int main() {
    // Example
    push(1);
    push(2);
    push(3);
    cout<<pop()<<endl;
    if (isEmpty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    cout<<pop()<<endl;
    cout<<size()<<endl;
    
    return 0;
}
3
false
2
1

Queue

Queue არის პირველი პირველი (FIFO) მონაცემთა სტრუქტურა, რომელიც enqueue და dequeue ოპერაციებს ასრულებს მოპირდაპირე მხარეებზე. მოდით გამოვიყენოთ Deque- ს წინა ნაწილი enqueue ოპერაციისთვის და Deque- ის უკანა ნაწილი dequeue ოპერაციისთვის.

Enqueue (x)

იმისათვის, რომ გამოყოთ ელემენტი x რიგში, უბრალოდ დაამატეთ ელემენტი Deque– ს წინა მხარეს.

დროის სირთულე = O (1)

Dequeue ()

ელემენტის რიგის მოსაშორებლად ამოიღეთ ელემენტი Deque– ს უკანა მხარეს და დააბრუნეთ იგი.

დროის სირთულე = O (1)

ცარიელია()

ის მდგომ ცარიელია, თუ Deque ცარიელია, სხვა შემთხვევაში ეს არ არის. ასე რომ, დააბრუნეთ Deque- ს ცარიელი.

დროის სირთულე = O (1)

ზომა ()

რიგის ზომა იგივეა რაც Deque- ს ზომა, ასე რომ დააბრუნე deque- ს ზომა.

დროის სირთულე = O (1)

კოდი

JAVA კოდი რიგის განსახორციელებლად deque– ს გამოყენებით
import java.util.Deque;
import java.util.LinkedList;
class QueueUsingDeque {
    // deque used to implement queue
    private static Deque<Integer> deque;

    private static void enqueue(int x) {
        // add the element x at the front of deque
        deque.addFirst(x);
    }

    private static int dequeue() {
        // if deque is not empty remove and return the rear of deque
        if (!deque.isEmpty()) {
            return deque.removeLast();
        }
        return -1;
    }

    private static boolean isEmpty() {
        // queue is empty if deque is empty
        return deque.isEmpty();
    }

    private static int size() {
        // size of queue is same as size of deque
        return deque.size();
    }

    public static void main(String[] args) {
        deque = new LinkedList<>();

        // Example
        enqueue(1);
        enqueue(2);
        enqueue(3);
        System.out.println(dequeue());
        System.out.println(isEmpty());
        System.out.println(size());
        System.out.println(dequeue());
    }
}
1
false
2
2
C ++ კოდი რიგის განსახორციელებლად deque– ს გამოყენებით
#include <bits/stdc++.h>
using namespace std;

// deque used to implement queue
deque<int> dq;

void enqueue(int x) {
    // add the element x at the front of deque
    dq.push_front(x);
}

int dequeue() {
    // if deque is not empty remove and return the rear of deque
    if (!dq.empty()) {
        int front = dq.back();
        dq.pop_back();
        return front;
    }
    return -1;
}

int size() {
    // size of queue is same as size of deque
    return dq.size();
}

bool isEmpty() {
    // queue is empty if deque is empty
    return dq.empty();
}

int main() {
    // Example
    enqueue(1);
    enqueue(2);
    enqueue(3);
    cout<<dequeue()<<endl;
    if (isEmpty()) {
        cout<<"true"<<endl;
    } else {
        cout<<"false"<<endl;
    }
    cout<<size()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
1
false
2
2