Implement k stacks in a single array


Implement k stacks in a single array
Problem 2: How can you implement n (n > 2) stacks in a single array, where no stack overflows until no space left in the entire array space?
Let’s take three stacks sharing an array with capacity 10 as an example. Figure 3 shows the initial status for the array and stacks. Each item in the array has two blocks, one for item data and the other for the index of another block.
Figure 3: Initial status of three stacks sharing an array


As shown in Figure 3, each item is linked to the next item (the link block of the ith item is i+1). The head of list for available items in the array points to the item at position 0, which is the Ava pointer in the figure. Since three stacks are empty, their top (Top1, Top2 and Top3 in the figure) are initialized as -1.

Let’s try to push an item a into the first stack. Currently the first available item is at the position 0, so we set its data block as a. The link block of the item is 1, which means the next available item is at the position 1, so we update the Ava pointer to the position 1. Additionally, the link block of the item at the position 1 should be updated to -1, the previous top index of the first stack. Lastly, we update to top index of the first stack to 0. The status of the array and stacks are shown in Figure 4.
Figure 4: The status after pushing a into the first stack
Let’s push two more items b and c into the first stack. The operations are similar as before, and the status is shown in Figure 5.
Figure 5: The status after adding two more items, b and c, into the first stack
In the next step we are going to push another d into the second stack. Most operations are similar as before. The link block in the item at the position 3 is updated to -1, since the second stack is empty before and its top index is -1 previously. And then the top index of the second stack is updated to 3. The status after adding d into the second stack is shown in Figure 6.

Figure 6: The status after pushing d into the second stack
If we continue to push three more item ef, and g into the second stack, the status is shown in Figure 7.
Figure 7: The status after pushing three more items, e, f, and g, into the second stack
At this time we are going to pop an item from the first stack. Since the top index of the first stack is 2, the item to be popped off is at the position 2. The link value in that item is 1, which means the previous top in the first stack is at the position 1 in the array, so we update the top index of the first stack as 1. Now the item at the position 2 becomes available, it should be linked to the list for available items. We move the Ava pointer to 2, and then update the link value of the item at the position 2 as 7, which is the previous head position of the list for available items. The status is shown in Figure 8.
Figure 8: The status after popping an item from the first stack
If we pop an item off the second stack, the item at the position 6 will be linked to the list for available items too. Figure 9 depicts the status after the related operations.
Figure 9: The status after popping an item off the second stack
If we push h into the third stack, it will be placed into the item at the position 6 because Ava points to that item. The next available item is at the position 2 (the link value in the item at the position 6). Therefore, the head of the list for available items points to location 2, as shown in Figure 10.
Figure 10: The status after pushing h into the third stack
Let’s continue to push four more items into the third stack, ijk, and l. The status after these four items are pushed is shown in Figure 11. At this time, there are two items in the first stack (a and b), three items in the second stack (de and f), and five items in the third stack (hijk, and l). Please note that items inside a stack are not necessarily adjacent. 
Figure 11: The status after pushing i, j, k, l into the third stack
After l is pushed into the item at the position 9, the Ava pointer is update to -1 (the previous link value in the item at the position 9), which means all items in the array have been occupied by stacks. We can’t push more items until some items are popped off.

template <typename T, int capacity, int count> class Stacks

{
public:
    Stacks()
    {
        int i;
        for(i = 0; i < capacity - 1; ++i)
            items[i].link = i + 1;
        items[i].link = -1;
        emptyHead = 0;

        for(i = 0; i < count; ++i)
            stackHead[i] = -1;
    }

    T top(int stackIndex)
    {
        validateIndex(stackIndex);
        if(empty(stackIndex))
            throw new exception("The stack is empty.");

        return items[stackHead[stackIndex]].data;
    }

    void push(int stackIndex, const T& item)
    {
        validateIndex(stackIndex);
        if(full())
            throw new exception("All space has been occupied.");

        Item<T>& block = items[emptyHead];
        int nextEmpty = block.link;

        block.data = item;
        block.link = stackHead[stackIndex];
        stackHead[stackIndex] = emptyHead;

        emptyHead = nextEmpty;
    }

    void pop(int stackIndex)
    {
        validateIndex(stackIndex);
        if(empty(stackIndex))
            throw new exception("The stack is empty.");

        Item<T>& block = items[stackHead[stackIndex]];
        int nextItem = block.link;

        block.link = emptyHead;
        emptyHead = stackHead[stackIndex];
        stackHead[stackIndex] = nextItem;
    }

    bool empty(int stackIndex)
    {
        return (stackHead[stackIndex] < 0);
    }

private:
    void validateIndex(int stackIndex)
    {
        if(stackIndex < 0 || stackIndex >= count)
            throw new exception("Invalid index of stack.");
    }

    bool full()
    {
        return (emptyHead < 0);
    }

private:
    template <typename T> struct Item
    {
        T data;
        int link;
    };

private:
    Item<T> items[capacity];
    int emptyHead;
    int stackHead[count];
};
Create a data structure kStacks that represents k stacks. Implementation of kStacks should use only one array, i.e., k stacks should use the same array for storing elements. 

