# Tough question. C ++?

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

Relevance

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() {

}

inline bool empty() {

}

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
• C++ is a computer language.( Computer programmes are written by C++ etc...)

• Login to reply the answers