• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Sort Stack in place

November 23, 2014 by Dhaval Dave

Question is to sort a Stack in place without using extra Stack or other Data Structure.Answer :
Basic solution which comes in mind is to pop all element and sort and push into Stack again.
but as we don’t have extra space or Data Structure to sort stack.
We need to use inplace sorting, and to do so we need to have all elements out of stack.
One way to do so is to use “Recursion” .
It will use internally memory stack to store recursion values. but we can implement without initializing extra stack or memory.

Logic :

1) Recursively call function and pop all data.
2) Once stack is empty, Push last data.
3) While pushing data into stack pop top data and check for order.
4) Recursively call Sort function again and Push data finally.

Code :

#include <iostream>
#include <stack>
using namespace std;

void StackSort(int nTop, stack<int>& S);
//Step1
void StackSortUtil(stack<int>& S)
{
    for(int i=0;i<S.size(); ++i)
{
int nTop = S.top();
S.pop();
StackSort(nTop, S);
}
}

void StackSort(int nTop, stack<int>& S)
{
//Step2
if(S.size() == 0)
{
S.push(nTop);
return;
}
//Step3
int nT = S.top();
if(nT > nTop)
{
int i = nTop;
nTop = nT;
nT = i;
}
//Step4
S.pop();
StackSort(nT,S);
S.push(nTop);
}
int printStack(stack <int>& S)
{
    while( ! S.empty()) {
        cout<< S.top() <<“n”;
        S.pop();
    }
}
int main()
{
std::stack<int> Stk;
Stk.push(10);
Stk.push(13);
Stk.push(41);
Stk.push(72);
Stk.push(15);

StackSortUtil(Stk);
        cout << “==Stack in decending order==n”;
        printStack(Stk);
return 0;
}
If you want to share such question , solution  or your experience of any company, Please do share at admin@gohired.in , As sharing is caring
http://ideone.com/cUS2sO

Similar Articles

Filed Under: Amazon Interview Question, Data Structure, problem

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Doubly linked list

ADOBE Aptitude C Language Test

Find min element in Sorted Rotated Array (With Duplicates)

Find the number ABCD such that when multipled by 4 gives DCBA.

Fibonacci Hashing & Fastest Hashtable

Coin Collection Dynamic Programming

Generic Object Oriented Stack with Template

25 horses 5 tracks Find 3 fastest puzzle

Maximum sum contiguous subarray of an Array

Given Set of words or A String find whether chain is possible from these words or not

Find if a binary tree is height balanced ?

LeetCode: Container With Most Water

Count number of ways to reach a given score in a game

Amazon Interview Experience – SDE Chennai

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

Spanning Tree

LeetCode : Word Search

Closed Parentheses checker

Cisco Hiring Event 21st – 22nd Feb 2015

Urban Ladder Written Test.

Find the kth number with prime factors 3, 5 and 7

Handle duplicates in Binary Search Tree

Generate largest number arranging a no. of given non negative integer numbers

Print Power Set of a Set

Reversal of LinkedList

Generate next palindrome number

The greedy coins game Dynamic Programming

Linked List V/S Binary Search Tree

Check if an array has duplicate numbers in O(n) time and O(1) space

Minimum insertions to form a palindrome

Copyright © 2025 · Genesis Framework · WordPress · Log in