Блог

Мне нужно найти наименьшее значение в стеке, но за постоянное время. Итак, из-за этого я не могу использовать for цикл или while цикл. Я предоставлю вам приведенный ниже код, и мне просто нужна подсказка, поэтому я буду рад, если вы сможете мне помочь.

Вот заголовочные файлы и main.cpp file .

main.cpp:

 // Testni program za stek
#include <iostream>
using namespace std;

#include "nizstektmp.h"

int Menu() { // Ispis menu opcija
    int izbor;
    cout << endl<<"---Menu----------------------" << endl<<endl;
    cout << "1. Stavi na INT stek" << endl;
    cout << "2. Skini sa INT steka" << endl;
    cout << "3. Element na vrhu INT steka" << endl;
    cout << "4. Prikazi sadrzaj INT steka" << endl;
    cout << "5. Stavi na CHAR stek" << endl;
    cout << "6. Skini sa CHAR steka" << endl;
    cout << "7. Element na vrhu CHAR steka" << endl;
    cout << "8. Prikazi sadrzaj CHAR steka" << endl;
    cout << "9. Skini vise elemenata sa INT steka" << endl;
    cout << "10. Nadji minimalan elemenat u steku O(1)" << endl;
    cout << "0. Izlaz" << endl;
    cout << endl<<"-------------Izaberite opciju>" ;
    cin >> izbor;
    if (cin)
        return izbor;
    else {
        cin.clear();
        cin.ignore(100,'n');
        return -1;
    }
}

int main() {
    NizStek<int> intstek;
    NizStek <char> charstek;
    int izbor, x, k;
    char y;
    while (izbor=Menu()) {
        try {
            switch (izbor) {
                case 0:
                    return 0;
                case 1:
                    cout << "nUnesite podatak:";
                    cin >> x;
                    if (!cin) throw 0;
                    intstek.StaviNaStek(x);
                    cout << "Element je umetnut" << endl;
                    break;
                case 2:
                    x=intstek.SkiniSaSteka();
                    cout << "Element " << x << " je skinut" << endl;
                    break;
                case 3:
                    cout << "nElement na vrhu steka:" << intstek.ElementNaVrhu();
                    break;
                case 4:
                    intstek.Prikazi();
                    break;
                case 5:
                    cout << "nUnesite podatak:";
                    cin >> y;
                    charstek.StaviNaStek(y);
                    cout << "Element je umetnut" << endl;
                    break;
                case 6:
                    y=charstek.SkiniSaSteka();
                    cout << "Element " << y << " je skinut" << endl;
                    break;
                case 7:
                    cout << "nElement na vrhu steka:" << charstek.ElementNaVrhu();
                    break;
                case 8:
                    charstek.Prikazi();
                    break;
                case 9:
                    intstek.SkiniSaStekaVise(k);
                    break;
                case 10:
                    intstek.NadjiMinimum();
                    break;
                default:
                    cout << "Pogresan izbor" << endl;
            }
        }
        catch (const char greska[]) {
            cout << greska;
        }
        catch (...) {
            cout << "nGreska u programu";
        }
    }
} 
 

stek.h

 // Definicija apstraktne klase “Stek”
#ifndef STEK_H
#define STEK_H

template <typename InfoTip>
class Stek {
private:
    void operator =(const Stekamp;); // Zaštita za dodjelu
    Stek(const Stekamp;); // Zaštita za konstruktor kopije
public:
    Stek() {} // Podrazumijevani konstruktor
    virtual ~Stek() {} // Bazni destruktor
    virtual void Brisi() = 0; // Reinicijalizacija steka
    virtual void StaviNaStek(const InfoTipamp;) = 0; // Stavljanje na stek
    virtual InfoTip SkiniSaSteka() = 0; // Skidanje sa steka
    virtual const InfoTipamp; ElementNaVrhu() const = 0; // Vraca vršni el.
    virtual int Duzina() const = 0; // Vraca dužinu steka
};

