• 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

How strtok() Works

Cisco Hiring Event 21st – 22nd Feb 2015

Practo Hiring Experience

Knight Tour Problem (Graph – Breadth First Search)

Get Minimum element in O(1) from input numbers or Stack

C++ OOPs Part1

C++ OOPs Part2

Walmart Labs Interview Experience

Add Sub Multiply very large number stored as string

Skiing on Mountains Matrix

Interfaces in C++ (Abstract Classes in C++)

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

flattens 2 D linked list to a single sorted link list

Subset Sum Problem Dynamic programming

Circular Linked List

Given a float number convert it into the string WITHOUT using any inbuilt Function

Maximum difference between two elements s.t larger element appears after the smaller number

Daughter’s Age VeryGood Puzzle

Connect n ropes with minimum cost

Naurki.com Security Breach

Templates in C++

Test Cases for Round Function

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

Print Power Set of a Set

Amazon Interview On-Campus For Internship – 1

SAP Off Campus Hiring_ March 2015 Sample Questions

Binary Tree in Java

Facebook Interview Question : Interleave List

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

Edit Distance ( Dynamic Programming )

Copyright © 2025 · Genesis Framework · WordPress · Log in