Tag Archives: stack

Printing binary form of a number using stack

0
Posted on by
void printBinaryForm(int n)
{
    Stack S;  // Say it creates an empty stack S
    while (n > 0)
    {
      // This line pushes the value of n%2 to stack S
      push(&S, n%2);
 
      n = n/2;
    }
 
    // Run while Stack S is not empty
    while (!isEmpty(&S))
      printf("%d ", pop(&S)); // pop an element from S and print it
}

How to sort a stack?

0
Posted on by

Given a stack S, write a C program to sort the stack (in ascending order).
You are not allowed to make any assumptions about how the stack is implemented; the only
functions allowed to be used are: Push, Pop, Top, IsEmpty, IsFull.

time complexity O(n^2)
Assuming that the only data structure allowed here is the Stack,
then you could use 2 Stacks.

Iterate until the original stack is empty and in each iteration,
pop an element from the original stack, while the top element
in the second stack is smaller than the removed element,
pop the second stack and push it to the original stack.
Now you can push the element you originally popped off the
original stack to the second stack.
if the top element in the 2nd stack is greater than the removed element
just push the removed element from the stack1 to stack2

Ex:
initially
s1:100,2,76,3
s2:null

s1:2,76,3
s2:100

s1:76,3
s2:2,100

s1:2,3
s2:76,100

s1:3
s2:2,76,100

s1:2
s2:3,76,100

s1:null
s2:2,3,76,100

This is actually a modified insertion sort

#include<iostream>
#include<stack>
using namespace std;
int main(){
stack<int> s1,s2;
s1.push(3);
s1.push(76);
s1.push(2);
s1.push(100);
s2.push(s1.top());
s1.pop();
int value;
while(!s1.empty()){
value=s1.top();
s1.pop();
while(value>s2.top()){
s1.push(s2.top());
s2.pop();
}
s2.push(value);
}
while(!s2.empty()){
cout<<s2.top()<<' ';
s2.pop();
}
}
view raw sortstack.cpp hosted with ❤ by GitHub