Exercises: 232. Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Solution: take advantage of the features of both stacks

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
    }

    /** Push element x to the back of queue. */
    void push(int x) {
        sta0.push( x );
    }

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        while( !sta0.empty() ){
            sta1.push( sta0.top() );
            sta0.pop();
        }
        int ans = sta1.top();
        sta1.pop();

        while( !sta1.empty() ){
            sta0.push( sta1.top() );
            sta1.pop();
        }

        return ans;
    }

    /** Get the front element. */
    int peek() {
        while( !sta0.empty() ){
            sta1.push( sta0.top() );
            sta0.pop();
        }
        int ans = sta1.top();

        while( !sta1.empty() ){
            sta0.push( sta1.top() );
            sta1.pop();
        }

        return ans;
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return sta0.empty();
    }
protected:
    stack<int> sta0;
    stack<int> sta1;
};

int main()
{
    MyQueue *obj = new MyQueue();
    obj->push(1);
    obj->push(2);
    cout << obj->peek() << endl;
    cout << obj->empty() << endl;
    delete obj;
    return 0;
}

Exercises: 155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Solution: store min value in an another stack when push a new number. Pop the top value if the last value is min value. Get the minimum element from the min stack.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int val) {
        nums.push( val );
        if( mins.size() == 0 ){
            mins.push( val );
        }
        else{
            if( val <= mins.top() ){
                mins.push( val );
            }
        }
    }

    void pop() {
        if( nums.size() == 0 ) return ;

        if( nums.top() == mins.top() ){
            mins.pop();
        }
        nums.pop();
    }

    int top() {
        return nums.top();
    }

    int getMin() {
        return mins.top();
    }
protected:
    stack<int> nums;
    stack<int> mins;
};

int main()
{
    MinStack *obj = new MinStack();
    obj->push(-2);
    obj->push(0);
    obj->push(-3);
    cout << obj->getMin() << endl;
    obj->pop();
    cout << obj->top() << endl;
    cout << obj->getMin() << endl;
    delete obj;
    return 0;
}

Exercises: 20. Valid Parentheses

Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

Solution: use stack to compare the lastest char and the new char.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

class Solution {
public:
    bool IsValidPair( char ch0, char ch1 ){
        if( ch0 == '(' && ch1 == ')' ){
            return true;
        }
        if( ch0 == '{' && ch1 == '}' ){
            return true;
        }
        if( ch0 == '[' && ch1 == ']' ){
            return true;
        }
        return false;
    }
    bool isValid(string s) {
        for( auto ch: s ){
            if( charStack.size() && IsValidPair( charStack.top(), ch ) ){
                charStack.pop();
            }
            else {
                charStack.push( ch );
            }
        }
        return charStack.size() == 0;
    }
protected:
    stack<char> charStack;
};

int main()
{
    Solution *obj = new Solution();
    cout << obj->isValid( "()[]{}" ) << endl;
    delete obj;
    return 0;
}

Exercises: 739. Daily Temperatures

Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] 0 instead.

Solution: check the old values and set the number of the days when a new temperature comes.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> ans;
        for( auto value: temperatures )
        {
            ans.push_back( 0 );
            for( int j = ans.size() - 2; j >= 0; --j ){
                if( temperatures[j] >= value ){
                    break;
                }
                if( ans[j] == 0 && value > temperatures[j] ){
                    ans[j] = ans.size() - 1 - j;
                }
            }
        }
        return ans;
    }
};

int main()
{
    Solution *obj = new Solution();
    vector<int> vec{ 73, 74, 75, 71, 69, 72, 76, 73 };
    auto ans = obj->dailyTemperatures( vec );
    for( auto element: ans ){
        cout << element << "\t";
    }
    delete obj;
    return 0;
}

Exercises: 23. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.Merge all the linked-lists into one sorted linked-list and return it.

Solution: use priority_queue to sort all elements and generate a list.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue <int,vector<int>,greater<int> > q;
        for( auto myList: lists ){
            while( myList ){
                q.push( myList->val );
                myList = myList->next;
            }
        }
        if( q.empty() ){
            return nullptr;
        }
        ListNode *head = new ListNode( q.top() );
        ListNode *pointer = head;
        q.pop();
        while( !q.empty() ){
            pointer->next = new ListNode( q.top() );
            q.pop();
            pointer = pointer->next;
        }

        return head;
    }
};

int main()
{
    Solution *obj = new Solution();
    ListNode *list1 = new ListNode( 1 );
    ListNode *tmp = new ListNode( 4 );
    list1->next = tmp;
    tmp = new ListNode( 5 );
    list1->next->next = tmp;

    vector<ListNode*> lists;
    lists.push_back( list1 );
    ListNode *nums = obj->mergeKLists( lists );
    while( nums ){
        cout << nums->val << "\t";
        nums = nums->next;
    }

    delete obj;
    return 0;
}

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

3D Model Viewer: add grid plane and convex hull.
Add google translate tool at right-bottom position.

X
A prohibited operation
0
Would love your thoughts, please comment.x
()
x