Implementing two stacks using single array in java

Question

Please review the code

package com.gmail.practice;

import java.util.Arrays;

public class StacksForTwo {

    int size;
    int[] stack;
    int top1;
    int top2;

    public StacksForTwo(int arraysize)
    {
        size = arraysize;
        stack = new int[size];
        top1 = -1;
        top2 = size;        
    }

    public void push1(int x)
    {
        if(top1 < top2-1)
        {
        top1++;
        stack[top1] = x;        
        }else{
            System.out.println("stackoverflow");
        }
    }

    public void push2(int y)
    {
        if(top1 < top2-1)
        {
            top2--;
            stack[top2] = y;
        }else{
            System.out.println("stack overflow");
        }
    }

    public void pop1()
    {
        if(top1 >= 0)
        {
            top1--;
            System.out.println("The popped out number is"+" "+stack[top1+1]);
        }else{
            System.out.println("stack underflow");
        }
    }

    public void pop2()
    {
        if(top2 < size)
        {
            top2++;
            System.out.println("The popped out number is"+" "+stack[top2+1]);
        }else{
            System.out.println("stack underflow");
        }
    }

    public void display()
    {
        System.out.println(Arrays.toString(stack));
    }

    public static void main(String[] args)
    {
        StacksForTwo sft = new StacksForTwo(10);
        sft.push1(4);
        sft.push1(5);
        sft.push1(3);
        sft.push1(2);
        sft.push2(6);
        sft.push2(4);
        sft.display();
        sft.push2(8);
        sft.push1(2);
        sft.push2(6);
        sft.push2(4);
        sft.push2(8);
        sft.display();
    }
}

Answer 1

I would go for

interface Stack {
    boolean isEmpty();
    int pop();
    void push(int x);
}

And then make a class providing two Stacks.

Also create a counter to detect when both stacks are full. This can be done with an AtomicInteger (thread-safeness) counting the free array slots.