#endif
 

nizstek.h

 // Definicija klase “NizStek”
#ifndef NIZSTEK_H
#define NIZSTEK_H

#include "stek.h"

template <typename InfoTip>
class NizStek : public Stek<InfoTip> {
private:
    InfoTip *Elementi; // Niz koji sadrži elemente steka
    int kapacitet; // Kapacitet steka
    int vrh; // Vrh steka
public:
    NizStek(int kapacitet = 10) : kapacitet(kapacitet), // Konstruktor
        vrh(-1), Elementi(new InfoTip[kapacitet]) {}
    ~NizStek() {delete [] Elementi; } // Destruktor
    void Brisi() { vrh = -1; } // Brisanje
    void StaviNaStek (const InfoTip amp;x); // Stavljanje na stek
    InfoTip SkiniSaSteka(); // Skidanje sa steka
    const InfoTipamp; ElementNaVrhu() const; // Vraca vršni element
    bool JeLiPrazan() const { return vrh == -1; } // Je li stek prazan?
    bool JeLiPun() const { return vrh == kapacitet - 1; } // Je li stek pun?
    int Duzina() const { return vrh   1; } // Vraca dužinu steka
    void Prikazi() const; // Ispis sadržaja steka
    InfoTip SkiniSaStekaVise(int k);
    InfoTip NadjiMinimum();
};

#endif 
 

nizstektmp.h

 // Definicija metoda klase “NizStek”
#ifndef NIZSTEKTMP_H
#define NIZSTEKTMP_H

#include "nizstek.h"

template <typename InfoTip> // Stavljanje na stek
void NizStek<InfoTip>::StaviNaStek(const InfoTip amp;x) {
    if (JeLiPun())
        throw "nStek je pun!n";
    Elementi[  vrh] = x;
}

template <typename InfoTip> // Skidanje sa steka
InfoTip NizStek<InfoTip>::SkiniSaSteka() {
    if (JeLiPrazan())
        throw "nStek prazan!n";
    return Elementi[vrh--];
}

template <typename InfoTip> // Vraca vršni element
const InfoTipamp; NizStek<InfoTip>::ElementNaVrhu() const {
    if (JeLiPrazan())
        throw "nStek prazan!n";
    return Elementi[vrh];
}

template <typename InfoTip> // Ispis sadržaja steka
void NizStek<InfoTip>::Prikazi() const {
    cout << endl << "Sadrzaj steka:" << endl << endl;
    for(int i = vrh; i >= 0; i--)
        cout << i << ":" << Elementi[i] << endl;
}

template <typename InfoTip>
InfoTip NizStek<InfoTip>::SkiniSaStekaVise(int k) {
    if(JeLiPrazan())
        throw "nStek prazan!n";
    cout << "Koliko elemenata zelite skinuti sa steka: ";
    cin >> k;
    vrh -= k;
    return Elementi[vrh];
}

template <typename InfoTip>
InfoTip NizStek<InfoTip>::NadjiMinimum() {
    InfoTip *PomocniStek = new InfoTip[kapacitet];
    int noviVrh = 0;
    PomocniStek[noviVrh  ] = vrh;
    if(noviVrh >= 0 amp;amp; Elementi[vrh] < PomocniStek[noviVrh]) {
        PomocniStek[noviVrh  ] = vrh;
    } else if (noviVrh == -1) {
        PomocniStek[noviVrh  ] = vrh;
    }
    cout << "Najmanji elemenat u stacku je: " << noviVrh << endl;
}

#endif 
 

Вызывается функция , которую я использую для получения минимального элемента NadjiMinimum() . У меня есть идея создать новый стек и скопировать только те элементы, которые находятся ниже остальных элементов в этом стеке, так что мне нужно возвращать только верхний элемент в стеке.

Я совершаю ошибку, или что-то подобное возможно?