Sort the stack #stack #sorting #data_structure #leetcode

SortStack.cpp

#include <cassert>
#include <iostream>
#include <stack>

// Goal:
//   Sort `s` by decreasing order, from the bottom to the top.
//   The minimal element will be at the top after sorting.
// Limit:
//   You cannot use other data structures to implement it
//   except an additional stack.
// Approach:
//   Obviously, the additional stack is used as a temporary storage.
//   If the additional stack can be kept in increasing order, from its bottom
//   to its top(The top element is the maximum), then the goal can be done when
//   we push elements from the additional stack back to the original stack.
template <class T>
void Sort(std::stack<T>& s)
{
  // The stack is sorted naturally if it's empty or has one element.
  if (s.size() < 2) {
    return;
  }

  std::stack<T> r; // Keep reverse order of the goal of `s`.

  // Assume `r` is sorted, we need to keep popping the top elements from `s`
  // and then insert them into `r`.
  while (!s.empty()) {
    // Hold the popped element outside of the two stacks.
    T i = s.top(); s.pop();

    // To search where the held element should insert into, we keep moving
    // the top elements from `r` to `s`(use `s` as the temporary storage)
    // while the held elenment is smaller than the top elements.
    unsigned int num = 0;
    while (!r.empty() && r.top() > i) {
      s.push(r.top()); r.pop();
      ++num;
    }

    // Insert the held element into the right position of `r`.
    r.push(i);

    // Move the elements from `r` in `s` back to `r`.
    while(num) {
      r.push(s.top()); s.pop();
      --num;
    }

    // So the `r` is still sorted.
  }

  // Now `r` is sorted in increasing order, from the bottom to the top.
  // The `s` will be sorted in decreasing order, from the bottom to the top,
  // after we pop all the elements from `r` and push them into `s`.
  while (!r.empty()) {
    s.push(r.top()); r.pop();
  }
}

int main()
{
  std::stack<int> s;
  int values[] = { 4, 7, 1, 9, 3, 29, 12, 34, -3, 0 -5, -7, 100, 31, 87 };
  for (unsigned int i = 0 ; i < sizeof(values)/sizeof(values[0]) ; ++i) {
    s.push(values[i]);
  }

  Sort(s);

  while(!s.empty()) {
    int k = s.top(); s.pop();
    std::cout << k << std::endl;
    assert(s.empty() || s.top() >= k);
  }
}