Как найти максимальный элемент стека - Autoru.top

Improve Article

Save Article

Like Article

Read

Discuss

Improve Article

Save Article

Like Article

Given a Stack, keep track of the maximum value in it. The maximum value may be the top element of the stack, but once a new element is pushed or an element is popped from the stack, the maximum element will be now from the rest of the elements.

Examples:

Input : 4 19 7 14 20
Output : Max Values in stack are

4 19 19 19 20

Input : 40 19 7 14 20 5
Output : Max Values in stack are

40 40 40 40 40 40

Method 1 (Brute-force):

We keep pushing the elements in the main stack and whenever we are asked to return the maximum element, we traverse the stack and print the max element.

Time Complexity : O(n)
Auxiliary Space : O(1)

Method 2 (Efficient): An efficient approach would be to maintain an auxiliary stack while pushing element in the main stack. This auxiliary stack will keep track of the maximum element.

Below is the step by step algorithm to do this:

Create an auxiliary stack, say ‘trackStack’ to keep the track of maximum element

Push the first element to both mainStack and the trackStack.

Now from the second element, push the element to the main stack. Compare the element with the top element of the track stack, if the current element is greater than the top of trackStack then push the current element to trackStack otherwise push the top element of trackStack again into it.

If we pop an element from the main stack, then pop an element from the trackStack as well.

Now to compute the maximum of the main stack at any point, we can simply print the top element of Track stack.

Step by step explanation :

Suppose the elements are pushed on to the stack in the order {4, 2, 14, 1, 18}

Step 1 : Push 4, Current max : 4

Step 2 : Push 2, Current max : 4

Step 3 : Push 14, Current max : 14

Step 4 : Push 1, Current max : 14

Step 5 : Push 18, Current max : 18

Step 6 : Pop 18, Current max : 14

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

class StackWithMax

{

stack<int> mainStack;

stack<int> trackStack;

public:

void push(int x)

{

mainStack.push(x);

if (mainStack.size() == 1)

{

trackStack.push(x);

return;

}

if (x > trackStack.top())

trackStack.push(x);

else

trackStack.push(trackStack.top());

}

int getMax()

{

return trackStack.top();

}

void pop()

{

mainStack.pop();

trackStack.pop();

}

};

int main()

{

StackWithMax s;

s.push(20);

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

s.push(10);

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

s.push(50);

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

return 0;

}

Java

import java.util.*;

