How to sort a stack using only Push, Pop, Top, IsEmpty, IsFull?
Asked Answered
S

11

7

Given a stack S, need to sort the stack using only Push, Pop, Top, IsEmpty, IsFull.

Looking for most simple solution.

Edited: Removed in place condition. Can't use another stack or queue.

Samson answered 30/1, 2010 at 17:52 Comment(20)
if this is homework, please tag it as suchResurgent
Simple. Pop everything into a vector, sort, push it all back. Version 2 gets rid of the stack because it is the wrong data structure. Doing it any other way is only interesting for homework assignments.Cerberus
@Ankit: Can you change the data structure?Lethargy
Can you use more than one stack?Loki
No cant use another stack or queue.Samson
@nobugz Use of extra array is not permitted. Wont use SO for that solution would I..Samson
This sounds like an awfully common homework problem. What kind of company or coding practice would forbid you from using additional storage? Not changing the primary data structure, sure (part of someone else's interface), but not being able to create secondary storage? Right. Admittedly, the homework presentation is solvable while yours is not. If it's not homework, why are you placing such severe restrictions on yourself?Lethargy
@ankit - this is just utter nonsense. The stack is no doubt implemented using an array, sort the frikkin array. I don't believe for a minute this is not a homework question, voting to close.Cerberus
@GMan well if you call preparing for job interviews as homework then it is that only. If you do not have a solution - its OK. Do not take it as a failure. There are many helping SO users who are trying to help me. Thanks anyways.Samson
Well if you guys have time look at link in Anthony's answer. It gives a solution that just uses two variables to sort a stack.Samson
Please do not call some one's question as 'utter nonsense'. The only thing utter non sense here is your comment. You do not own SO OK!!!!Cailly
Ankit, no, Anthony's answer uses a second stack.Listing
Presumably it is acceptable to use whatever mechanism a language provides to link the call frames together. (Yes, this is usually but not always a stack) So, write or cite a recursive solution and call it a day. It's certainly possible to solve using a fairly reasonable if not overly strict interpretation of even the original unedited condition. I did it.Spleen
We aren't making a new tag for one question, when a more suitable tag exists.Lethargy
I think a "second stack" or "in-place" simply means that you can't use another aggregate data structure of a similar size. This is a perfectly reasonable question and it has a fairly simple answer.Spleen
Wow there are an awful lot of critical people out there. Who cares if it's homework, interview, actual work, or just someong bored out of his mind deciding to write code than go on a date? The question is posed. If you don't think it's worth your precious time then don't respond, but don't waste that same precious time whining and complaining that you had to take valuable time out of your day to read about a problem you couldn't solve a few years ago.Overlook
@Joel: I can't speak for others but I personally don't care either way. What annoys me is when people ask obvious test-based question, be it homework or something else, then deny any sort of questioning or give any honest answer. Just be straight up and say it's homework/interview review/etc., not beat around it.Lethargy
@Gman: Eh. My point is. Who gives a rip? A question is a question. Do you really need to know why in order to answer it? I see a ton of questions that could be answered simply if the person typed it into Google. What I don't do (typically, but this case seems to be the exception) is waste time wonking about it. I just ignore the question and move on.Overlook
@Joel: I don't care, I wasn't the one to ask if it was homework. :P But once it was asked, the behavior bugged me.Lethargy
@Joel A point well made.Samson
S
8

It can be done...


Ok: sorted, ahem, "in-place" with only the listed ops, didn't need Top() or IsFull() or another stack or data structure other than the call frames. (Presumably the whole point of the homework problem was to require a recursive solution.)

Ruby

@a = [3, 2, 1, 6, 5, 4]

class Array
  def empty?
    return size == 0
  end
end

def sort e
  if @a.empty?
    @a.push e
    return
  end
  t = @a.pop
  if e > t
    @a.push(t).push(e)
    return
  end
  sort e
  @a.push t
end

def resort
  return if @a.empty?
  t = @a.pop
  resort
  sort t
end

p ['first ', @a]
resort
p ['final ', @a]
Spleen answered 30/1, 2010 at 20:26 Comment(3)
So this one works by defining two sort functions: resort which does not assume that the stack is already sorted and sort which does. Both work by recursively popping an element off until their goal is reached. In the case of the top-level resort, it's goal is to remove everything and build it back up by calling sort, and sort works by recursing just far enough to push a single element. I have to think a solution like this was the point of the exercise.Spleen
You are using extra memory; surely not explicitly organized as a stack (rather hidden in the call stack) but I'm curious if the OP's satisfied.Sal
Sure, but I think that was intended. Maybe this solution would be obvious to some people, but I had to think a bit to get this. It's a fun problem and I suspect it was designed to require pretty much this solution.Spleen
K
12

For this problem, can we consider using system stack? Make several recursive calls.

public static void sort(Stack<Integer> s) {
    if (!s.isEmpty()) {
        Integer t = s.pop();
        sort(s);
        insert(t, s);
    }
}

private static void insert(Integer x, Stack<Integer> s) {
    if (s.isEmpty()) {
        s.push(x);
        return;
    }

    if (x < s.peek()) {
        Integer t = s.pop();
        insert(x, s);
        s.push(t);
    } else {
        s.push(x);
    }
}
Kitten answered 18/8, 2010 at 8:8 Comment(0)
S
8

It can be done...


Ok: sorted, ahem, "in-place" with only the listed ops, didn't need Top() or IsFull() or another stack or data structure other than the call frames. (Presumably the whole point of the homework problem was to require a recursive solution.)

Ruby

@a = [3, 2, 1, 6, 5, 4]

class Array
  def empty?
    return size == 0
  end
end

def sort e
  if @a.empty?
    @a.push e
    return
  end
  t = @a.pop
  if e > t
    @a.push(t).push(e)
    return
  end
  sort e
  @a.push t
end

def resort
  return if @a.empty?
  t = @a.pop
  resort
  sort t
end

p ['first ', @a]
resort
p ['final ', @a]
Spleen answered 30/1, 2010 at 20:26 Comment(3)
So this one works by defining two sort functions: resort which does not assume that the stack is already sorted and sort which does. Both work by recursively popping an element off until their goal is reached. In the case of the top-level resort, it's goal is to remove everything and build it back up by calling sort, and sort works by recursing just far enough to push a single element. I have to think a solution like this was the point of the exercise.Spleen
You are using extra memory; surely not explicitly organized as a stack (rather hidden in the call stack) but I'm curious if the OP's satisfied.Sal
Sure, but I think that was intended. Maybe this solution would be obvious to some people, but I had to think a bit to get this. It's a fun problem and I suspect it was designed to require pretty much this solution.Spleen
R
3

techInterview Discussion - Sorting on Stack

More pseudo than anything, but there is code examples and possible solution.

Resurgent answered 30/1, 2010 at 17:56 Comment(4)
I don't see how that is in-place. In-place means that you don't create any extra memory, save a few variables in O(1) space.Relator
OP had removed the in place conditionResurgent
People really need to take as wide an interpretation of the conditions as necessary in order to solve the problem. Obviously, in this case, in-place meant that another similarly-sized aggregate was not to be used, thus forcing a recursive solution with a temporary local variable or two in any given frame instance. Nothing is gained by taking a literal or overly pedantic view of the problem to the obviously-unintended extreme of permitting no solution.Spleen
If the question wanted a recursive answer, then IMO it makes more sense to say so, rather than imposing the very confusing condition "must implement this in a way which, in an imperative language, is pretty much guaranteed to be worse in every single way than using a second data structure". Of course this is a complaint about interview puzzlers in general rather than this question in particular :-)Secretion
T
3

