multiple stack in one dimentional array using node/ linked list

[ezkonekgal]

before anything else, i have a question. How can you have a multiple stack in one vector using node/linked list? i don't get the concept of linked list yet. Anyways, this is my problem:
Create a Java class definition of a multiple-stack in one dimensional vector. Implement the basic operations on stack (push, pop, etc) to make them applicable on multiple-stack.

i have this so far:

import javax.swing.*;

public class MStack implements Stack{

		private Node top;
		private int numElements = 0;

		class Node{
			Object info;
			Node link;
		}

		public int size(){
			return (numElements);
		}

		public boolean isEmpty(){
			return (top == null);
		}

		public Object top(){
			if (isEmpty()) throw new StackException("Stack empty.");
			return top.info;
		}

		public Object pop(){
			Node temp;
			if (isEmpty())throw new StackException("Stack underflow.");
				temp = top;
				top = top.link;
			return temp.info;
		}

		public void push(Object item){
			Node newNode = new Node();
			newNode.info = item;
			newNode.link = top;
			top = newNode;
		}


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

	public MStack(){
		String item= JOptionPane.showInputDialog("hi:");
		push(item);
		JOptionPane.showMessageDialog(null, top);
	}

}

public interface Stack {

	public int size();
	public boolean isEmpty();
	public Object top() throws StackException;
	public Object pop() throws StackException;
	public void push(Object item) throws StackException;

	class StackException extends RuntimeException{
		public StackException(String err){
		super(err);
		}
	}
}

i don't know if i did a multiple stack.. please help? thanks

[verruckt24]

No, you did not, from the code you have written you are just implementing a single stack. Also to confess I too have not understood what your assignment is : "to implement multiple stack with a single dimensional vector". Details would be required for further thought.
BTW : Linked List is a sequential list of nodes where each node carrries a data element and a "link" to the next such node in the list. You have defined the structure correctly for that.

[ezkonekgal]

No, you did not, from the code you have written you are just implementing a single stack. Also to confess I too have not understood what your assignment is : "to implement multiple stack with a single dimensional vector". Details would be required for further thought.
BTW : Linked List is a sequential list of nodes where each node carrries a data element and a "link" to the next such node in the list. You have defined the structure correctly for that.

Or prof. gave the assignment. Thats the instructions. What kind of details would that be? I also don't get it.
I believe multiple stack is possible using array, but a NODE? OK, what if i have 3 stacks namely stack1, stack2, stack3. how do i put it in a single vector. what is a vector anyways?

[verruckt24]

OK, what if i have 3 stacks namely stack1, stack2, stack3. how do i put it in a single vector.

Well thats what I too am finding hard to understand.

what is a vector anyways?

Here's where you can find out what a vector in java is.

[ezkonekgal]

Well thats what I too am finding hard to understand.

Here's where you can find out what a vector in java is.

I checked the link.. thanks for that.. Well, what do you think of the problem?

[BestJewSinceJC]

You have to tell us what a multiple stack is. I don't think very many people have heard that term before. Then we can help you. If a multiple stack is just more than one stack, which would seem likely, then just use a Vector of Vectors. So a Vector where each index in the Vector is, itself, a Vector. Same as a list of lists.

[ezkonekgal]

2.7.1 Multiple Stacks using One-Dimensional Array
Two or more stacks may coexist in a common vector S of size n. This approach boasts of better memory utilization. If two stacks share the same vector S, they grow toward each other with their bottoms anchored at opposite ends of S.
2.7.1.1 Three or More Stacks in a Vector S
If three or more stacks share the same vector, there is a need to keep track of several tops and base addresses. Base pointers defines the start of m stacks in a vector S with
size n. Notation of which is B(i):
B = ën/mû * i - 1 0 £ i < m
B[m] = n-1
B points to the space one cell below the stack's first actual cell. To initialize the stack, tops are set to point to base addresses, i.e.,
T = B , 0 £ i £ m

[ezkonekgal]

This is what i have so far:

import java.io.*;
import java.util.*;

public class MStack {

	/* Default length of the array */
	public static final int CAPACITY = 500;

	/* Length of the array used to implement the stack */
	public static int capacity;

	int d;

	/* Array used to implement the stack*/
	Object S[];

	/* Initialize the stack to default CAPACITY */
	public MStack(){
		this(CAPACITY);
	}
	/* Initialize the stack to be of the given length */
	public MStack(int c){
		capacity = c;
		S = new Object[capacity];
	}

	 public static void main (String []args){
		new MStack();
		System.out.println(CAPACITY);

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

		}
	 }


	 int T[] = new int[d];
	 int B[]= new int[d];

	 /* Pushes element on top of stack i */
	 public void push(int i, Object item) {
		 if (T[i]== B[i+1]) MStack(i);
		 S[++T[i]]= item;
	 }
	 /* Pops the top of stack i */
	 public Object pop(int i) throws StackException{
		 Object item;
		 if (isEmpty(i))throw new StackException("Stack underflow.");
		 item = S[T[i]];
		 S[T[i]--] = null;
		 return item;
	 }
	 public boolean isEmpty(){
			return (T[i] = B[i+1]);
		}
	 class StackException extends RuntimeException{
			public StackException(String err){
			super(err);
	 }

   }
}

