Sort the stack #stack #sorting #data_structure #leetcode
#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);
}
}