Рубрики

Разработка и внедрение специальной структуры данных стека | Добавлена космическая оптимизированная версия

Вопрос: Разработайте структуру данных SpecialStack, которая поддерживает все операции со стеком, такие как push (), pop (), isEmpty (), isFull () и дополнительная операция getMin () который должен возвращать минимальный элемент из SpecialStack. Все эти операции SpecialStack должны быть O (1). Чтобы реализовать SpecialStack, вы должны использовать только стандартную структуру данных стека и никакую другую структуру данных, такую как массивы, списки и т. Д.

Пример:

Consider the following SpecialStack
16  --> TOP
15
29
19
18

When getMin() is called it should return 15, which is the minimum 
element in the current stack. 

If we do pop two times on stack, the stack becomes
29  --> TOP
19
18

When getMin() is called, it should return 18 which is the minimum 
in the current stack.

Решение. Используйте два стека: один для хранения фактических элементов стека, а другой в качестве вспомогательного стека для хранения минимальных значений. Идея состоит в том, чтобы выполнять операции push () и pop () таким образом, чтобы вершина вспомогательного стека всегда была минимальной. Давайте посмотрим, как работают операции push () и pop ().

Push (int x) // вставляет элемент x в специальный стек
1) нажмите x в первый стек (стек с актуальными элементами)
2) сравнить x с верхним элементом второго стека (вспомогательный стек). Пусть верхний элемент будет y.
… ..A) Если x меньше, чем y, нажмите x во вспомогательный стек.
… ..B) Если x больше, чем y, тогда переместите y во вспомогательный стек.

int Pop () // удаляет элемент из специального стека и возвращает удаленный элемент
1) вытолкнуть верхний элемент из вспомогательного стека.
2) вытолкнуть верхний элемент из фактического стека и вернуть его.

Шаг 1 необходим, чтобы убедиться, что вспомогательный стек также обновляется для будущих операций.

int getMin () // возвращает минимальный элемент из специального стека
1) Вернуть верхний элемент вспомогательного стека.

Мы видим, что все вышеперечисленные операции являются O (1) .
Давайте посмотрим на пример. Предположим, что оба стека изначально пусты и 18, 19, 29, 15 и 16 вставлены в SpecialStack.

 Когда мы вставляем 18, оба стека меняются на следующие.
Фактический стек
18

Ниже приведена реализация класса SpecialStack. В приведенной ниже реализации SpecialStack наследуется от Stack и имеет один минимальный объект Stack, который работает как вспомогательный стек.

C ++

#include<iostream>
#include<stdlib.h>

  

using namespace std;

  
/ * Простой класс стека с основными функциями стека * /

class Stack

{

private:

    static const int max = 100;

    int arr[max];

    int top;

public:

    Stack() { top = -1; }

    bool isEmpty();

    bool isFull();

    int pop();

    void push(int x);

};

  
/ * Метод члена стека, чтобы проверить, является ли стек iempty * /

bool Stack::isEmpty()

{

    if(top == -1)

        return true;

    return false;

}

  
/ * Метод члена стека, чтобы проверить, заполнен ли стек * /

bool Stack::isFull()

{

    if(top == max - 1)

        return true;

    return false;

}

  
/ * Метод члена стека для удаления элемента из него * /

int Stack::pop()

{

    if(isEmpty())

    {

        cout<<"Stack Underflow";

        abort();

    }

    int x = arr[top];

    top--;

    return x;

}

  
/ * Метод члена стека для вставки в него элемента * /

void Stack::push(int x)

{

    if(isFull())

    {

        cout<<"Stack Overflow";

        abort();

    }

    top++;

    arr[top] = x;

}

  
/ * Класс, который поддерживает все операции со стеком и одну дополнительную

  операция getMin (), которая возвращает минимальный элемент из стека в

  любое время. Этот класс наследуется от класса стека и использует

  вспомогательный стек, содержащий минимальные элементы * /

class SpecialStack: public Stack

{

    Stack min;

public:

    int pop();

    void push(int x);

    int getMin();

};

  
/ * Метод члена SpecialStack для вставки в него элемента. Этот метод

   гарантирует, что минимальный стек также обновляется с соответствующим минимумом

   ценности */

void SpecialStack::push(int x)

{

    if(isEmpty()==true)

    {

        Stack::push(x);

        min.push(x);

    }

    else

    {

        Stack::push(x);

        int y = min.pop();

        min.push(y);

        if( x < y )

          min.push(x);

        else

          min.push(y);

    }

}

  
/ * Метод члена SpecialStack для удаления элемента из него. Этот метод

   также удаляет верхний элемент из минимального стека. * /

int SpecialStack::pop()

{

    int x = Stack::pop();

    min.pop();

    return x;

}

  
/ * Метод члена SpecialStack для получения минимального элемента из него. * /

int SpecialStack::getMin()

