Implement 3 stacks in 1 array


Implement k stacks in a single array
https://martinm2w.wordpress.com/2012/05/28/3-1-stack-implement-3-stacks-using-a-single-array/
Approach 2:
In this approach, any stack can grow as long as there is any free space in the array.
We sequentially allocate space to the stacks and we link new blocks to the previous block. This means any new element in a stack keeps a pointer to the previous top element of that particular stack.
In this implementation, we face a problem of unused space. For example, if a stack deletes some of its elements, the deleted elements may not necessarily appear at the end of the array. So, in that case, we would not be able to use those newly freed spaces.
To overcome this deficiency, we can maintain a free list and the whole array space would be given initially to the free list. For every insertion, we would delete an entry from the free list. In case of deletion, we would simply add the index of the free cell to the free list.
In this implementation we would be able to have flexibility in terms of variable space utilization but we would need to increase the space complexity.
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://martinm2w.wordpress.com/2012/05/28/3-1-stack-implement-3-stacks-using-a-single-array/
Approach 1:
Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: “[“ means inclusive, while “(“ means exclusive of the end point).
»»for stack 1, we will use [0, n/3)
»»for stack 2, we will use [n/3, 2n/3)
»»for stack 3, we will use [2n/3, n)
This solution is based on the assumption that we do not have any extra information about the usage of space by individual stacks and that we can’t either modify or use any extra space. With these constraints, we are left with no other choice but to divide equally.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int stackSize = 300;
int[] buffer = new int [stackSize * 3];
int[] stackPointer = {0, 0, 0}; // stack pointers to track top elem
void push(int stackNum, int value) {
// Find the index of the top element in the array + 1, and increment the stack pointer
    int index = stackNum * stackSize + stackPointer[stackNum] + 1;
    stackPointer[stackNum]++;
    buffer[index] = value;
}
 
int pop(int stackNum) {
    int index = stackNum * stackSize + stackPointer[stackNum];
    stackPointer[stackNum]--;
    int value = buffer[index];
    buffer[index]=0;
    return value;
}
 
int peek(int stackNum) {
    int index = stackNum * stackSize + stackPointer[stackNum];
    return buffer[index];
}
 
boolean isEmpty(int stackNum) {
    return stackPointer[stackNum] == stackNum*stackSize;
}
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];
    }

Implement 3 stacks in 1 array
Method 2 - Getting space efficient solution
Here is the procedure to do so: 
  1. Define two stacks beginning at the array endpoints and growing in opposite directions.
  2. Define the third stack as starting in the middle and growing in any direction you want.
  3. Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing.

So this is what happens:  
  • First stack grows from left to right.
  • Second stack grows from right to left.
  • Third stack starts from the middle. Suppose odd sized array for simplicity. Then third stack grows like this:
    
    * * * * * * * * * * *
          5 3 1 2 4
First and second stacks are allowed to grow maximum at the half size of array. The third stack can grow to fill in the whole array at a maximum.
Worst case scenario is when one of the first two arrays(arrays at both ends) grows at 50% of the array. Then there is a 50% waste of the array. To optimize the efficiency the third array (i.e. the array in the middle) must be selected to be the one that grows quicker than the other two.
From http://stackoverflow.com/questions/4770627/how-to-implement-3-stacks-with-one-array
Space (not time) efficient. You could:
1) Define two stacks beginning at the array endpoints and growing in opposite directions.
2) Define the third stack as starting in the middle and growing in any direction you want.
3) Redefine the Push op, so that when the operation is going to overwrite other stack, you shift the whole middle stack in the opposite direction before Pushing.
You need to store the stack top for the first two stacks, and the beginning and end of the third stack in some structure.
Edit
alt text
public class StackMFromArray {
    private StackNode[] stackNodes = null;
    private static int CAPACITY = 10;
    private int freeListTop = 0;
    private int size = 0;
    private int[] stackPointers = { -1, -1, -1 };
    StackMFromArray() {
        stackNodes = new StackNode[CAPACITY];
        initFreeList();
    }
    private void initFreeList() {
        for (int i = 0; i < CAPACITY; i++) {
            stackNodes[i] = new StackNode(0, i + 1);
        }
    }
    public void push(int stackNum, int value) throws Exception {
        int freeIndex;
        int currentStackTop = stackPointers[stackNum - 1];
        freeIndex = getFreeNodeIndex();
        StackNode n = stackNodes[freeIndex];
        n.prev = currentStackTop;
        n.value = value;
        stackPointers[stackNum - 1] = freeIndex;
    }
    public StackNode pop(int stackNum) throws Exception {
        int currentStackTop = stackPointers[stackNum - 1];
        if (currentStackTop == -1) {
            throw new Exception("UNDERFLOW");
        }
        StackNode temp = stackNodes[currentStackTop];
        stackPointers[stackNum - 1] = temp.prev;
        freeStackNode(currentStackTop);
        return temp;
    }
    private int getFreeNodeIndex() throws Exception {
        int temp = freeListTop;
        if (size >= CAPACITY)
            throw new Exception("OVERFLOW");
        freeListTop = stackNodes[temp].prev;
        size++;
        return temp;
    }
    private void freeStackNode(int index) {
        stackNodes[index].prev = freeListTop;
        freeListTop = index;
        size--;
    }
http://www.cnblogs.com/grandyang/p/4675640.html

http://www.geeksforgeeks.org/efficiently-implement-k-stacks-single-array/
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.
Read full article from Implement 3 stacks in 1 array ~ KodeKnight

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