Leetcode: Implement Stack using Queues

Implement Stack using Queues

My Submissions

Total Accepted: 28206 Total Submissions: 92981 Difficulty: Easy

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Notes:

• You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
• Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
• You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

Update (2015-06-11):
The class name of the Java function had been updated to MyStack instead of Stack.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and all test cases.

Subscribe to see which companies asked this question

Hide Tags

 Stack Design

Show Similar Problems

------------------------------------------------------------------------

stack.pop() using queue.pop():

using queue to push its front values to back until the original back one! Then pop the current front one.


////////////////////////////////////////////////////////////////////////////
class Stack {
public:
    queue<int> que;
    // Push element x onto stack.
    void push(int x) {
        que.push(x);
    }

    // Removes the element on top of the stack.
    void pop() {
        //using queue itself to push all front values to back until the last one
        for (int i=0;i<que.size()-1;i++){
            que.push(que.front());
            que.pop();
        }
        que.pop();
    }

    // Get the top element.
    int top() {
        return que.back();
    }

    // Return whether the stack is empty.
    bool empty() {
        return que.empty();
    }
};

Leetcode: Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation

My Submissions

Total Accepted: 57639 Total Submissions: 254722 Difficulty: Medium

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Subscribe to see which companies asked this question

Hide Tags

 Stack

Show Similar Problems

----------------------------------------------------------------------------------

思路：

典型的stack问题。逐一扫描每个token，如果是数字，则push入stack，如果是运算符，则从stack中pop出两个数字，进行运算，将结果push回stack。最后留在stack里的数即为最终结果。

以题中例子说明

exp:     2    1      +    3      *

stack:   2    2,1   3    3,3   9

///////////////////////////////////////////////////////////////////////

class Solution {

 public:

        int evalRPN(vector<string>& tokens) {

               stack<int> tokTmp;

               for (int i = 0; i<tokens.size(); i++){

                      //tokens[i] is a string, so "" is used!

                      if ((tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/")){

                            int y = tokTmp.top();

                            tokTmp.pop();

                            int x = tokTmp.top();

                            tokTmp.pop();

                            if (tokens[i] == "+")tokTmp.push(x + y);

                            else if (tokens[i] == "-")tokTmp.push(x - y);

                            else if (tokens[i] == "*")tokTmp.push(x*y);

                            else if (tokens[i] == "/")tokTmp.push(x / y);

                      }

                      else {

                            int x = stoi(tokens[i], nullptr, 10);

                            tokTmp.push(x);

                      }

               }

               return tokTmp.top();

        }

 };

Leetcode: Min Stack

 Min Stack

My Submissions

Total Accepted: 57566 Total Submissions: 271279 Difficulty: Easy

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Subscribe to see which companies asked this question

Hide Tags

 Stack Design

Show Similar Problems

--------------------------------------------------------------------------
Keep two stacks inside: one store all and the other store the minimal.
Note: only the current x is smaller or equal to the mimStack.top() is saved.



///////////////////////////////////////////////////////////
class MinStack {

public:
    void push(int x) {
        curSta.push(x);
        if(minSta.empty() || x<=minSta.top() )
           minSta.push(x);
    }

    void pop() {
       
        if(minSta.top() == curSta.top() )
            minSta.pop();
        curSta.pop(); //Note: this line should be put in last, otherwise, the above codes can not be compared!!!!       
    }

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

    int getMin() {
        return minSta.top();
    }
   
private:
    stack<int> minSta;
    stack<int> curSta;  
};

Leetcode: Valid Parentheses (0ms)(string)(stack)

PROBLEM:
https://leetcode.com/problems/valid-parentheses/

--------------------------------

1. using stack to temporally store the characters;
2. when meet [, {, (, push to stack;
3. when meet }, ], ), compare with the top of stack;
        if it's a pair, pop the top one (delete the top one);
        if it's not a pair, it's failed. 
4. if in the final, nothing it's left, it's true. 

See codes for details. 



/////////////////////////////////////////////////////////
// codes 0ms

class Solution {

public:

       bool isValid(string s) {

              stack<char> sta;

              sta.push('0');

              for (auto c : s){

                     switch (c) {

                     case '{':

                           sta.push('{');

                           break;

                     case '}':

                           if (sta.top() != '{') return false;

                           else sta.pop();

                           break;

                     case '[':

                           sta.push('[');

                           break;

                     case ']':

                           if (sta.top() != '[') return false;

                           else sta.pop();

                           break;

                     case '(':

                           sta.push('(');

                           break;

                     case ')':

                           if (sta.top() != '(') return false;

                           else sta.pop();

                           break;

                     default:;

                     }

              }

              if (sta.top() == '0')return true;

              else return false;

       }

};

Leetcode:Trapping Rain Water (8ms) Analysis & solution

PROBLEM:

Given n non-negative integers representing an elevation map where the width of each bar is 1, 

compute how much water it is able to trap after raining.

For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain
water (blue section) are being trapped. Thanks Marcos for contributing this image!

Hide Tags