Its not possible.

That happens because you cant iterate through the stack, because it has to be in place (you could if you would use extra memory). So if you cant iterate through the stack you cant even compare two elements of the stack. A sort without comparing would need extra memory, so that cant be used either.

Also im sure its not homework, because i dont think a teacher would give you a problem that cant be solved.

If you really have to do it only with stacks, just use 1-2 extra temporary stacks (i think 2 are needed, but not 100% sure) and do it.

Trudey answered 30/1, 2010 at 18:5 Comment(2)
Except, I just did it. Presumably a recursive solution was the intended solution, even though this certainly requires some sort of behind-the-scenes data structure. I think it's best to handle this kind of problem by coming up with some sort of solution that in some way meets the criteria. I doubt if the prof will be too impressed by "it's impossible".Spleen
As you said, you are using a "behind-the-scenes" data structure, which is the call stack. I should maybe better say its not possible with iteration, but possible with recursion :) . Edit: also my answer when he wanted an in-place solution (now he changed the topic), which is not one with recursion, because to be in-place the space used has to be a constant (which it isnt because you are using as much stack space you want).Trudey
R
2

You can't. You can't reorder the contents of a stack without removing elements, by definition. Also push and pop aren't in-place operations, so basically you're asking to sort a stack with Top, IsEmpty and IsFull. IsEmpty = !IsFull. So you're asking to sort a stack with Top and IsEmpty.

