Создайте стек для получения исходных элементов и возврата минимального элемента за время O (1) и пространство O (1)

Опубликовано: 24 Января, 2022

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

Пример:

Рассмотрим следующий специальный стек
16 -> ТОП
15
29
19
18

Когда вызывается getMin (), он должен вернуть 15, что является минимумом. 
элемент в текущем стеке. 

Если мы дважды вытолкнем стек, стек станет
29 -> ТОП
19
18

Когда вызывается getMin (), он должен вернуть 18, что является минимумом. 
в текущем стеке.

Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.

Здесь обсуждается подход, который использует O (1) время и O (1) дополнительное пространство. Однако в предыдущей статье исходные элементы не восстанавливаются. В любой момент времени возвращается только минимальный элемент.

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

Подход:
Рассмотрим переменный минимум, в котором мы храним минимальный элемент в стеке. А что, если мы вытолкнем минимальный элемент из стека? Как обновить минимальную переменную до следующего минимального значения? Одно из решений - поддерживать другой стек в отсортированном порядке, чтобы наименьший элемент всегда был наверху. Однако это пространственный подход O (n).
Чтобы достичь этого в пространстве O (1) , нам нужен способ сохранить текущее значение элемента и следующее минимальное значение в одном и том же узле. Это можно сделать, применив простую математику:

new_value = 2*current_value - minimum

Мы помещаем это new_value в стек вместо current_value. Чтобы получить current_value и следующий минимум из new_value:

текущее_значение = (новое_значение + минимум) / 2
минимум = новое_значение - 2 * текущее

Когда операция Push (x) выполнена, мы следуем приведенному ниже алгоритму:

If stack is empty
insert x into the stack
make minimum equal to x.
If stack is not empty
if x is less than minimum
set temp equal to 2*x-minimum
set minimum equal to x
set x equal to temp
insert x into stack

Когда операция Pop (x) выполнена, мы следуем приведенному ниже алгоритму:

If stack is not empty
set x equal to topmost element
if x is less than minimum
set minimum equal to 2*minimum – x
set x equal to (x+minimum)/2
return x

When getMin() is called, we return the element stored in variable, minimum:

Java

// Java program to retrieve original elements of the
// from a Stack which returns the minimum element
// in O(1) time and O(1) space
  
class Stack {
    Node top;
  
    // Stores minimum element of the stack
    int minimum;
      
    // Function to push an element
    void push(Node node)
    {
        int current = node.getData();
        if (top == null) {
            top = node;
            minimum = current;
        }
        else {
            if (current < minimum) {
                node.setData(2 * current - minimum);
                minimum = current;
            }
            node.setNext(top);
            top = node;
        }
    }
  
    // Retrieves topmost element
    Node pop()
    {
        Node node = top;
        if (node != null) {
            int current = node.getData();
            if (current < minimum) {
                minimum = 2 * minimum - current;
                node.setData((current + minimum) / 2);
            }
            top = top.getNext();
        }
        return node;
    }
  
    // Retrieves topmost element without
    // popping it from the stack
    Node peek()
    {
        Node node = null;
        if (top != null) {
            node = new Node();
            int current = top.getData();
            node.setData(current < minimum ? minimum : current);
        }
        return node;
    }
  
    // Function to print all elements in the stack
    void printAll()
    {
        Node ptr = top;
        int min = minimum;
        if (ptr != null) { // if stack is not empty
            while (true) {
                int val = ptr.getData();
                if (val < min) {
                    min = 2 * min - val;
                    val = (val + min) / 2;
                }
                System.out.print(val + "  ");
                ptr = ptr.getNext();
                if (ptr == null)
                    break;
            }
            System.out.println();
        }
        else
            System.out.println("Empty!");
    }
  
    // Returns minimum of Stack
    int getMin()
    {
        return minimum;
    }
  
    boolean isEmpty()
    {
        return top == null;
    }
}
  
// Node class which contains data
// and pointer to next node
class Node {
    int data;
    Node next;
    Node()
    {
        data = -1;
        next = null;
    }
  
    Node(int d)
    {
        data = d;
        next = null;
    }
  
    void setData(int data)
    {
        this.data = data;
    }
  
    void setNext(Node next)
    {
        this.next = next;
    }
  
    Node getNext()
    {
        return next;
    }
  
    int getData()
    {
        return data;
    }
}
  