public class StackPair {
    public final Stack firstStack = new Stack { ... };
    public final Stack secondStack = new Stack { ... };
    public StackPair(int capacity) { ... }

---

In StackPair the single array and an AtomicInteger freeEntries. In both Stack implementations access to the array and freeEntries.

Answer 2

This code is a WOM implementation of a stack - Write Only Memory. Normally it's done as a joke. The only way to get the data out of the stack is to parse the standard output waiting for println statements with the values in them.

I can understand that your code is here for you to watch the process happening, but beyond that there's not much real functionality in here. I encourage you to use proper code where the pop() methods actually return their result, and the calling code is the code that prints the output. Alternatively, I strongly recommend you use the IDE's debugger interface to step through your code so you can watch things happen that way.

Having said all that, here are some general comments:

1. your instance variables are not private, and should be.
2. the size and stack variables should also be final
3. instead of having a display() method, just override the toString()
4. push1, and pop1 et all should probably be renamed to pushLeft and pushRight, or really anythong other than 1 and 2. You used the variables x and y so why not pushX and pushY?

Answer 3

You are inconsistent with your brace and indentation style. If in doubt, pick an auto-formatter and work with that. Most IDEs come with one, just use that for the beginning.

---

public class StacksForTwo

That's a bad name for the class. A "pair" is a better word to use.

---

int size;
int[] stack;
int top1;
int top2;

Why are these variables package-private?

---

public StacksForTwo(int arraysize)

arraysize is an incorrect name for this variable, size would be correct as that an array is being used is only an implementation detail and should not be shown through the API.

public StacksForTwo(int size) {
    this.size = size;
    ...

Also it should be made clear that the size is the size for all items.

---

public void push1(int x)

x is a bad name for this variable, it should rather be item or value.

---

System.out.println("stackoverflow");

It would be better to throw an exception in this case.

---

public void pop1()
...
    System.out.println("The popped out number is"+" "+stack[top1+1]);

This method should return the popped number and leave the printing to the outside code.

---

top1--;
System.out.println("The popped out number is"+" "+stack[top1+1]);

For easier reading, you can roll that into one operation:

return stack[top1--];

---

System.out.println("stack underflow");

This should also be an exception.

---

public void display()
{
    System.out.println(Arrays.toString(stack));
}

That should be the overridden toString method.

---

public static void main(String[] args)

Ideally, your main class is a different one.

---

StacksForTwo sft = new StacksForTwo(10);

Please don't go fancy with names, always pick the stupid and simple ones, like stacksForTwo or stacks. Down in a 1000+ line method, having to work with shortened names and/or acronyms as names is a nightmare you don't want to find yourself, because you constantly have to map the names to something that makes sense for you.

Answer 4

I have to second Joop Eggen and put providing a proper interface first. With Java botching it right from the start (ab)using an abstract class in pre-Collections Framework times to go and not create FIFO, but decorate Deque, I guess there is no way getting an interface Stack right. I ended up on the fat side:

/** <code>Stack</code> with quintessential <code>push()</code>
 * and <code>pop()</code>. */
public interface Stack<E>
    extends Iterable<E> // don't know how else to provide a default iterator() 
    // java.util.Collection<E> if that wasn't FAT
{
    /** A <code>Stack</code> with a buddy allowing access to the latter. */
    interface Buddy<E> extends Stack<E> {
        Buddy<E> buddy();
    }
 // essential
    E pop();
    /** @throws IllegalStateException if <code>element</code> not accepted */
    default void push(E element) {
        checkRecursion();
        if (!offer(element))
            throw new IllegalStateException("element offered not accepted");
    }
 // important if pop() throws when empty
    default boolean isEmpty() { return size() <= 0; }

 // secondary
    /** <em>Not</em> specifying overrides not to throw the likes of
     *  <code>IllegalStateException</code> instead,
     *   the default implementation returns <code>null</code> if empty.
     * Fails catastrophically if pop() or push()
     *  fail in between modifying and restoring state. */
    default E peek() {
        if (isEmpty())
            return null;
        E top = pop();
        push(top);
        return top;
    }

    /** @return accepted */
    default boolean offer(E element) { push(element); return true; }
    int size();

 // support
    /** For consistency, the <code>Iterator<E></code> returned
     *  should <em>not</em> allow <code>remove()</code>
     *  (but, possibly, for the top element). */
    @Override
    default java.util.Iterator<E> iterator() {
        throw new UnsupportedOperationException();
    }

    default void checkRecursion() {
        try {
            if (Stack.class == getClass().getMethod("offer",
                    new Class [] { Object.class }).getDeclaringClass())
                throw new IllegalStateException(
                    "neither offer nor push implemented");
        } catch (NoSuchMethodException | SecurityException e) {
            throw new IllegalStateException(e);
        }
    }
}


// for the hell of it: an implementation
// Don't do as I do: Do as I say (regarding doc comment _everything_ public)
/** Not synchronised. */
public class Stack_<E> implements Stack.Buddy<E> {
    protected final AtomicInteger total;
    protected Object[] elements; // might be final but for resizing
    protected Stack.Buddy<E> buddy;
    @Override
    public Stack.Buddy<E> buddy() {
        if (null == buddy)
            buddy = new Stack_.Buddy<>(this, elements, total);
        return buddy;
    }

    protected int top;
    @Override
    public int size() { return top + 1; }
    protected int nextTop() { return ++top; }
    protected int prevTop() { return --top; }
 // Alternative to overridden <code>top<code> manipulation:
 //  overridden accessors
 // E at(int i) { return (E) elements[i]; }
 // void set(int i, E e) { elements[i] = e; }

 // An implementation growing elements on demand should conceivably
 //  provide a default constructor (using a default capacity).
    public Stack_(int arraysize) {
        elements = new Object[arraysize];
        total = new AtomicInteger();
        buddy = null;
        top = -1;
    }
    protected Stack_(Object[] elements, AtomicInteger total) {
        this.elements = elements;
        this.total = total;
    }
    public void push(E x) {
        if (total.incrementAndGet() <= elements.length)
            elements[nextTop()] = x;
        else {
            total.decrementAndGet();
            throw new IllegalStateException(
//          System.err.println(
                "no space");
        }
    }
    @Override
    public E pop() {
        E value = peek();
        elements[top] = null;  // long lived containers should support GC
        prevTop();
        return value;
    }
    @Override
    public E peek() { return (E) elements[top]; }
    @Override
    public String toString() {  // might cache asList
        return java.util.Arrays.asList(elements).subList(0, top).toString();
    }


    static class Buddy<E> extends Stack_<E> {
        public Buddy(Stack_<E> buddy, Object[] elements, AtomicInteger total) {
            super(elements, total);
            this.buddy = buddy;
            top = elements.length;
        }
        @Override
        protected int nextTop() { return --top; }
        @Override
        protected int prevTop() { return ++top; }
        @Override
        public int size() { return elements.length - top; }

        @Override
        public String toString() {
            StringBuffer sb = new StringBuffer(2+4*size());
            String sep = "[";
            for (int i = elements.length ; top <= --i ; sep = ", ")
                sb.append(sep).append(String.valueOf(elements[i]));
            return sb.append(']').toString();
        }
    }
}

(Considering what is ranked secondary, the remaining difference may be)
Stack.Buddy<E>: a stack supporting getting a buddy.
Using a proper interface gets "the member naming issue" out of the way.

Next comes my hobby horse: comment, at least doc comment everything public.

Then, there is code duplication between push[12]() & pop[12]()
- for 1½ exercises in avoiding it, see the implementation above.

Avoid having business functions communicate, e.g. using System.in/out.