Իրականացրեք Stack- ը և հերթը Deque- ի միջոցով


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Ֆանատիկա GE Healthcare MAQ Մենտրա Qualcomm
Դեկվյու Հերթ Գրապահոց

Խնդիրի հայտարարություն

«Իրականացնել բուրգը և հերթը Deque- ի օգտագործմամբ» խնդիրը նշում է, որ Stack- ը և 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,

Իրականացրեք Stack- ը և հերթը Deque- ի միջոցով

Գրապահոց

Գրապահոց վերջին վերջին ելքի (LIFO) տվյալների կառուցվածքն է, այսինքն ՝ տարրերը դուրս են գալիս նույն կողմից, որտեղ դրանք մղվում են: Եկեք օգտագործենք Deque- ի ճակատը `stack- ի համար հրում և փոփ գործողություն կատարելու համար:

Հրել (x)

X տարրը դեղին մղելու համար պարզապես ավելացրեք x տարրը Deque- ի առջևում:

Timeամանակի բարդություն = Ո (1)

Փոփ ()

Փոփ գործողությունը տեղի է ունենում Push- ի նույն կողմում, այսինքն ՝ stack- ից տարր դուրս գալը ջնջել deque- ի առջևում գտնվող տարրը և վերադարձնել այն:

Timeամանակի բարդություն = Ո (1)

դատարկ է()

Եթե ​​Deque- ը դատարկ է, ապա դեղը դատարկ է, այլապես դա չէ: Այսպիսով, վերադարձրեք Deque- ի դատարկը:

Timeամանակի բարդություն = Ո (1)

չափ ()

Դեղի չափը նույնն է Deque- ի չափին, այնպես որ վերադարձեք deque- ի չափը:

Timeամանակի բարդություն = Ո (1)

Կոդ

JAVA կոդ ՝ stack օգտագործելով 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 ++ կոդ ՝ ստեղն օգտագործելու համար, օգտագործելով deque
#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

Հերթ

Հերթը առաջինն է առաջինից դուրս (FIFO) տվյալների կառուցվածքն է, որը enqueue և dequeue գործողություններն իրականացվում են հակառակ կողմերում: Եկեք օգտագործենք Deque- ի ճակատը `enqueue գործողության համար, իսկ Deque- ի հետեւի մասը` dequeue գործողության համար:

Enqueue (x)

Հերթում x տարր պարունակելու համար պարզապես ավելացրեք տարրը Deque- ի առջևում:

Timeամանակի բարդություն = Ո (1)

Dequeue ()

Որպեսզի տարրը հերթից հանելու համար հեռացրեք տարրը Deque- ի հետևում և վերադարձեք այն:

Timeամանակի բարդություն = Ո (1)

դատարկ է()

The հերթ դատարկ է, եթե Deque- ն դատարկ է, այլապես չէ: Այսպիսով, վերադարձրեք Deque- ի դատարկը:

Timeամանակի բարդություն = Ո (1)

չափ ()

Հերթի չափը նույնն է, ինչ Deque- ի չափը, այնպես որ վերադարձեք deque- ի չափը:

Timeամանակի բարդություն = Ո (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