Stacks and Queues

stack top

int Stack::top() {

if (length > 0)

return stk[stktop]

else

return (-9999);

}

stack push

int Stack::push(int e) {

int i;

if (length == max) {

int newstk = new int[2 max];

int * oldstk = stk;

for ( i = 0; i < max; i++)

newstk[i] = stk[i];

newstk[max]=e;

stk = newstk;

delete [] oldstk;

length ++;

stktop++;

max = 2 * max;

}

else {

length++;

stktop++;

stk[stktop] = e;

}

return 1;

}

stack pop

int Stack::pop(){

if ( length == 0)

return -1;

else

if (max <= 300) {

length--;

stktop--;

}

else if (length < max/3) {

stktop--;

length--;

int * newstk = new int[max/2];

int * oldstk = stk;

for (int i = 0; i <length ; i++)

newstk[i] = stk[i];

stk = newstk;

delete [] oldstk;

max = max/2;

}

else {

stktop -- ;

length -- ;

}

return 1;

}

}

enqueue

int Queue::enqueue(int e) {

if (length == max) {

int newque= new int[2max];

int * oldque = que;

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

newque[i] = que[ (front+i) mod max ];

}

front = 0;

// back = max -1;

back = max;

newque[back] = e;

que = newque;

delete [] oldque;

length ++;

max = 2 * max;

}

else {

back = (back +1) mod max;

que[ back ] = e;

length ++;

}

return 1;

}

dequeue

int Queue::dequeue() {

if (length ==0)

return -1;

else {

if (max <= 300) {

length--;

front = (front +1) mod max;

}

else if (length < max/3) {

length--;

int * newque = new int[max/2];

int * oldque = que;

for (int i = 0; i <length ; i++)

newque[i] = que[(front + i) mod max];

que = newque;

delete [] oldque;

front = 0;

back = length -1;

max = max/2;

}

else {

front = (front + 1 ) mod max ;

length -- ;

}

return 1;

}

}