Your task is to implement Stack and Queue classes for Objects. Both
Stack and Queue should extend Collection, which is an abstract class
that will be given to you. You will need to download and modify the
NetBeans project that goes along with this assignment.
Stack should have the following members:
-size:int
-capacity:int
-top:int
-collection:Object[]
and the following constructors and methods:
+Stack():
+Stack(capacity:int):
+push(x:Object):void
+peek():Object
+pop():Object
+getSize():int
+getCapacity():int
+setCapacity(capacity:int):void
Queue should have the following members:
-size:int
-capacity:int
-head:int
-tail:int
-collection:Object[]
and the following constructors and methods:
+Queue():
+Queue(capacity:int):
+enqueue(x:Object):void
+dequeue():Object
+getSize():int
+getCapacity():int
+setCapacity(capacity:int):void
Write a class TestStackAndQueue to test your Stack and Queue
implementation. Demonstrate your implementation by storing and
retrieving Integers.

---------------------------------------------------
that's the question

So Far i got this !!

---------------------------------------------------
i made collection.java

import java.util.Arrays;

public abstract class Collection {
    public static final int DEFAULT_CAPACITY = 16;
    protected int size;
    protected int capacity;
    protected Object [] collection;
    
    public Collection () {
        this(DEFAULT_CAPACITY);
    }
    
    public Collection (int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.collection = new Object[capacity];
    }
    
    public int getSize () {
        return size;
    }
    
    public int getCapacity () {
        return capacity;
    }
    
    public void setCapacity (int capacity) throws Exception {
        if (capacity > this.capacity) {
            this.capacity = capacity;
            Object [] newCollection = Arrays.copyOf(collection, capacity);
            collection = newCollection;
        } else if (capacity < this.capacity) {
            throw new Exception("Capacity cannot be reduced");
        }
    }
}

and

i made stack.java

public class Stack extends Collection {
    private int top;
    
    public Stack () {
        top = -1;
    }
    
    public Stack (int capacity) {
        super(capacity);
        top = -1;
    }
    
    public void push(Object o) throws Exception {
        if (size == capacity) {
            setCapacity(2*capacity);
        }
        top++;
        collection[top] = o;
        size++;
    }
    
    public Object peek() {
        return collection[top];
    }
    
    //TODO: FIX THIS METHOD!
    public Object pop() {
        Object o = collection[top];
        top--;
        size--;
        return o;
    }
}

and i also made TestStackAndQueue.java

public class TestStackAndQueue {

   public static void main(String[] args) {
        
    }
}

-----------------------

now i am stuck on this .. i have to make queue.java

public class Queue {
    
}

and this is where i got stuck can any one please help me with this queue ???

thank you in advance !!!

Queue should have the following members:

-size:int
-capacity:int
-head:int
-tail:int
-collection:Object[]

and the following constructors and methods:

+Queue():
+Queue(capacity:int):
+enqueue(x:Object):void
+dequeue():Object
+getSize():int
+getCapacity():int
+setCapacity(capacity:int):void

Edited 5 Years Ago by glamourhits: n/a

The pop method of the Stack class is not complete. Maybe you have fixed it already, but you need to check if the stack is empty before removing the top element.

A queue is almost identical to a stack. The only difference is the stacks are LIFO (last in, first out), but queues are FIFO (first in, first out)

Also, why are you using [] instead of real dynamic array like ArrayList? This "Arrays.copyOf(collection, capacity); collection = newCollection;" is an inefficient way of implementing dynamic collection (too much of trouble). Is it in your requirement to do so?

Also, why do you have to multiply the capacity by 2 when you push an object? Or it is for future use?

Edited 5 Years Ago by Taywin: n/a

Collection ... is an abstract class that will be given to you

Hi Taywin - Fair questions, but it sounds like the OP didn't have any choice about that.

ps Doubling the capacity when the internal array is full is a very common algorithm, in fact ArrayList (java 7) uses

newCapacity = oldCapacity + (oldCapacity >> 1);

... which looks like trebling it to me ... I guess its a trade-off between how much memory you use and how often you have to allocate/copy a new array.

Edited 5 Years Ago by JamesCherrill: ps

This article has been dead for over six months. Start a new discussion instead.