class GfG {

static class StackWithMax

{

static Stack<Integer> mainStack = new Stack<Integer> ();

static Stack<Integer> trackStack = new Stack<Integer> ();

static void push(int x)

{

mainStack.push(x);

if (mainStack.size() == 1)

{

trackStack.push(x);

return;

}

if (x > trackStack.peek())

trackStack.push(x);

else

trackStack.push(trackStack.peek());

}

static int getMax()

{

return trackStack.peek();

}

static void pop()

{

mainStack.pop();

trackStack.pop();

}

};

public static void main(String[] args)

{

StackWithMax s = new StackWithMax();

s.push(20);

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

s.push(10);

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

s.push(50);

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

}

Python3

class StackWithMax:

def __init__(self):

self.mainStack = []

self.trackStack = []

def push(self, x):

self.mainStack.append(x)

if (len(self.mainStack) == 1):

self.trackStack.append(x)

return

if (x > self.trackStack[-1]):

self.trackStack.append(x)

else:

self.trackStack.append(self.trackStack[-1])

def getMax(self):

return self.trackStack[-1]

def pop(self):

self.mainStack.pop()

self.trackStack.pop()

if __name__ == '__main__':

s = StackWithMax()

s.push(20)

print(s.getMax())

s.push(10)

print(s.getMax())

s.push(50)

print(s.getMax())

C#

using System;

using System.Collections.Generic;

class GfG

{

public class StackWithMax

{

static Stack<int> mainStack = new Stack<int> ();

static Stack<int> trackStack = new Stack<int> ();

public void push(int x)

{

mainStack.Push(x);

if (mainStack.Count == 1)

{

trackStack.Push(x);

return;

}

if (x > trackStack.Peek())

trackStack.Push(x);

else

trackStack.Push(trackStack.Peek());

}

public int getMax()

{

return trackStack.Peek();

}

public void pop()

{

mainStack.Pop();

trackStack.Pop();

}

};

public static void Main()

{

StackWithMax s = new StackWithMax();

s.push(20);

Console.WriteLine(s.getMax());

s.push(10);

Console.WriteLine(s.getMax());

s.push(50);

Console.WriteLine(s.getMax());

}

Javascript

<script>

let mainStack = [];

let trackStack = [];

function push(x)

{

mainStack.push(x);

if (mainStack.length == 1)

{

trackStack.push(x);

return;

}

if (x > trackStack[trackStack.length - 1])

trackStack.push(x);

else

trackStack.push(trackStack[trackStack.length - 1]);

}

function getMax()

{

return trackStack[trackStack.length - 1];

}

function pop()

{

mainStack.pop();

trackStack.pop();

}

push(20);

document.write(getMax() + "</br>");

push(10);

document.write(getMax() + "</br>");

push(50);

document.write(getMax());

</script>

Time Complexity : O(1)
Auxiliary Complexity : O(n)

This article is contributed by Rohit. If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.

Last Updated :
16 Feb, 2023

Like Article

Save Article

Источник

Hello Everyone!

In this tutorial, we will learn about the working of a Stack and Finding it’s Maximum element in the C++ programming language.

To understand the basic functionality of the Stack, we will recommend you to visit the Stack Data Structure, where we have explained this concept in detail from scratch.

For a better understanding of its implementation, refer to the well-commented C++ code given below.

Code:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

//Function to print the Maximum element in the stack
void findMax(stack<int> s)
{
    int m = s.top(); //initialization

    int a;

    while (!s.empty())
    {
        a = s.top();

        if (m < a)
            m = a; //Storing the maximum element in m

        s.pop(); //removing the topmost element to bring next element at the top
    }

    cout << "nnThe maximum element of the Stack is: " << m << endl;
}

//Function to print the elements of the stack
void show(stack<int> s)
{
    while (!s.empty())
    {
        cout << "  " << s.top(); //printing the topmost element
        s.pop();                 //removing the topmost element to bring next element at the top
    }

    cout << endl;
}

int main()
{
    cout << "nnWelcome to Studytonight :-)nnn";
    cout << " =====  Program to Find the Maximum element in the Stack, in CPP  ===== nn";

    int i;

    //Stack declaration (stack of integers)
    stack<int> s;

    //Filling the elements by using the push() method.
    cout << "Filling the Stack in LIFO order using the push() method:"; //LIFO= Last In First Out

    s.push(4);
    s.push(2);
    s.push(20);
    s.push(12);
    s.push(52);
    s.push(14);

    cout << "nnThe elements of the Stack in LIFO order are: ";
    show(s);

    findMax(s); //to find the max element

    cout << "nnn";

    return 0;
}

Output:

We hope that this post helped you develop a better understanding of the concept of Stack and its implementation in C++. For any query, feel free to reach out to us via the comments section down below.

Keep Learning : )

Источник

Найти максимум в стеке за время O(1)

Можно ли найти максимальный элемент в контейнере, в частности в стеке, не организуя дополнительного прохода по нему? Да, но за это, конечно, придётся заплатить дополнительным объёмом хранимой информации.

Идея состоит в том, чтобы вместе с элементом помещать в стек дополнительное поле «локального максимума», найденного к этому моменту.

Тогда нам остаётся вернуть при поиске максимума запись, находящуюся по фиксированному адресу памяти.

Можно было, наверное, попытаться обойтись и одной дополнительной переменной, включённой в класс стека, просто сравнивая с ней вставляемый элемент и, при необходимости, запоминая новый максимум. Но как быть при удалении элемента, совпадающего с максимальным, чтобы не делать нового прохода по стеку? Думаю, математика может помочь решить и эту проблему, подумайте над ней сами

Вот листинг консольной программы, решающей задачу с помощью поля «локального максимума». Проверялась она в Visual Studio 2015.

#include <iostream> 
#include <climits> 
using namespace std;

struct record {
 int val, currentMax; //Элемент и локальный максимум
};

class Stack {
private:
 struct record *data; //Указатель на данные стека
 int size, top; //Размер и вершина стека
public:
 Stack(int);
 void push(int);
 int pop();
 int max();
};

Stack::Stack(int n) { //Создать стек
 size = n;
 data = new record[n];
 top = -1;
}

void Stack::push(int n) { //Поместить элемент в стек
 if (top == size - 1) {
  cout << "stack is full" << endl; return;
 }
 top++;
 if (top == 0) {
  data[top].val = n;
  data[top].currentMax = n;
 }
 else {
  if (data[top - 1].currentMax > n) {
   data[top].val = n;
   data[top].currentMax = data[top - 1].currentMax;
  }
  else {
   data[top].val = n;
   data[top].currentMax = n;
  }
 }
 cout << n << " item was pushed in stack" << endl;
 return;
}

int Stack::pop() { //Удалить элемент из стека
 if (top == -1) {
  cout << "stack is empty" << endl; return INT_MAX;
 }
 int item = data[top].val;
 top--;
 cout << item << " item was popped from stack" << endl;
 return item;
}

int Stack::max() { //Найти максимум за время O(1)
 if (top == -1) {
  cout << "stack is empty" << endl; return INT_MAX;
 }
 cout << "maximum val in the stack is " << data[top].currentMax << endl;
 return data[top].currentMax;
}

int main() {
 Stack S1(5);

 S1.push(2);
 S1.push(6);
 S1.push(11);
 S1.push(3);
 S1.push(12);
 S1.max();
 S1.pop();
 S1.max();
 cin.get(); return 0;
}

01.04.2019, 09:05 [3456 просмотров]

К этой статье пока нет комментариев, Ваш будет первым

Источник

Edit:

without iterating over the Stack

does not actually prohibit all iteration. Rather, the question only prohibits doing the simple

for (Integer i : lifo)

Thus, this solution satisfies the question’s limitations.

Just empty a copy of the stack. pop each of the elements from the copy, checking for max against an integer all the while.

Stack<Integer> lifoCopy = (Stack<Integer>) lifo.clone();
int max = Integer.MIN_VALUE;

while (!lifoCopy.isEmpty())
{
    max = Math.max(lifoCopy.pop(), max);
}

System.out.println("max=" + max.toString());

This will work for you in O(n) time even if your interviewers decide to be more restrictive and not allow more built in functions (max, min, sort, etc.).

Additionally, if you need to have the original unharmed, but can’t use clone, you can do so with an extra stack:

Stack<Integer> reverseLifo = new Stack<Integer>();
int max = Integer.MIN_VALUE;

while (!lifo.isEmpty())
{
    int val = lifo.pop();

    max = Math.max(val, max);

    reverseLifo.push(val);
}

while (!reverseLifo.isEmpty())
{
    lifo.push(reverseLifo.pop());
}

System.out.println("max=" + max.toString());

Finally, this assumes that comparison against a temp variable is acceptable. If no comparison is allowed at all, then this solution in conjunction with this method will work.

Источник

Suppose there are 50000+ integer entries in a Stack? How to efficiently find out a maximum or minimum in it?
Stack can grow or reduce i.e., pop() and push(), but we need to keep track of max and min value in the stack?

asked Oct 29, 2014 at 8:54

As Mischel pointed out, Stack with find-min/find-max more efficient than O(n)?, already answers the question.

However that response suggests that you need to store each and every max and min at each point in the stack. A better solution would be to have a separate stack for the max and the min. For the max stack you will push a new element onto the max stack only if the new element is greater than the current max, and vice-versa for min. You will pop elements of the min and max stacks when the element that you are popping of the main stack is equal to them and not equal to the next element in the main stack.

Note that this requires O(n) extra space while providing O(1) operations.