Εφαρμογή Stack χρησιμοποιώντας ουρές  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις PayPal
Σχέδια Ουρά Στοίβα

Εφαρμόστε τις ακόλουθες λειτουργίες του σωρός δομή δεδομένων χρησιμοποιώντας τυπικές λειτουργίες του ουρά,

  1. push (x) -> Σπρώξτε ένα στοιχείο x στη στοίβα
  2. pop () -> Αφαιρεί το στοιχείο στην κορυφή της στοίβας
  3. κορυφή () -> Επιστρέψτε το στοιχείο στην κορυφή της στοίβας
  4. κενό () -> Επιστρέψτε εάν η στοίβα είναι άδεια

Παραδείγματα  

εισόδου:
stack.push (1);
stack.push (2);
stack.top (); // επιστρέφει 2
stack.pop (); // επιστρέφει 2
stack.empty (); // επιστρέφει ψευδές
Παραγωγή:
2
2
ψευδής

Αλγόριθμος για εφαρμογή Stack χρησιμοποιώντας ουρές  

Μια στοίβα μπορεί να εφαρμοστεί χρησιμοποιώντας 2 ουρές (ας πούμε q1 και q2).

ώθηση (x)

Πιέστε το x στο τέλος του q1 και κρατήστε το ως το πάνω μέρος της στοίβας στην κορυφαία μεταβλητή.
Ψευδοκώδικας

void push(int x) {
    q1.add(x);
    top = x;
}

Πολυπλοκότητα χρόνου = Ο (1)

μπλουζα()

Το πάνω μέρος της στοίβας διατηρείται πάντα στην κορυφαία μεταβλητή, οπότε απλώς επιστρέψτε την κορυφή.
Ψευδοκώδικας

int top() {
    return top;
}

Πολυπλοκότητα χρόνου = Ο (1)

αδειάζω()

Η στοίβα είναι κενή εάν η ουρά q1 είναι κενή.
Ψευδοκώδικας

boolean empty() {
    return q1.isEmpty();
}

Πολυπλοκότητα χρόνου = Ο (1)

κρότος()

Το πίσω μέρος της ουράς q1 περιέχει το πάνω μέρος της στοίβας, αφήστε το μέγεθος του q1 να είναι n

  1. Μετακίνηση (n - 1) στοιχείων της ουράς q1 στην ουρά q2.
  2. Επίσης, διατηρήστε την κορυφή της στοίβας καθώς μεταφέρεται η τρέχουσα μεταβλητή.
  3. Τώρα, το q1 περιέχει μόνο 1 στοιχείο που βρίσκεται στην κορυφή της στοίβας.
  4. Αφαιρέστε και αποθηκεύστε αυτό το στοιχείο σε κάποια μεταβλητή (ας πούμε ele).
  5. Μετακίνηση όλων των στοιχείων από την ουρά q2 στην ουρά q1.
  6. Επιστροφή ele.
Βλέπε επίσης
Βρείτε τον ελάχιστο αριθμό πράξεων συγχώνευσης για να δημιουργήσετε έναν πίνακα palindrome

Πολυπλοκότητα χρόνου = O (n) 
όπου n είναι ο αριθμός των στοιχείων στην ουρά.

Εξετάστε ένα παράδειγμα,
q1 = 3 -> 5 -> 7 -> 1 -> 2
q2 = μηδέν

Βγάλτε ένα στοιχείο.

  1. Μεταφορά (n - 1) από q1 στο q2
    q1 = 2 και q2 = 3 -> 5 -> 7 -> 1
  2. Αφαιρέστε και αποθηκεύστε το στοιχείο στο q1.
    q1 = null και q2 = 3 -> 5 -> 7 -> 1 και ele = 2
  3. Μετακινήστε όλα τα στοιχεία από q2 στο q1.
    q1 = 3 -> 5 -> 7 -> 1 και q2 = null
  4. Επιστροφή ele.

Δείτε την παρακάτω εικόνα για διευκρινίσεις.

Εφαρμογή Stack χρησιμοποιώντας ουρέςΚαρφώστε

Ψευδοκώδικας

int pop() {
    int n = q1.size();
    for (int i = 0; i < n - 1; i++) {
        int curr = q1.remove();
        q2.add(curr);
        top = curr;
    }
    int ele = q1.remove();
    n = q2.size();
    for (int i = 0; i < n; i++) {
        q1.add(q2.remove());
    }
    return ele;
}

Πολυπλοκότητα χρόνου = O (n)

Κώδικας JAVA για εφαρμογή Stack χρησιμοποιώντας ουρές  

import java.util.Queue; 
import java.util.LinkedList;
public class StackUsingQueues {
    // Two queues to implement stack
    private static Queue<Integer> q1 = new LinkedList<>();
    private static Queue<Integer> q2 = new LinkedList<>();
    // Stores the top element of stack
    private static int top;

    private static void push(int x) {
        // Add element at rear of q1
        q1.add(x);
        // update top as current element
        top = x;
    }

    private static int top() {
        // Top stores the top of stack
        return top;
    }

    private static int pop() {
        int n = q1.size();
        // Shift (n - 1) elements from q1 to q2 and update top as curr
        // element transferred
        for (int i = 0; i < n - 1; i++) {
            int curr = q1.remove();
            q2.add(curr);
            top = curr;
        }
        // q1 contains only 1 element which is top of stack
        // store the element in ele and remove it from q1
        int ele = q1.remove();
        n = q2.size();
        // Again transfer back the elements from q2 to q1
        for (int i = 0; i < n; i++) {
            q1.add(q2.remove());
        }
        // return ele, this is the top of stack
        return ele;
    }
    
    private static boolean empty() {
        // If q1 is empty then stack is empty
        return q1.isEmpty();
    }
    
    public static void main(String[] args) {
        // Example
        push(1);
        push(2);
        System.out.println(top());
        System.out.println(pop());
        System.out.println(empty());
    }
}

Κωδικός C ++ για εφαρμογή Stack χρησιμοποιώντας ουρές  

#include <bits/stdc++.h>
using namespace std;

// Two queues to implement stack
queue<int> q1;
queue<int> q2;
// Stores the top element of stack
int Top;

void push(int x) {
    // Add element at rear of q1
    q1.push(x);
    // update top as current element
    Top = x;
}

int top() {
    // Top stores the top of stack
    return Top;
}

bool empty() {
    // If q1 is empty then stack is empty
    return q1.empty();
}

int pop() {
    int n = q1.size();
    // Shift (n - 1) elements from q1 to q2 and update top as curr
    // element transferred
    for (int i = 0; i < n - 1; i++) {
        int curr = q1.front();
        q1.pop();
        q2.push(curr);
        Top = curr;
    }
    // q1 contains only 1 element which is top of stack
    // store the element in ele and remove it from q1
    int ele = q1.front();
    q1.pop();
    n = q2.size();
    // Again transfer back the elements from q2 to q1
    for (int i = 0; i < n; i++) {
        q1.push(q2.front());
        q2.pop();
    }
    // return ele, this is the top of stack
    return ele;
}

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

Αναφορά1    αναφορά2