• 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

DFS (Depth First Search)

How Radix sort works

Implement a generic binary search algorithm for Integer Double String etc

HackeEarth Flipkart’s Drone

Spanning Tree

Coin Collection Dynamic Programming

Reliance Jio Software Developer Interview Experience

ADOBE Aptitude C Language Test

Python Dictionaries

Sort an array according to the order defined by another array

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

Find the element that appears once others appears thrice

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

1014 Practice Question of New GRE – Princeton

flattens 2 D linked list to a single sorted link list

Maximum occurred Smallest integer in n ranges

Generate next palindrome number

Find position of the only set bit

Get K Max and Delete K Max in stream of incoming integers

Python List

Reversal of LinkedList

Number of Islands BFS/DFS

Singly linked list

Printing intermediate Integers between one element & next element of array

C++ OOPs Part2

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

BFS (Breath First Search)

Print vertical sum of all the axis in the given binary tree

How strtok() Works

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Copyright © 2025 · Genesis Framework · WordPress · Log in