Skip to main content
Code Review

Return to Answer

added 3 characters in body
Source Link
KeithS
KeithS
  • 1.7k
  • 4
  • 13
  • 17

Another option is to use the array to implement a simple "hashset"-like structure (with 3 "hashes"; one per stack). The general is to create a Node struct, which your primary array will hold copies of. Each Node holds the actual value pushed, and a link tothe index of the next lower Node in that stack. To push, create a Node, assign the value and the index of the current "top" node of that Stack, then put that Node in the first available spot in the array (which you must keep track of because elements can be added/removed from pretty much anywhere) and remember its location as the new "top". To pop, do the opposite; go to the remembered "top" index, get that Node, then clear that index (checking to see if it's a lower index than the currently-known "first available"), and set the "top" node to the popped node's "next" index. The advantage is O(1) access in most cases (pushing a node, which requires determining the next null index of the array for the next push, is worst-case linear); the disadvantage is extra space necessary to maintain the links between nodes of a stack.

Another option is to use the array to implement a simple "hashset"-like structure (with 3 "hashes"; one per stack). The general is to create a Node struct, which your primary array will hold copies of. Each Node holds the actual value pushed, and a link to the next lower Node in that stack. To push, create a Node, assign the value and the index of the current "top" node of that Stack, then put that Node in the first available spot in the array (which you must keep track of because elements can be added/removed from pretty much anywhere) and remember its location as the new "top". To pop, do the opposite; go to the remembered "top" index, get that Node, then clear that index (checking to see if it's a lower index than the currently-known "first available"), and set the "top" node to the popped node's "next" index. The advantage is O(1) access in most cases (pushing a node, which requires determining the next null index of the array for the next push, is worst-case linear); the disadvantage is extra space necessary to maintain the links between nodes of a stack.

Another option is to use the array to implement a simple "hashset"-like structure (with 3 "hashes"; one per stack). The general is to create a Node struct, which your primary array will hold copies of. Each Node holds the actual value pushed, and the index of the next lower Node in that stack. To push, create a Node, assign the value and the index of the current "top" node of that Stack, then put that Node in the first available spot in the array (which you must keep track of because elements can be added/removed from pretty much anywhere) and remember its location as the new "top". To pop, do the opposite; go to the remembered "top" index, get that Node, then clear that index (checking to see if it's a lower index than the currently-known "first available"), and set the "top" node to the popped node's "next" index. The advantage is O(1) access in most cases (pushing a node, which requires determining the next null index of the array for the next push, is worst-case linear); the disadvantage is extra space necessary to maintain the links between nodes of a stack.

added 1080 characters in body
Source Link
KeithS
KeithS
  • 1.7k
  • 4
  • 13
  • 17

Another option is to use the array to implement a simple "hashset"-like structure (with 3 "hashes"; one per stack). The general is to create a Node struct, which your primary array will hold copies of. Each Node holds the actual value pushed, and a link to the next lower Node in that stack. To push, create a Node, assign the value and the index of the current "top" node of that Stack, then put that Node in the first available spot in the array (which you must keep track of because elements can be added/removed from pretty much anywhere) and remember its location as the new "top". To pop, do the opposite; go to the remembered "top" index, get that Node, then clear that index (checking to see if it's a lower index than the currently-known "first available"), and set the "top" node to the popped node's "next" index. The advantage is O(1) access in most cases (pushing a node, which requires determining the next null index of the array for the next push, is worst-case linear); the disadvantage is extra space necessary to maintain the links between nodes of a stack.

Another option is to use the array to implement a simple "hashset"-like structure (with 3 "hashes"; one per stack). The general is to create a Node struct, which your primary array will hold copies of. Each Node holds the actual value pushed, and a link to the next lower Node in that stack. To push, create a Node, assign the value and the index of the current "top" node of that Stack, then put that Node in the first available spot in the array (which you must keep track of because elements can be added/removed from pretty much anywhere) and remember its location as the new "top". To pop, do the opposite; go to the remembered "top" index, get that Node, then clear that index (checking to see if it's a lower index than the currently-known "first available"), and set the "top" node to the popped node's "next" index. The advantage is O(1) access in most cases (pushing a node, which requires determining the next null index of the array for the next push, is worst-case linear); the disadvantage is extra space necessary to maintain the links between nodes of a stack.

Source Link
KeithS
KeithS
  • 1.7k
  • 4
  • 13
  • 17

The implementation you have basically splits your array into 3 equal sub-arrays, and each stack can only use the elements of its subarray. It would be roughly the same as setting the first index to 0, the second index to array.length/3, and the third to array.length*2/3. Instead, you're working based on modular congrence; the first stack uses indices where that have a modulo by 3 of 0, the second stack 1 and the third stack 2.

"Improving" it depends on what you want to improve; space efficiency or performance? You could create a stack for which any number of unused indices could store values of any one stack, by implementing two "slide" helper methods:

private void SlideRight(int index, int stackNum)
{
    //keep a count of all elements in the array and make sure this operation
    //will not push an element "off the edge"
    if(totalCount + offset > array.length) throw new StackOverflowException();

    for(int i=totalCount-1; i>index; i--)
       array[i] = array[i-1];

    for(int j=stackNum; j<stacks.length; j++)
       stacks[j]++;
}

private void SlideLeft(int index, int stackNum)
{
    for(int i=index; i<totalCount-1; i++)
       array[i] = array[i+1];

    for(int j=stackNum; j<stacks.length; j++)
       stacks[j]++;
}

These can be used to push and pop values into any stack, up to the full capacity of the array:

public int[] stacks = new int[3]{0,0,0};

public void Push(int value, int stackNum)
{
   SlideRight(stacks[stackNum-1], stackNum);
   array[stacks[stackNum-1]] = value;
   stacks[stackNum-1]++;
   totalCount++;
}

public void Pop(int stackNum)
{
   int result = array[stacks[stackNum-1]]
   SlideLeft(stacks[stackNum-1], stackNum);
   stacks[stackNum-1]--;
   totalCount--;
   return result;
}

The downside is having to perform count-N swaps to insert a value into index N (which basically means that pushing or popping from stack X is bound in time to the number of elements in stacks higher than X).