Saturday, November 2, 2013

how to implement two stacks in one array

My friend came up with a new question  that he is asked in his interview,

Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

The code is implemented in C++.



/* 
 * File:   main.cpp
 * Author: bekoC
 */

#include <cstdlib>
#include<stdio.h>
#include <stdlib.h>
#include<iostream>

#define N 10 

struct Stacks {
    char charArray[N];
    int top1, top2;
    void olustur();
    bool Insert(int stackNumber, char veri);
    char deleteFromStack(int stackNumber);
    bool isEmpty(int stackNumber);
    void printStack(int stackNumber);
};

bool Stacks::Insert(int stackNumber, char newChar) {
    if (top1 == top2)
    {
        return false;
    }
    if (stackNumber == 1)
        charArray[top1++] = newChar;
    else
        charArray[top2--] = newChar;
    return true;
}

char Stacks::deleteFromStack(int stackNumber) {
    if (stackNumber == 1)
        return charArray[--top1];
    else
        return charArray[++top2];
}

bool Stacks::isEmpty(int stackNumber) {
    if (stackNumber == 1)
        return (top1 == 0);
    else
        return (top2 == N - 1);
}

void Stacks::create() {
    top1 = 0; 
    top2 = N - 1; 
}

void Stacks::printStack(int stackNumber) {

    if (stackNumber == 1 && !isEmpty(stackNumber)) {
        {
            for (int i = 0; i <= top1; ++i) {
                printf("%c", charArray[i]);

            }
        }
    } else if (isEmpty(stackNumber)) {
        printf("Stack 1 is empty");
    }
    if (stackNumber == 2 && !isEmpty(stackNumber)) {
        for (int i = N - 1; i >= top2; i--) {
            printf("%c", charArray[i]);
        }
    } else if (isEmpty(stackNumber)) {
        printf("Stack 2 is empty");
    }
}

int main() {
    Stacks myStack;
    myStack.create();
    myStack.Insert(1, 'A');
    myStack.Insert(1, 'B');
    myStack.Insert(1, 'C');
    myStack.Insert(1, 'D');
    myStack.Insert(1, 'E');
    myStack.Insert(1, 'F');

    myStack.Insert(2, 'W');
    myStack.Insert(2, 'X');
    myStack.Insert(2, 'Y');
    myStack.Insert(2, 'Z');
    myStack.printStack(1);
    myStack.printStack(2);
    if (!myStack.isEmpty(1))
        myStack.deleteFromStack(1);
    if (!myStack.isEmpty(2))
        myStack.deleteFromStack(2);
    return 0;
}

No comments:

Post a Comment