Question

Data Structures and Algorithms. (C++ Language)

1. Write the definition code for a function that passes in a stack and returns (using a return statement) the number of items in the stack (the stack size).

a. assume the this function is to be toolkit function in the implementation of the ADT stack.

b. assume that this function is not a toolkit function.

2. Given the declaration:

s = stack

i = item

struct STACK

{

INFO_RC i;

int top;

}

write the definition source code for the following functions in the implementation of the ADT stack:

a. create_stacks(s)

b. empty(s)

c. pop(s,i)

d. top(s,i)

e. push(s,i)

f. purge(s)

3. Indicate the Big-0 "run-time" of each of the following:

a. deletion from a stack that is implemented using an array with the top of the stack always maintained in component 0. Thus items are always inserted and/or deleted at component 0.

b. deletion from a stack that is implemented using an ordinary array with the top of the stack always maintained in the first available component of the array (the stack grows "upward" starting at component 0).

c. print out all of the elements in a stack.

d. determine the number of items currently in the stack. (stack size is not a toolkit function)

Answer 1

Answer for 1

//Stack definition assuming stack contains only integer numbers

struct STACK

{

int i;

int top;

}

int stack_size(s,top)

{

return top+1;

}

Answer for 2

//create_stacks

STACK create_stacks(s)

{ s.top=-1;

}

//empty(s)

bool empty(s)

{ if (s.top==-1)

return 1;

return 0;

}

//pop(s,i)

int pop(s,i)

{ int i=s[top--];

return i;

}

//top(s,i)

int tops(s,i)

{ return s[top];

}

//push(s,i)

STACK push(s,i)

{ s[++top]=i;

return s;

}

Answer for 3c

O(n)-where n is size of stack

Answer for 3d

O(n)-where n is stack size