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.
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.
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.)
@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]
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 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);
}
}
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.)
@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]
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 techInterview Discussion - Sorting on Stack
More pseudo than anything, but there is code examples and possible solution.
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.
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.
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.
To bad you couldn't have two other stacks, then you could have played the Towers of Hanoi in O(n) space.
//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);
}
}
}
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;
}
}
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());
}
#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";}
© 2022 - 2024 — McMap. All rights reserved.