leetcode
  • LeetCode Problems
  • Array
    • Array Partition I
    • Toeplitz Matrix
    • Find All Numbers Disappeared in an Array
    • Max Area of Island
    • Move Zeros
    • Two Sum II - Input array is sorted
    • Degree of an Array
    • Image Smoother
    • Positions of Large Groups
    • Missing Number
    • Maximum Product of Three Numbers
    • Min Cost Climbing Stairs
    • Longest Continuous Increasing Subsequence
    • Remove Element
    • Pascal's Triangle
    • Maximum Subarray
    • Largest Number At Least Twice of Others
    • Search Insert Position
    • Plus One
    • Find Pivot Index
    • Pascal's Triangle II
    • Two Sum
    • Maximize Distance to Closest Person
    • Maximum Average Subarray I
    • Remove Duplicates from Sorted Array
    • Magic Squares In Grid
    • Contains Duplicate II
    • Merge Sorted Array
    • Can Place Flowers
    • Shortest Unsorted Continuous Subarray
    • K-diff Pairs in an Array
    • Third Maximum Number
    • Rotate Array
    • Non-decreasing Array
    • Find All Duplicates in an Array
    • Teemo Attacking
    • Beautiful Arrangement II
    • Product of Array Except Self
    • Max Chunks To Make Sorted
    • Subsets
    • Best Time to Buy and Sell Stock with Transaction Fee
    • Combination Sum III
    • Find the Duplicate Number
    • Unique Paths
    • Rotate Image
    • My Calendar I
    • Spiral Matrix II
    • Combination Sum
    • Task Scheduler
    • Valid Triangle Number
    • Minimum Path Sum
    • Number of Subarrays with Bounded Maximum
    • Insert Delete GetRandom O(1)
    • Find Minimum in Rotated Sorted Array
    • Sort Colors
    • Find Peak Element
    • Subarray Sum Equals K
    • Subsets II
    • Maximum Swap
    • Remove Duplicates from Sorted Array II
    • Maximum Length of Repeated Subarray
    • Image Overlap
    • Length of Longest Fibonacci Subsequence
  • Contest
    • Binary Gap
    • Advantage Shuffle
    • Minimum Number of Refueling Stops
    • Reordered Power of 2
  • Dynamic Programming
    • Climbing Stairs
    • Range Sum Query - Immutable
    • Counting Bits
    • Arithmetic Slices
    • Palindromic Substrings
    • Minimum ASCII Delete Sum for Two Strings
    • Maximum Length of Pair Chain
    • Integer Break
    • Shopping Offers
    • Count Numbers with Unique Digits
    • 2 Keys Keyboard
    • Predict the Winner
    • Stone Game
    • Is Subsequence
    • Delete and Earn
    • Longest Palindromic Subsequence
    • Target Sum
    • Unique Binary Search Trees
    • Minimum Path Sum
    • Combination Sum IV
    • Best Time to Buy and Sell Stock with Cooldown
    • Largest Sum of Averages
    • Largest Plus Sign
    • Untitled
  • Invert Binary Tree
  • Intersection of Two Arrays
  • Surface Area of 3D Shapes
  • K Closest Points to Origin
  • Rotting Oranges
  • Smallest Integer Divisible by K
  • Duplicate Zeros
  • DI String Match
  • Implement Queue using Stacks
  • Increasing Order Search Tree
  • Reveal Cards In Increasing Order
  • Reshape the Matrix
  • Partition List
  • Total Hamming Distance
  • Validate Binary Search Tree
  • Decode Ways
  • Construct Binary Tree from Preorder and Inorder Traversal
  • Construct Binary Search Tree from Preorder Traversal
  • Design Circular Queue
  • Network Delay Time
  • Most Frequent Subtree Sum
  • Asteroid Collision
  • Binary Tree Inorder Traversal
  • Check If Word Is Valid After Substitutions
  • Construct Binary Tree from Preorder and Postorder Traversal
  • K-Concatenation Maximum Sum
Powered by GitBook
On this page
  • Description
  • Solution

Implement Queue using Stacks

Description

Implement the following operations of a queue using stacks.

  • push(x) -- Push element x to the back of queue.

  • pop() -- Removes the element from in front of queue.

  • peek() -- Get the front element.

  • empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

  • You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.

  • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.

  • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Solution

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

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

    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if (rst.empty())
            transfer(rst, st);
        int val = rst.top();
        rst.pop();
        return val;
    }

    /** Get the front element. */
    int peek() {
        if (rst.empty())
            transfer(rst, st);
        return rst.top();
    }

    void transfer(stack<int> &s1, stack<int> &s2) {
        while (!s2.empty()) {
            s1.push(s2.top());
            s2.pop();
        }
    }

    /** Returns whether the queue is empty. */
    bool empty() {
        return st.empty() && rst.empty();
    }

    stack<int> st, rst;
};
PreviousDI String MatchNextIncreasing Order Search Tree

Last updated 5 years ago