{

    int x = min.pop();

    min.push(x);

    return x;

}

  
/ * Программа драйвера для тестирования методов SpecialStack * /

int main()

{

    SpecialStack s;

    s.push(10);

    s.push(20);

    s.push(30);

    cout<<s.getMin()<<endl;

    s.push(5);

    cout<<s.getMin();

    return 0;

}

Джава

// Java-реализация SpecialStack
// Примечание: здесь мы используем класс Stack для реализации Stack

  

import java.util.Stack;

  
/ * Класс, который поддерживает все операции со стеком и одну дополнительную
операция getMin (), которая возвращает минимальный элемент из стека в
любое время. Этот класс наследуется от класса стека и использует
вспомогательный стек, содержащий минимальные элементы * /

  

class SpecialStack extends Stack<Integer>

{

    Stack<Integer> min = new Stack<>();

      

    / * Метод члена SpecialStack для вставки в него элемента. Этот метод

    гарантирует, что минимальный стек также обновляется с соответствующим минимумом

    ценности */

    void push(int x)

    {

        if(isEmpty() == true)

        {

            super.push(x);

            min.push(x);

        }

        else

        {

            super.push(x);

            int y = min.pop();

            min.push(y);

            if(x < y)

                min.push(x);

            else

                min.push(y);

        }

    }

  

    / * Метод члена SpecialStack для вставки в него элемента. Этот метод

    гарантирует, что минимальный стек также обновляется с соответствующим минимумом

    ценности */

    public Integer pop()

    {

        int x = super.pop();

        min.pop();

        return x;

    }

  

    / * Метод члена SpecialStack для получения минимального элемента из него. * /

    int getMin()

    {

        int x = min.pop();

        min.push(x);

        return x;

    }

  

    / * Программа драйвера для тестирования методов SpecialStack * /

    public static void main(String[] args) 

    {

        SpecialStack s = new SpecialStack();

        s.push(10);

        s.push(20);

        s.push(30);

        System.out.println(s.getMin());

        s.push(5);

        System.out.println(s.getMin());

    }

}
// Этот код предоставлен Sumit Ghosh

Выход:
10
5

Космическая оптимизированная версия
Вышеуказанный подход может быть оптимизирован. Мы можем ограничить количество элементов во вспомогательном стеке. Мы можем толкать только тогда, когда входящий элемент основного стека меньше или равен вершине вспомогательного стека. Аналогично, во время pop, если элемент pop off равен вершине вспомогательного стека, удалите верхний элемент вспомогательного стека. Ниже приводится модифицированная реализация push () и pop ().

C ++

/ * Метод члена SpecialStack для вставки в него элемента. Этот метод

   гарантирует, что минимальный стек также обновляется с соответствующим минимумом

   ценности */

void SpecialStack::push(int x)

{

    if(isEmpty()==true)

    {

        Stack::push(x);

        min.push(x);

    }

    else

    {

        Stack::push(x);

        int y = min.pop();

        min.push(y);

   

        / * push только когда входящий элемент основного стека меньше

        чем или равно вершине вспомогательного стека * /

        if( x <= y )

          min.push(x);

    }

}

  
/ * Метод члена SpecialStack для удаления элемента из него. Этот метод

   также удаляет верхний элемент из минимального стека. * /

int SpecialStack::pop()

{

    int x = Stack::pop();

    int y = min.pop();

  

    / * Отодвинуть вытянутый элемент y обратно, только если он не равен x * /

    if ( y != x )

      min.push(y);

  

    return x;

}

Джава

/ * Метод члена SpecialStack для вставки в него элемента. Этот метод
гарантирует, что минимальный стек также обновляется с соответствующим минимумом
ценности */

  

void push(int x)

{

    if(isEmpty() == true)

    {

        super.push(x);

        min.push(x);

    }

    else

    {

        super.push(x);

        int y = min.pop();

           min.push(y);

      

        / * push только когда входящий элемент основного стека меньше

        чем или равно вершине вспомогательного стека * /

        if( x <= y )

            min.push(x);

    }

}

      
/ * Метод члена SpecialStack для удаления элемента из него. Этот метод
также удаляет верхний элемент из минимального стека. * /

public Integer pop()

{

    int x = super.pop();

    int y = min.pop();

      

    / * Отодвинуть вытянутый элемент y обратно, только если он не равен x * /

    if ( y != x )

        min.push(y);

    return x;

}

  
// Этот код предоставлен Sumit Ghosh


Разработайте стек, который поддерживает getMin () за O (1) время и O (1) дополнительное пространство

Спасибо @Venki , @swarup и @Jing Huang за их вклад.

Пожалуйста, напишите комментарии, если вы обнаружите, что приведенный выше код неверен, или найдите другие способы решения той же проблемы.

Рекомендуемые посты:

Разработка и внедрение специальной структуры данных стека | Добавлена космическая оптимизированная версия

0.00 (0%) 0 votes