 Array Stack Two Pointers

Show Similar Problems

Analysis:

Method 1:

The index of  i is sweeping from left to right. Two pointers: start and end, are used to temporally store the index of a convex. Then we  do summation when the two are found. And continue until the end.....

The keys are that we need to consider all possible conditions. Three conditions should be considered in the following figure, labeled as 1~3:

If you can cover all above cases, it's not difficult to coding. Usually, it's really difficult to identify all possible cases when start to coding. Problem arises when new case appear. So lots of time were wasted on finding the cases. I don't think it's a good problem to enhance the coding ability! 
Therefore, don't waste your time on this method!!

Method 2:
Another smarter method is:
1. find out the index of largest item
2. for left part of the index, the trapped water for each unit depends on the left highest item.
3. for right part of the index, the trapped water for each unit depends on the right highest item.
see figure below:

The logic is simple and don't need to consider so many cases in method 1. So, strategy is much more important than coding itself!!

method 1:

///////////////////////////////////////////////////////////////////////////////

//codes 8ms

class Solution {

public:

       int trap(vector<int>& height) {

              int start = 0, end = -1;

              int sFlag = 0, sum = 0;

              //check input

              if (height.size()<3)return 0;

              //sweep i from left to right

              for (int i = 1; i<height.size(); i++){

                     //identify start and end

                     if (sFlag == 0 && height[i]<height[i - 1]){

                           start = i - 1;

                           sFlag = 1;

                     }

                     else if (sFlag == 1 && end == -1)end = height[i] > height[i - 1] ? i : -1;

                     //case 1

                     else if (sFlag == 1 && end !=-1)end = height[i] > height[end] ? i : end;

                     //identify when to do summation

                     if (sFlag==1 && end!=-1){

                           if (height[end] >= height[start] || (i == height.size() - 1 ))

                           {

                                  int tmp = height[start] > height[end] ? height[end] : height[start];//choose the lower lever

                                   for (int j = start+1; j<end; j++){

                                         int sTmp = (tmp - height[j]) > 0 ? (tmp - height[j]) : 0;//case 2: prevent negtive value

                                         sum += sTmp;

                                  }

                                  //case 3

                                  if (i == height.size() - 1 && end != height.size() - 1){

                                         i = end - 1;

                                  }

                                  sFlag = 0;

                                  end = -1;

                           }

                     }

              }

              return sum;

       }

};

//////////////////////////////////////

method 2

////////////////////////////////////////

class Solution {
public:
       /*
        //function of finding the highest value in ...
        int findHighest(int left, int right, vector<int>& height){
            int maxH=0;
            for (int i=left;i<=right;i++){
                if(height[i]>maxH)maxH=height[i];
            }
            return maxH;
        }
        */

    int trap(vector<int>& height) {
        //corner case
        if (height.size()<3)return 0;

        //find the highest point
        int hMax=height[0], idx=0;
        for (int i=0;i<height.size();i++){
            if (height[i]>hMax) {hMax=height[i]; idx=i;}
        }
        
        int sum=0, maxTmp=height[0];
        //for left part
        for (int i=1;i<idx;i++){
            if (height[i]>maxTmp){
                maxTmp=height[i];
            }
            sum=maxTmp-height[i] >0 ?sum+maxTmp-height[i]:sum;
        }
        
        
        //for right part
        maxTmp=height[height.size()-1];
        for (int i=height.size()-1;i>idx;i--){
            
            
            if (height[i]>maxTmp){
                maxTmp=height[i];
            }
            sum=maxTmp-height[i] >0 ?sum+maxTmp-height[i]:sum;
        }        
        
        
        /*
        //for left part
        int sum=0;
        for (int l=idx-1;l>0;l--){
            int tmpMax=findHighest(0,l,height);
            sum=tmpMax-height[l] >0 ?sum+tmpMax-height[l]:sum;
            
        }
        //for right part
        for (int r=idx+1;r<height.size();r++){
            int tmpMax=findHighest(r,height.size()-1,height);
            sum=tmpMax-height[r] >0 ?sum+tmpMax-height[r]:sum;
            
        }        
        */
        return sum;
  
        
    }

};