Following functions must be supported by kStacks.

push(int x, int sn) –> pushes x to stack number ‘sn’ where sn is from 0 to k-1
pop(int sn) –> pops an element from stack number ‘sn’ where sn is from 0 to k-1

Method 2 (A space efficient implementation)
The idea is to use two extra arrays for efficient implementation of k stacks in an array. This may not make much sense for integer stacks, but stack items can be large for example stacks of employees, students, etc where every item is of hundreds of bytes. For such large stacks, the extra space used is comparatively very less as we use two integer arrays as extra space.
Following are the two extra arrays are used:
1) top[]: This is of size k and stores indexes of top elements in all stacks.
2) next[]: This is of size n and stores indexes of next item for the items in array arr[]. Here arr[] is actual array that stores k stacks.
Together with k stacks, a stack of free slots in arr[] is also maintained. The top of this stack is stored in a variable ‘free’.
All entries in top[] are initialized as -1 to indicate that all stacks are empty. All entries next[i] are initialized as i+1 because all slots are free initially and pointing to next slot. Top of free stack, ‘free’ is initialized as 0.

The best part of above implementation is, if there is a slot available in stack, then an item can be pushed in any of the stacks, i.e., no wastage of space.
    static class KStack 
    {
        int arr[];   // Array of size n to store actual content to be stored in stacks
        int top[];   // Array of size k to store indexes of top elements of stacks
        int next[];  // Array of size n to store next entry in all stacks
                     // and free list
        int n, k;
        int free; // To store beginning index of free list
  
        //constructor to create k stacks in an array of size n
        KStack(int k1, int n1) 
        {
            // Initialize n and k, and allocate memory for all arrays
            k = k1;
            n = n1;
            arr = new int[n];
            top = new int[k];
            next = new int[n];
  
            // Initialize all stacks as empty
            for (int i = 0; i < k; i++)
                top[i] = -1;
  
            // Initialize all spaces as free
            free = 0;
            for (int i = 0; i < n - 1; i++)
                next[i] = i + 1;
            next[n - 1] = -1; // -1 is used to indicate end of free list
        }
  
        // A utility function to check if there is space available
        boolean isFull() 
        {
            return (free == -1);
        }
  
        // To push an item in stack number 'sn' where sn is from 0 to k-1
        void push(int item, int sn) 
        {
            // Overflow check
            if (isFull()) 
            {
                System.out.println("Stack Overflow");
                return;
            }
  
            int i = free; // Store index of first free slot
  
            // Update index of free slot to index of next slot in free list
            free = next[i];
  
            // Update next of top and then top for stack number 'sn'
            next[i] = top[sn];
            top[sn] = i;
  
            // Put the item in array
            arr[i] = item;
        }
  
        // To pop an from stack number 'sn' where sn is from 0 to k-1
        int pop(int sn) 
        {
            // Underflow check
            if (isEmpty(sn)) 
            {
                System.out.println("Stack Underflow");
                return Integer.MAX_VALUE;
            }
  
            // Find index of top item in stack number 'sn'
            int i = top[sn];
  
            top[sn] = next[i]; // Change top to store next of previous top
  
            // Attach the previous top to the beginning of free list
            next[i] = free;
            free = i;
  
            // Return the previous top item
            return arr[i];
        }
  
        // To check whether stack number 'sn' is empty or not
        boolean isEmpty(int sn) 
        {
            return (top[sn] == -1);
        }
  
    }



