我们的任务是设计一个支持所有堆栈操作的数据结构SpecialStack，比如 推 , pop（） , isEmpty（） , isFull（） 还有一个额外的手术 getMin( )它应该从SpecialStack返回最小元素。SpecialStack的所有这些操作都必须在时间复杂度为O（1）的情况下执行。要实现SpecialStack，您应该只使用标准堆栈数据结构，而不使用数组、列表等其他数据结构。 例子：
null
Consider the following Special-Stack16 --> TOP15291918When 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 becomes29 --> TOP1918When getMin() is called, it should return 18 which is the minimum in the current stack.
一 方法 讨论了使用O（1）时间和O（1）额外空间的情况 在这里 .然而，在前一篇文章中，原始元素没有被恢复。在任何给定的时间点，只返回最小元素。 在本文中，对前面的方法进行了修改，以便在查询过程中也可以检索原始元素 pop（） 活动 方法： 考虑变量 最低限度 我们在堆栈中存储最小元素。现在，如果我们从堆栈中弹出最小元素呢？如何将最小变量更新为下一个最小值？一种解决方案是按排序顺序维护另一个堆栈，以便最小的元素始终位于顶部。然而，这是一种O（n）空间方法。 为了实现这一目标 O（1） 空间，我们需要一种方法来存储元素的当前值和同一节点中的下一个最小值。这可以通过应用简单的数学来实现：
new_value = 2*current_value - minimum
我们将这个新的_值推送到堆栈中，而不是当前的_值。要从新的_值中检索当前_值和下一个最小值：
current_value = (new_value + minimum)/2minimum = new_value - 2*current
手术什么时候开始 推（x） 完成后，我们遵循以下给定的算法：
- 如果堆栈为空
- 在堆栈中插入x
- 使最小值等于x。
- 如果堆栈不是空的
- 如果x小于最小值
- 将温度设置为最小2*x
- 将最小值设为x
- 将x设置为temp
- 将x插入堆栈
手术什么时候开始 流行音乐（x） 完成后，我们遵循以下给定的算法：
- 如果堆栈不是空的
- 将x设置为最上面的元素
- 如果x小于最小值
- 将最小值设置为2*最小值–x
- 将x设置为（x+最小值）/2
- 返回x
调用getMin（）时，我们返回存储在变量中的元素， 最低限度 :
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 .minimum ) - removedNode ) new_node.value = ( (removedNode + self .minimum) / 2 ) self .top = self .top. next return int (new_node.value) # Driver program to test above class stack = Stack() stack.push( 5 ) stack.push( 3 ) stack.push( 4 ) print ( "Elements in the stack are:" ) print (stack) print ( "Minimum: {}" . format ( stack.getMin() ) ) stack.push( 1 ) stack.push( 2 ) print ( "Stack after adding new elements:" ) print (stack) print ( "Minimum:{}" . format ( stack.getMin() ) ) print ( "Element Popped: {}" . format (stack.pop())) print ( "Element Popped: {}" . format (stack.pop())) print ( "Stack after removing top two elements: " ) print (stack) print ( "Minimum: {}" . format ( stack.getMin() ) ) print ( "Top: {}" . format ( stack.peek() ) ) # This code is contributed by Blinkii |
C#
// C# program to retrieve original elements of the // from a Stack which returns the minimum element // in O(1) time and O(1) space using System; public class Stack { Node top; // Stores minimum element of the stack public int minimum; // Function to push an element public 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 public 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 public 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 public 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; } Console.Write(val + " " ); ptr = ptr.getNext(); if (ptr == null ) break ; } Console.WriteLine(); } else Console.WriteLine( "Empty!" ); } // Returns minimum of Stack public int getMin() { return minimum; } public bool isEmpty() { return top == null ; } } // Node class which contains data // and pointer to next node public class Node { public int data; public Node next; public Node() { data = -1; next = null ; } public Node( int d) { data = d; next = null ; } public void setData( int data) { this .data = data; } public void setNext(Node next) { this .next = next; } public Node getNext() { return next; } public int getData() { return data; } } // Driver Code public class MainClass { 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 Console.WriteLine( "Elements in the stack are:" ); stack.printAll(); // Print current minimum element if stack is // not empty Console.WriteLine(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 Console.WriteLine( "Stack after adding new elements:" ); stack.printAll(); // Print current minimum element if stack is // not empty Console.WriteLine(stack.isEmpty() ? "Empty Stack!" : "Minimum: " + stack.getMin()); // Pop elements from the stack node = stack.pop(); if (node == null ) Console.WriteLine( "Element Popped: " + "Empty!" ); else Console.WriteLine( "Element Popped: " +node.getData()); node = stack.pop(); if (node == null ) Console.WriteLine( "Element Popped: " + "Empty!" ); else Console.WriteLine( "Element Popped: " +node.getData()); // Printing stack after popping elements Console.WriteLine( "Stack after removing top two elements:" ); stack.printAll(); // Printing current Minimum element in the stack Console.WriteLine(stack.isEmpty() ? "Empty Stack!" : "Minimum: " + stack.getMin()); // Printing top element of the stack node = stack.peek(); if (node == null ) Console.WriteLine( "Top: " + "Empty!" ); else Console.WriteLine( "Top: " +node.getData()); } } // This code is contributed by Rajput-Ji |
C++
// Cpp program to retrieve original elements of the // from a Stack which returns the minimum element // in O(1) time and O(1) space #include<bits/stdc++.h> using namespace std; // Node class which contains data // and pointer to next node class Node { public : 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; } }; class Stack{ public : 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; } cout << val << " " ; ptr = ptr->getNext(); if (ptr == NULL) break ; } cout << '' ; } else cout << "Empty!" ; } // Returns minimum of Stack int getMin() { return minimum; } bool isEmpty() { return top == NULL; } }; int main() { Stack* stack = new Stack(); Node* node; stack->push( new Node(5)); stack->push( new Node(3)); stack->push( new Node(4)); // Calls the method to print the stack cout << "Elements in the stack are:" ; stack->printAll(); // Print current minimum element if stack is // not empty if (stack->isEmpty()) cout << "Empty Stack!" ; else cout << "Minimum: " << stack->getMin() << '' ; // Push new elements into the stack stack->push( new Node(1)); stack->push( new Node(2)); // Printing the stack cout << "Stack after adding new elements:" ; stack->printAll(); // Print current minimum element if stack is // not empty if (stack->isEmpty()) cout << "Empty Stack!" ; else cout << "Minimum: " << stack->getMin() << '' ; // Pop elements from the stack node = stack->pop(); cout << "Element Popped: " ; if (node == NULL) cout << "Empty!" ; else cout << node->getData() << '' ; node = stack->pop(); cout << "Element Popped: " ; if (node == NULL) cout << "Empty!" ; else cout << node->getData() << '' ; // Printing stack after popping elements cout << "Stack after removing top two elements:" ; stack->printAll(); // Printing current Minimum element in the stack if (stack->isEmpty()) cout << "Empty Stack!" ; else cout << "Minimum: " << stack->getMin() << '' ; // Printing top element of the stack node = stack->peek(); cout << "Top: " ; if (node == NULL) cout << "Empty!" ; else cout << node->getData() << '' ; return 0; } |
输出：
Elements in the stack are:4 3 5 Minimum: 3Stack after adding new elements:2 1 4 3 5 Minimum: 1Element Popped: 2Element Popped: 1Stack after removing top two elements:4 3 5 Minimum: 3Top: 4
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