// Driver Code
public class Main {
    public static void main(String[] args)
    {
        // Create a new stack
        Stack stack = new Stack();
        Node node;
  
        // Push the element into the stack
        stack.push(new Node(5));
        stack.push(new Node(3));
        stack.push(new Node(4));
  
        // Calls the method to print the stack
        System.out.println("Elements in the stack are:");
        stack.printAll();
          
        // Print current minimum element if stack is
        // not empty
        System.out.println(stack.isEmpty() ? "
Empty Stack!" : 
                                "
Minimum: " + stack.getMin());
  
        // Push new elements into the stack
        stack.push(new Node(1));
        stack.push(new Node(2));
  
        // Printing the stack
        System.out.println("
Stack after adding new elements:");
        stack.printAll();
          
        // Print current minimum element if stack is
        // not empty
        System.out.println(stack.isEmpty() ? "
Empty Stack!" : 
                                    "
Minimum: " + stack.getMin());
  
        // Pop elements from the stack
        node = stack.pop();
        System.out.println("
Element Popped: "
                        + (node == null ? "Empty!" : node.getData()));
  
        node = stack.pop();
        System.out.println("Element Popped: "
                        + (node == null ? "Empty!" : node.getData()));
          
        // Printing stack after popping elements
        System.out.println("
Stack after removing top two elements:");
        stack.printAll();
          
        // Printing current Minimum element in the stack
        System.out.println(stack.isEmpty() ? "
Empty Stack!" : 
                                        "
Minimum: " + stack.getMin());
          
        // Printing top element of the stack
        node = stack.peek();
  
        System.out.println("
Top: " + (node == null ? 
                                       "
Empty!" : node.getData()));
    }
}

Python3

"""
Python program to retrieve original elements of the
from a Stack which returns the minimum element
in O(1) time and O(1) space
"""
  
# Class to make a Node 
class Node:
      
    # Constructor which assign argument to nade"s value 
    def __init__(self, value):
        self.value = value
        self.next = None
  
    # This method returns the string 
    # representation of the object.
    def __str__(self):
        return "Node({})".format(self.value)
      
    # __repr__ is same as __str__
    __repr__ = __str__
  
  
class Stack:
      
    # Stack Constructor initialise
    # top of stack and counter.
    def __init__(self):
        self.top = None
        self.count = 0
        self.minimum = None
          
    # This method returns the string
    # representation of the object (stack).
    def __str__(self):
        temp=self.top
        m = self.minimum
        out=[]
        if temp is None:
            print("Empty Stack")
        else:
            while not temp is None :
                val = temp.value
                if val < m:
                    m = (2 * m) -val
                    val = ( val + m ) / 2
                out.append(str(int(val)))
                temp=temp.next
            out=" ".join(out)
            return (out)
          
    # __repr__ is same as __str__
    __repr__=__str__
      
    # This method is used to get minimum element of stack
    def getMin(self):
        if self.top is None:
            return "Stack is empty"
        else:
            return self.minimum
  
  
    # Method to check if Stack is Empty or not
    def isEmpty(self):
          
        # If top equals to None then stack is empty 
        if self.top == None:
            return True
        else:
              
        # If top not equal to None then stack is empty 
            return False
  
    # This method returns length of stack     
    def __len__(self):
        self.count = 0
        tempNode = self.top
        while tempNode:
            tempNode = tempNode.next
            self.count+=1
        return self.count
  
    # This method returns top of stack     
    def peek(self):
        if self.top is None:
            print ("Stack is empty")
        else: 
            if self.top.value < self.minimum:
                return self.minimum
            else:
                return self.top.value
  
    # This method is used to add node to stack
    def push(self,value):
        if self.top is None:
            self.top = Node(value)
            self.minimum = value
          
        else:
            new_node = Node(value)
            if value < self.minimum:
                temp = (2 * value) - self.minimum
                new_node.value = temp
                self.minimum = value
            new_node.next = self.top
            self.top = new_node
              
  
    # This method is used to pop top of stack
    def pop(self):
        new_node = self.top
        if self.top is None:
            print( "Stack is empty")
        else:
            removedNode = new_node.value
            if removedNode < self.minimum:
                self.minimum = ( ( 2 * self
            

                    
                                            Структуры данных
                                    
РЕКОМЕНДУЕМЫЕ СТАТЬИРазличия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023
Введение в связанный список — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Лист Google SDE: вопросы и ответы на собеседовании
12 Декабря, 2022
Введение в массивы — учебные пособия по структуре данных и алгоритмам
12 Декабря, 2022
Как подготовиться к ICFP или Международной конференции по функциональному программированию?
12 Декабря, 2022


    


        
            
                
                    
                        
                        < PROGLER >
                    
                
                
                    
                        Общее
                        
                        Контакты
                        Политика конфиденциальности
                    
                    
                        Обучение
                        Блог
                    
                
            
            
                © progler.ru 2025. Все права защищены.