Relator answered 30/1, 2010 at 17:55 Comment(4)
Err, your statement on IsEmpty and IsFull is wrong (for most stacks). If the stack is not empty, it's not necessarily full (unless it's a one-element stack). :)Mucilage
Why aren't push and pop in-place operations?Adama
well, to get access to the nth element you need to pop n-1 elements. the n depends on the input size so it's not constant size memory allocation therefore not in-place.Relator
I think it's possible to do it "in-place", for some definition. See my posted answer and my comment on George's answer.Spleen
P
2

What temporary data structures can you use? With push and pop, and no temporary storage for n elements, accessing data near the bottom of the stack would be impossible without storing the rest -somewhere-.

If top (equiv to {x=pop();push(x);return x}) was replaced with shift, it would be perfectly doable - the stack would change into fifo (shift+push; pop would fall into disuse) and it would allow for an easy bubblesort on currently available elements.

Pyridine answered 31/1, 2010 at 0:35 Comment(0)
B
2

To bad you couldn't have two other stacks, then you could have played the Towers of Hanoi in O(n) space.

Blush answered 18/8, 2010 at 9:33 Comment(0)
J
2

//A java version

public static void sort(Stack<Integer> s){
    if(s.size() > 0){
        int tmp = s.pop();
        sort(s);
        sortFromBottom(s, tmp);
    }
}

private static void sortFromBottom(Stack<Integer> s, Integer value){
    if(s.size() == 0){
        s.add(value);
    }else{
        int tmpValue = s.peek();
        if(tmpValue < value){
            s.pop();
            sortFromBottom(s, value);
            s.push(tmpValue);
        }else{
            s.push(value);
        }
    }
}
Junoesque answered 7/12, 2012 at 16:24 Comment(0)
T
0

Bubble Sort and Insert Sort in Java https://github.com/BruceZu/sawdust/blob/82ef4729ee9d2de50fdceab2c8976d00f2fd3ba0/dataStructuresAndAlgorithms/src/main/java/stack/SortStack.java

 /**
  * Sort the stack using only Stack API, without using other data structure
  * Ascending from bottom to top
 */
public class SortStack<T extends Comparable<T>> {
 int sorted;

/**
 * Just Bubble Sort.
 */
private void bubble(Stack<T> s, T max) {
    if (s.empty() || s.size() == sorted) {
        s.push(max);
        sorted++;
        return; // note return
    }

    T currentTop = s.pop();
    if (max.compareTo(currentTop) < 0) {
        T tmp = max;
        max = currentTop;
        currentTop = tmp;
    }

    bubble(s, max);
    s.push(currentTop);
}

public Stack<T> sortAscending(Stack<T> s) {
    sorted = 0;
    if (s == null || s.size() <= 1) {
        return s;
    }

    while (sorted != s.size()) {
        bubble(s, s.pop());
    }
    return s;
}

/**
 * Just Insert Sort.
 */
private void insertSort(Stack<T> s) {
    if (s.empty()) {
        return;
    }
    T currentTop = s.pop();
    insertSort(s);
    insert(s, currentTop);
}

private void insert(Stack<T> s, T insert) {
    if (s.isEmpty() || insert.compareTo(s.peek()) <= 0) {
        s.push(insert);
        return;
    }

    T current = s.pop();
    insert(s, insert);
    s.push(current);
}

public Stack<T> sortAscendingByInsertSort(Stack<T> s) {
    if (s == null || s.size() <= 1) {
        return s;
    }
    insertSort(s);
    return s;
 }
}
Trunks answered 29/6, 2016 at 0:27 Comment(0)
F
0