What i figured out to have a multiple stack, is that you have an array, and inside the array you have a stack.. You subdivide the array to have multiple stacks by having base pointers to identify each stack inside the array.
I'm having trouble on the base pointer... can any one help me..

[verruckt24]

In your previous post you gave a formula to calculate the array of base pointers which will all be holding the start of the m stacks.
B = ën/mû * i - 1, 0 £ i < m
Here,
n is the size of the array
mu - I guess is the mathematical constant, though I don't know how it fits over here.
i = the stack number, out of the m stacks that you want to calculate the base pointer location for.
For the m th stack the location is given by you as follows :
B[m] = n-1
I hope this clears it up.

[ezkonekgal]

In your previous post you gave a formula to calculate the array of base pointers which will all be holding the start of the m stacks.
B = ën/mû * i - 1, 0 £ i < m
Here,
n is the size of the array
mu - I guess is the mathematical constant, though I don't know how it fits over here.
i = the stack number, out of the m stacks that you want to calculate the base pointer location for.
For the m th stack the location is given by you as follows :
B[m] = n-1
I hope this clears it up.

that's supposedly be like this:
B = [n/m] * i - 1,
Math.floor(n/m) => it should be th floor of the result..
i understand how to compute for the base pointers, but how do i get into which stack? plus the stack should be implemented as link. should i do this?:

Node Stack[];

i got this push method in the book that i use for multiple stacks:

public void push(int i, Object item) {

if (T[i]== B[i+1]) MStack(i);
S[++T[i]]= item;
}

I think T if for the top and B is for the base. how do i declare them ?like:

double T[];
double B[];

To initialize the stack, tops are set to point to base addresses, i.e.,
T = B

so if n = 300 and m stacks = 3 (that is i want 3 stacks)then:

B = Math.floor(n/m) * i - 1.
B[0] = -1
B[1]= 99
B[2]= 199
B[m] = B[3] = 299

how do i set tops to these base pointer? do i loop them?:-/

[ezkonekgal]

I want to greet everyone here a happy new year!:)

[verruckt24]

To say the least your requirements are very vague. If you have been given the base pointer address calculation as according to the formula, how can you be implementing the stack as a list ? If your base pointer address calculation is to be taken into consideration then your stacks should be in an array with their base pointers at the calculated locations of the array. Also the Multiple stack definition as read by me on the internet specifies that these are implemented in an array where say there are two stacks then these have base pointers at the opposite ends of the array and they grow towards each other.
How have you been asked to implement these in a List, detail on that.
Also to answer your question on setting tops you can set them to the base pointers while setting the base pointers themselves. Why, can't you ?

[ezkonekgal]

here is what i did to compute the formula:

public void computeBase(){
		int n = size;
		int m = 3;
		for (int i = 0; i <= 3; i++){
			Base[i]= Math.floor(n/m) * i -1;
			Object base = Base[i];
			setBase(base);
		}
	}

and this i the rest of the new code i did:

import java.io.*;



public class Mstack1 {

	Node top;
	int size = 300;
	Object S[] = new Object[size];
	Object Top[];
	Object Base[];
	String item;
	int i;

	public void computeBase(){
		int n = size;
		int m = 3;
		for (int i = 0; i <= 3; i++){
			Base[i]= Math.floor(n/m) * i -1;
			Object base = Base[i];
			setBase(base);
		}
	}
	class Node{
		Object info;
		Node link;
	}

	public void setBase(Object base){
		Top[i] = Base[i];
	}

	public void push(Object item) {
		if (Top[i]==Base[i+1]){
			System.out.println("Stack"+ i + "is full.");
		}else{
			Node newNode = new Node();
			newNode.info = item;
			newNode.link = top;
			top = newNode;
		}
	}

	public Object pop(int i){
		Node temp;
		if (isEmpty(i)){
			System.out.println("Stack has nothing inside it");
		}
		temp = top;
		top = top.link;
		return temp.info;
	}

	public boolean isEmpty(int i){
		return (Top[i] == Base[i]);
	}

	public String getValue(){
		return item;
	}

	public static void main (String []args){
		Mstack1 s = new Mstack1();

		try{
			InputStreamReader ir = new InputStreamReader(System.in);
			BufferedReader bf = new BufferedReader(ir);
			System.out.println("Where do you want to enter an element?" + "\n B1" + "\n B2" + "\n B3");
			String str = bf.readLine();
			if(str.equalsIgnoreCase("B1")){
				int i = 0;
				s.push(i);
				System.out.println("Enter element:");
				String item = bf.readLine();
				s.push(item);
			}else if(str.equals("B2")){
				System.out.println("Enter element:");
				String item = bf.readLine();
				s.push(item);
			}
		}catch(IOException e){}

	}
	class StackException extends RuntimeException{
		public StackException(String err){
			super(err);
		}
	}
}

what i did is create an array, initialize its size and implementing the stack as node (although i didn't know if i did it)..