https://www.byte-by-byte.com/nstacks/
public class Stacks {
    int[] topOfStack;
    int[] stackData;
    int[] nextIndex;
    int nextAvailable = 0;
    public Stacks(int numStacks, int capacity) {
        topOfStack = new int[numStacks];
        for (int i = 0; i < topOfStack.length; i++) {
            topOfStack[i] = -1;
        }
        stackData = new int[capacity];
        nextIndex = new int[capacity];
        for (int i = 0; i < nextIndex.length - 1; i++) {
            nextIndex[i] = i+1;
        }
        nextIndex[nextIndex.length - 1] = -1;
    }
    public void push(int stack, int value) {
        if (stack < 0 || stack >= topOfStack.length) {
            throw new IndexOutOfBoundsException();
        }
        if (nextAvailable < 0) return;
        int currentIndex = nextAvailable;
        nextAvailable = nextIndex[currentIndex];
        stackData[currentIndex] = value;
        nextIndex[currentIndex] = topOfStack[stack];
        topOfStack[stack] = currentIndex;
    }
    public int pop(int stack) {
        if (stack < 0 || stack >= topOfStack.length
              || topOfStack[stack] < 0) {
            throw new IndexOutOfBoundsException();
        }
        int currentIndex = topOfStack[stack];
        int value = stackData[currentIndex];
        topOfStack[stack] = nextIndex[currentIndex];
        nextIndex[currentIndex] = nextAvailable;
        nextAvailable = currentIndex;
        return value;
    }
}


Method 1 (Divide the array in slots of size n/k) 
A simple way to implement k stacks is to divide the array in k slots of size n/k each, and fix the slots for different stacks, i.e., use arr[0] to arr[n/k-1] for first stack, and arr[n/k] to arr[2n/k-1] for stack2 where arr[] is the array to be used to implement two stacks and size of array be n.
The problem with this method is inefficient use of array space. A stack push operation may result in stack overflow even if there is space available in arr[].
Describe how you could use a single array to implement three stacks.
https://hellosmallworld123.wordpress.com/2014/05/09/describe-how-you-could-use-a-single-array-to-implement-three-stacks/
The other solution is to use a pointer to keep track of the previous location for every entry. The user can add elements as long as there is free space in the array. We also need to have a free list to keep track of all the free elements that was popped. So first we add all the elements into the free list. we can only use integer to track the head of the stacks.
public class Stack {
    int STACKSIZE = 300;
    int [] head = {-1, -1, -1};
    StackNode [] s = new StackNode[STACKSIZE];
    int [] free = new int [STACKSIZE];
    int firstFree = 0;
    public Stack() {
        for (int i = 0; i < STACKSIZE; i++) {
            free[i] = i;
        }
    }
     
    public boolean push(int stackNum, int val) {
        if (firstFree == STACKSIZE)
            return false; //no space to push
        s[free[firstFree]] = new StackNode(val);
        s[free[firstFree]].pre = head[stackNum];
        head[stackNum] = free[firstFree];
        firstFree++;
        return true;
    }
     
    public int pop(int stackNum) {
        if (head[stackNum] == -1)
            return -1; // empty stack
        StackNode n = s[head[stackNum]];
        firstFree--;
        free[firstFree] = head[stackNum]; // add to freelist
        head[stackNum] = n.pre;
        return n.val;
    }
     
    public int peek(int stackNum) {
        if (head[stackNum] == -1)
            return -1; //empty stack
        return s[head[stackNum]].val;
    }
}
public class StackNode {
    int val;
    int pre; // only track the previous index, not the node itself
    public StackNode (int v) {
        this.val = v;
    }
}

https://github.com/wzhishen/cracking-the-coding-interview/blob/master/src/chap03/Q1.java
Not good: space wasted.
public class Q1 {
    //Describe how you could use a single array to implement three stacks.
 
    final int STACK_SIZE = 100;
    int[] buffer = new int[3 * STACK_SIZE];
    int[] stackPointer = {-1, -1, -1}; // relative index
 
    void push(int stackNum, int x) {
        if (isFull(stackNum))
            throw new IllegalArgumentException("Stack is full!");
        ++stackPointer[stackNum];
        buffer[getAbsIndex(stackNum)] = x;
    }
 
    int pop(int stackNum) {
        int ret = peek(stackNum);
        --stackPointer[stackNum];
        return ret;
    }
 
    int peek(int stackNum) {
        if (isEmpty(stackNum))
            throw new IllegalArgumentException("Stack is empty!");
        return buffer[getAbsIndex(stackNum)];
    }
 
    boolean isEmpty(int stackNum) {
        return stackPointer[stackNum] == -1;
    }
 
    boolean isFull(int stackNum) {
        return stackPointer[stackNum] == STACK_SIZE - 1;
    }
 
    private int getAbsIndex(int stackNum) {
        return stackNum * STACK_SIZE + stackPointer[stackNum];
    }

Read full article from How to efficiently implement k stacks in a single array? - GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts