• 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

HackeEarth Flipkart’s Drone

Generic Object Oriented Stack with Template

K’th Largest Element in BST when modification to BST is not allowed

Maximum size of square sub matrix with all 1’s in a binary matrix

Given a string, find the first character which is non-repetitive

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

Client Server C program

SAP Interview Questions

Maximum path sum between two leaves

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Skiing on Mountains Matrix

robot standing at first cell of an M*N matrix. It can move only in two directions, right and down. In how many ways, it can reach to the last cell i.e. (M, N) Code it

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

SAP Off Campus Hiring_ March 2015 Computer Skills

BlueStone E-commerce Interview Experience

Possible sizes of bus to carry n groups of friends

Memory Efficient LinkedList

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

Implement a generic binary search algorithm for Integer Double String etc

C Program for TAIL command of UNIX

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

SAP Off Campus Hiring_ March 2015 Verbal Skills

Find the smallest window in a string containing all characters of another string

CodeChef’ RRCOPY

Printing each word reverse in string

Regular Expression Matching

1014 Practice Question of New GRE – Princeton

Coin Collection Dynamic Programming

System Design: Designing a LLD for Hotel Booking

Check Binary Tree is Binary Search Tree or not

Copyright © 2025 · Genesis Framework · WordPress · Log in