• 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

Leetcode: Merge Intervals

Find Percentage of Words matching in Two Strings

Longest Increasing Subsequence

Maximum sum contiguous subarray of an Array

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

LeetCode : Word Search

Amazon Interview On-Campus For Internship – 1

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

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

Flipkart SDET Interview Experience

Calculate price of parking from parking start end time prices

Find Nearest Minimum number in left side in O(n)

Printing each word reverse in string

CodeChef Code SGARDEN

Maximum path sum between two leaves

Edit Distance ( Dynamic Programming )

BFS (Breath First Search)

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

ADOBE Aptitude C Language Test

Skiing on Mountains Matrix

C++ OOPs Part2

Walmart Labs Interview Experience

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

Handle duplicates in Binary Search Tree

Print Power Set of a Set

SAP Hiring Off-Campus General Aptitude

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Search element in a matrix with all rows and columns in sorted order

25 horses 5 tracks Find 3 fastest puzzle

Copyright © 2025 · Genesis Framework · WordPress · Log in