7.8 Improved Stack Implementation, Solutions by Kris Jurka

Problem 1

* Add to the code a method which returns the number of items currently on the stack.

int number_of_items()
{
return number;
}

Problem 2

* Add to the stack class a second constructor of two arguments, one giving the initial stack size, and one giving the increment.

Stack(int limit, int increment)
{
this.limit = limit;
this.increment = increment;
array = new int[limit];
number = 0;
}

Problem 3

** Suppose we wished for the stack to reduce the size of the allocated array whenever number is less than limit - increment. Modify the code accordingly.

int pop()
{
int x = array[--number];
if (number < limit - increment) shrink();
return x;
}

void shrink()
{
int newArray[] = new int[limit-increment];
for (int i=0; i < limit-increment; i++)
{
newArray[i]=array[i];
}
array = newArray;
limit -= increment;
}

Problem 4

*** Change the policy for incrementing stack size to one which increases the size by a factor, such as 1.5, rather than simply adding an increment. Do you see any advantages or disadvantages of this method vs. the fixed increment method?

When adding an increment you are beholden to the initial increment. If the increment is small and you are dealing with a large array, there will be numerous array resizings which will slow things down considerably. Incrementing by a factor is more flexible since it decides how much to increment by based upon the current size of the array.

class Stack
{
double factor;
int limit, number;
int array[];

Stack(int limit, int factor)
{
this.limit = limit;
this.factor = factor;
array - new int[limit];
number = 0;
}

// we size the new array as limit*factor+1 since for both a small limit
// and factor we could end up with the limit we started with and then
// when pushing onto the the new array we will throw an
// ArrayIndexOutOfBoundsException.

void ensure()
{
if (number >= limit)
{
int newArray = new int[(int)(limit*factor+1)];
for (int i=0; i < limit; i++)
{
newArray[i] = array[i];
}
array = newArray;
limit = (int)(limit*factor+1);
}
}

void push(int x)
{
ensure();
array[number++] = x;
}

...... // other methods remain unchanged
}

Problem 5

*** For the methods presented here, there is no requirement that the items in the stack be in a contiguous array. Instead a linked list could be used. Although a linked list will require extra space for pointers, the amount of space al located is exactly proportional to the number of items on the stack. Implement a stack based on linked lists.

class node {
int data;
node next;

node(int x) {
data = x;
next = null;}
}

class stack {
node top;

stack() {
top = null;}

int pop() {
int x = top.data;
top = top.next;
return x;}

void push(int x) {
node new_node = new node(x);
new_node.next = top;
top = new_node;}
}

Problem 6

**** Along the lines of the preceding linked list idea, but rather than linking individual items, link together chunks of items. Each chunk is an array. Thus the overhead for the links themselves can be made as small as we wish by making the chunks large enough. This stack gives the incremental allocation of our example, but does not require copying the array on each extension. As such, it is superior, although its implementation is more complicated.

class chunk {
int data[];
int number, size;
chunk next;

chunk(int size) {
data = new int[size];
number = 0;
this.size = size;
next = null;}

int pop() {
return data[--number];}

void push(int x) {
data[number++] = x;}

boolean empty() {
return(number==0);}

boolean full() {
return(number==size);}
}

class stack {
int size = 100;

chunk top;

stack() {
top = null;}

int pop() {
int x = top.pop();
if(top.empty()) {
top = top.next;}
return x;}

void push(int x) {
if(top==null || top.full()) {
chunk new_chunk = new chunk(size);
new_chunk.next = top;
top = new_chunk;}
top.push(x);}
}
Kris Jurka