Tough question. C ++?

One of the major disadvantages of the stack design in the file

stackofint.cc https://www.cs.tcd.ie/John.Waldron/2E3/stackofint.... is

that you have to know the future! In other words you have to guess in

advance the maximum number of elements that will go on the stack and

if you get it wrong you are in big trouble.

1/ Implement and fully test a stack using an extendable array. Create

an array initially of size eight say and then if it fills up make a new

array of size sixteen and copy the eight elements into the new array

so that the stack never runs out of space. For each method in your stack

class analyse the running time using the generalised methodology

and include this as a comment in your submission.

2/ Implement a stack class using a linked list rather than an

array. For each method in your stack class analyse the running time

using the generalised methodology and include this as a comment in

your submission.

2 Answers

Relevance
  • cja
    Lv 7
    1 decade ago
    Favorite Answer

    This appears to be assignment for a class, and you should really be doing your own work. I'll give you an answer to #1, to give you an idea of how to do it and help get you started. Mine isn't the only way to do it, and you may find a better approach. Studying and understanding a working solution should teach you something.

    #include <iostream>

    #include <cstring>

    using namespace std;

    class IntStack {

      public:

        IntStack() : maxSize(0),growIncr(0),

                                  top(NULL),stackData(NULL) { }

        IntStack(unsigned size, unsigned n = 2) :

            maxSize(size), growIncr(n) {

            stackData = new int[size+1];

            top = &stackData[size];

            init(stackData,size+1);

        }

        ~IntStack() {

            if (stackData != NULL) delete [] stackData;

        }

        void init(int *data, int size) {

            memset(data,0,size*sizeof(int));

        }

        inline bool full() {

            return top == stackData;

        }

        inline bool empty() {

            return top == &stackData[maxSize];

        }

        inline unsigned stackLen()

            { return &stackData[maxSize] - top;

            }

        inline unsigned getMaxSize() {

            return maxSize;

        }

        void push(int n) {

            if (full() == true) grow();

            *(--top) = n;

        }

        int pop() {

            int x = *top;

            if (empty() == false) top++;

            return x;

        }

        void grow() {

            cout << "growing" << endl;

            int newSize = maxSize + growIncr;

            int *temp = new int[newSize + 1];

            init(temp,newSize+1);

            memcpy( temp + growIncr,stackData,(maxSize+1) * sizeof(int) );

            maxSize += growIncr;

            delete [] stackData;

            stackData = temp;

            top = &stackData[growIncr];

        }

        void stackDump() {

            if (empty() == false) {

                int len = stackLen();

                int *p = top;

                for (int i = 0; i < len; i++) {

                    cout << *p++ << endl;

                }

            }

            cout << endl;

        }

      private:

        unsigned maxSize;

        unsigned growIncr;

        int *top;

        int *stackData;

    };

    int main(int argc, char *argv[]) {

        IntStack *s = new IntStack(5);

        cout << "stackLen = " << s->stackLen() << endl;

        if (s->empty() == true) cout << "empty" << endl;

        for (int i = 1; i <= 5; i++) {

            s->push(i);

            cout << "stackLen = " << s->stackLen() << endl;

        }

        if (s->full() == true) cout << "full" << endl;

        s->stackDump();

        cout << "popping 2" << endl;

        s->pop();

        s->pop();

        if (s->full() == true) cout << "full" << endl;

        if (s->empty() == true) cout << "empty" << endl;

        s->stackDump();

        cout << "stackLen = " << s->stackLen() << endl;

        cout << "pushing 5" << endl;

        for (int i = 10; i < 15; i++) s->push(i);

        s->stackDump();

        delete s;

        return 0;

    }

    #if 0

    Program Output:

    stackLen = 0

    empty

    stackLen = 1

    stackLen = 2

    stackLen = 3

    stackLen = 4

    stackLen = 5

    full

    5

    4

    3

    2

    1

    popping 2

    3

    2

    1

    stackLen = 3

    pushing 5

    growing

    growing

    14

    13

    12

    11

    10

    3

    2

    1

    #endif

    • Login to reply the answers
  • 1 decade ago

    C++ is a computer language.( Computer programmes are written by C++ etc...)

    • Login to reply the answers
Still have questions? Get your answers by asking now.