Sorting a stack without extra space is quite not a possibility . At least not coming to my sane mind . We can surely use the recursion stack as extra space over here . The below approach might be helful .

My approach is O(N**2) . Over here I am iterating over stack N times, every time fixing the ith element in the stack .

Firstly fixed the bottom element by popping out N elements and pushing min_element and in Second try fixed the 2nd element from bottom by popping out N-1 elements and pushing min_element except the one pushed before this And so on .

Refer to the code below for more details .

    stack<int> stk;
    int sort_util(stack<int> &stk,int n,int mn)
    {
        if(n==0)
        {
            stk.push(mn);
            return mn;
        }

        int vl = stk.top();
        stk.pop();

        int fmin = sort_util(stk,n-1,min(mn,vl));

        if(fmin==vl)
            return INT_MAX;
        else
            stk.push(vl);

        return fmin;
    }

    void sort_stack(stack<int> &stk)
    {
        for(int i=stk.size();i>1;i--)
            sort_util(stk,i,stk.top());
    }
Fibrovascular answered 3/3, 2017 at 17:31 Comment(0)
T
0
#include<iostream> using namespace std;
class node {public:int n;
node* link;};class stack {public:

node* head = nullptr;
node* head1 = nullptr;
node* ik = nullptr;
int top = -1;
int top1 = -1;`

void push() {
    top++;
    top1++;

    node* temp = new node;
    node* temp1 = new node;

    int n;
    cin >> n;
    temp->n = temp1->n = n;
    temp->link = temp1->link = nullptr;

    if (head == nullptr) {
        head = temp;
        head1 = temp1;
    }
    else {
        temp->link = head;
        temp1->link = head1;
        head = temp;
        head1 = temp1;
    }
}

void pop1() {
    if (top1 == -1) {
        return;
    }
    int z = head1->n;
    head1 = head1->link;
    top1--;
    pop1();
    cout << z << ' ';
}

void lol(int n) {
    node* temp = nullptr;
    while (n < ik->n && ik->link != nullptr) {
        node* topo = new node;
        topo->n = ik->n;
        topo->link = nullptr;
        ik = ik->link;
        if (temp == nullptr)
            temp = topo;
        else {
            topo->link = temp;
            temp = topo;
        }
    }
    node* yoo = new node;
    yoo->n = n;
    yoo->link = nullptr;

    if (ik->link == nullptr) {
        if (n < ik->n) {
            ik->link = yoo;
        }
        else {
            yoo->link = ik;
            ik = yoo;
        }
    }
    else {
        if (ik == nullptr)
            ik = yoo;
        else {
            yoo->link = ik;
            ik = yoo;
        }
    }
    while (temp != nullptr) {
        node* uu = new node;
        uu->n = temp->n;
        uu->link = ik;
        ik = uu;
        temp = temp->link;
    }
}

void pushz() {
    int z = head->n;
    head = head->link;
    node* t = new node;
    t->n = z;
    t->link = nullptr;

    if (ik == nullptr) {
        ik = t;
    }
    else {
        if (ik->n < z) {
            t->link = ik;
            ik = t;
        }
        else {
            lol(z);
        }
    }
}

void sort() {
    while (top != -1) {
        pushz();
        top--;
    }
}

void sorty() {
    if (ik == nullptr)
        return;
    int z = ik->n;
    ik = ik->link;
    sorty();
    cout << z << ' ';
}

void display() {
    cout << "Original stack: ";
    pop1();
    cout << "\nSorted stack: ";
    sort();
    sorty();
}};int main() {

int n;
cin >> n;
stack s;
if (n == 0)
    cout << "Stack is empty";
else if (n < 11) {
    while (n--)
        s.push();
    s.display();
}
else if (n > 10)
    cout << "Stack is full";}
Tartuffe answered 30/9, 2023 at 21:6 Comment(1)
Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.Misshape

© 2022 - 2024 — McMap. All rights reserved.