Maximum Element

Problem Information:

problem's link

AC date : 2017-04-23

Category : data structure->stack


Question

You have an empty sequence, and you will be given queries. Each query is one of these three types:

1 x -Push the element x into the stack.

2 -Delete the element present at the top of the stack.

3 -Print the maximum element in the stack.

Input Format

The first line of input contains an integer, \(N\) . The next \(N\) lines each contain an above mentioned query. (It is guaranteed that each query is valid.)

Constraints

  • \(1 \le N \le 10^5\)
  • \(1 \le x \le 10^5\)
  • \(1 \le type \le 3\)

Output Format

For each type query, print the maximum element in the stack on a new line.

Sample Input

10

1 97

2

1 20

2

1 26

1 20

2

3

1 91

3

Sample Output

26

91

Answer

The most valuable part is the implementation of stack. Alt text

C++

#head.h

using namespace std;

typedef struct Node{
    int data;
    Node * next;
}Node;

class Stack{
private:
    Node * top;
    int max;
    int findMax(Node *);
    void clear();
public:
    Stack();
    ~Stack();
    void push(int x);
    void pop();
    void printMax();
};

Stack::Stack():top(NULL), max(0){

}

Stack::~Stack(){
    clear();
}

void Stack::push(int x){
    Node * newTop = new Node;
    newTop->data = x;
    newTop->next = top;
    top = newTop;
    max = x > max? x:max;
}

void Stack::pop(){
    Node * temp = top;
    if(top->data==max){
        max = findMax(top->next);
    }
    top = top->next;
    free(temp);
}

void Stack::printMax(){
    cout<<max<<endl;
}

int Stack::findMax(Node * topItem){
    Node * temp = topItem;
    int tempMax = 0;
    while(temp!=NULL){
        tempMax = tempMax > temp->data?tempMax:temp->data;
        temp=temp->next;
    }
    return tempMax;
}

void Stack::clear(){
    while (top)
    {
        Node* topOfStack = top;
        top = top->next;
        delete topOfStack;

    }
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int N = 0;
    int type, x;
    Stack s;

    cin>>N;

    while(N--){
        cin >> type;
        if( type == 1 ){
            cin >> x;
            s.push(x);
        }
        else if( type == 2 ){
            s.pop();
        }
        else if( type == 3 )
            s.printMax();
    }
    return 0;
}

上一篇: Algorithmic Crush
下一篇: Tree-Preorder Traversal

发布时间:
2017-04-23 17:06
分类:
标签: