Maksimal tezlikli stek (Həll təhlili)

Hər bir $x$ ədədi üçün, həmin ədədin stekdə rast gəlinmə sayını freq[x] saxlayacağıq. $freq$ saxlama strukturu olaraq xəritədən istifadə edəcəyik.

Stack massivini vector003cstack003cint003e003e st elan edəcəyik, burada $st[i]$ elementi stekdə tam olaraq i + 1 dəfə rast gəlinən ədədləri saxlayır (massiv $st$ sıfırdan başlayaraq indekslənib). $st[i]$ içərisindəki elementlərin sırası stəkə əlavə olunma sırası ilə müvafiqdir.

Tutaq ki, $x$ ədədi stekə $k$-cı dəfə əlavə olunur. Əgər st[k - 1] stəki hələ yarudulmamış olsa, onu push_back ilə yaradırıq. Sonra $x$ elementini st[k - 1] stəkünün zirvəsinə qoyuruq.

Elementin silinməsi zamanı ən sonuncu boş olmayan stəkin zirvəsindən element çıxarılmalıdır.

Məsələn, daha sonrakı əməliyyatlar yalnız pop olarsa, stekdən elementlər aşağıdakı sırayla silinəcək: 4, 5, 4, 6, 5, 4.

Nümunə

Elementlərin stek massivinə əlavə olunma qaydasını aşağıda bir nümunə ilə nəzərdən keçirək.

Elementlər aşağıdakı sırayla çıxarılacaq: 1, 5, 1, 5, 2, 6, 1, 5.

Alqoritmin reallaşdırılması

Frekvensiya steki ilə işləmək üçün FreqStack sinifini müəyyən edəcəyik.

class FreqStack
{
public:

Elan edək:

• $freq$ xəritəsi, burada freq[x] stekdə $x$ elementinin rast gəlinmə sayını saxlayır;

• stek massivləri $st$;

  map\u003cint, int\u003e freq;
  vector\u003cstack\u003cint\u003e\u003e st;

push funksiyası stekə $x$ elementini əlavə edir.

  void push(int x)
  {
    int f = freq[x];
    freq[x] = f + 1;
    if (f == st.size()) st.push_back(stack\u003cint\u003e());
    st[f].push(x);
  }

pop funksiyası stekədən element çıxarır.

  int pop()
  {
    int x = st.back().top();
    st.back().pop();
    if (st.back().empty()) st.pop_back();
    freq[x]--;
    return x;
  }
};

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq. Stek əməliyyatlarını modelləşdiririk.

while (cin \u003e\u003e str)
{
  if (str == "push")
  {
    cin \u003e\u003e n;
    fs.push(n);
  }
  else // pop
    cout \u003c\u003c fs.pop() \u003c\u003c endl;
}