yeasir007

Thursday, November 09, 2017

Stack Implementation without STL in C++ and Java language & Runtime Stack Re-Initialization

Stack: A stack is a container of objects that are inserted(push) and removed (pop) according to the last-in-first-out(LIFO) principle.

[Problem]
Insert(Push) the given N (2 <=N <=100) numbers in order into a stack, then pop each and print on the screen.

[Input]
The first input line contains the number of test cases,T.
The next line contains the number of data input.
Then,integer data will be listed.

[Output]
For each given test case,print each stack.

Input                                                       OUTPUT
2 //Test case                                            #1 5 4 3 2 1
5 //Data size                                           #2 1 2 3 4 5
1 2 3 4 5
5
5 4 3 2 1


JAVA Source:

package com.datastructure;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.net.URL;
import java.util.Scanner;
public class Stack {

static final int MAX_N = 100;
static int top;
static int stack[] = new int[MAX_N];
static private final String INPUT = System.getProperty("user.dir") + "\\src\\data\\stack.txt";

public static void main(String[] args) {

    FileInputStream instream = null;
    try {
        instream = new FileInputStream(INPUT);
        System.setIn(instream);
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }

    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    for(int testcase = 1;testcase<=T;testcase++)
    {
        initStack();
        int N = sc.nextInt();

        for(int i=0;i<N;i++)
        {
            int value = sc.nextInt();
            stackPush(value);
        }

        System.out.println("Now poping out stack elements: ");
        for(int i=0;i<N;i++)
        {
            Integer popvalue = null;
            popvalue = stackPop();
            System.out.println(popvalue + " ");
        }
        System.out.println();

    }
    sc.close();
}

private static Integer stackPop() {
    Integer retVal = null;
    if(!stackIsEmpty())
    {
        top--;
        retVal = new Integer(stack[top]); 
    }

    return retVal;
}

private static void stackPush(int value) {
    if(!stackIsFull())
    {
        stack[top] = value;
        top++;
    }
}

private static boolean stackIsFull() {
    if(top <=MAX_N)
    {
        return false;
    }
    else
        System.out.println("Stack is full.");

    return true;
}

private static boolean stackIsEmpty() {
    return (top == 0);
}

private static void initStack() {
    top=0;      
}

}

C++ Source :

#include<iostream>
#define MAX_N 100

using namespace std;

int top;
int stack[MAX_N];

void initStack();
bool stackIsFull();
void stackPush(int value);
bool stackIsEmpty();
bool stackPop(int *popVal);

int main()
{
 int T, tc,N;
 freopen("stack.txt", "r", stdin);

 cin >> T;

 for (tc = 1; tc <= T; tc++)
 {
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int value;
        cin >> value;
        stackPush(value);

    }

    cout << "#" << tc << " ";

    while (!stackIsEmpty())
    {
        int popVal;
        if (stackPop(&popVal))
        {
            cout << popVal << " ";
        }
    }
    cout << endl;

}

 return 0;
}

bool stackPop(int *popVal)
{
 if (!stackIsEmpty())
 {
    top--;
    *popVal = stack[top];
    return true;
 }
 else
 {
    cout << "Stack is empty." << endl;
    return false;
 }
}
void stackPush(int value)
{
if (!stackIsFull())
{
    stack[top] = value;
    top++;
}
}

bool stackIsEmpty()
{
   return (top == 0);
}

bool stackIsFull()
{
  if (top >= MAX_N)
  {
    cout << "Stack is full." << endl;
    return true;
}

  return false;
}

void initStack()
{
   top = 0;
}

Runtime Stack Re-Initialization : 

#include<iostream>
#include<malloc.h>

using namespace std;
#define INF -999999
class Stack
{
private:
 int stackSize;
 int *StackData;
 int Top;
public:
Stack()
{
    this->Top = 0;
    this->stackSize = 1;
    StackData = (int *)malloc(sizeof(int)* stackSize);
}

private:
void reSizeTheStack()
{
    int *temp = (int *)malloc(sizeof(int)*stackSize*2);

    for (int i = 0; i < stackSize; i++)
        temp[i] = StackData[i];
    /*for (int i = stackSize; i < stackSize * 2; i++)
        temp[i] = -INF;
    */
    free(StackData);
    stackSize = stackSize * 2;
    StackData = temp;
}

public:
void push(int data)
{
    if (Top >= stackSize)
    {
        reSizeTheStack();
    }

    StackData[Top++] = data;
}

int pop()
{
    if (Top <= 0)
    {
        cout << "Sorry Stack is underflow." << endl;
        return -1;
    }

    StackData[Top] = INF;

    Top--;
    return StackData[Top];
}

int size()
{
    return stackSize;
}

bool isEmpty()
{
    return (Top <= 0);
}

void printStackData()
{
    for (int i = 0; i < Top; i++)
    {
        cout << StackData[i] << " ";
    }

    cout << endl;
 }
};

int main()
{
Stack *objStack = new Stack();

objStack->push(10);
objStack->push(9);
objStack->push(8);
objStack->push(7);
objStack->push(6);
objStack->push(5);
objStack->push(4);
objStack->push(3);
objStack->push(2);
objStack->push(1);

cout << "Stacked data : " << endl;
objStack->printStackData();

cout << "Popped data : " << objStack->pop() << endl;

cout << "After poped Stacked data : " << endl;
objStack->printStackData();

return 0;
}

No comments:

Post a Comment

Thanks for your comments