{"id":9217,"date":"2022-08-26T11:24:09","date_gmt":"2022-08-26T11:24:09","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9217"},"modified":"2022-09-13T13:37:08","modified_gmt":"2022-09-13T13:37:08","slug":"how-to-efficiently-implement-k-stacks-in-a-single-array","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/how-to-efficiently-implement-k-stacks-in-a-single-array\/","title":{"rendered":"How to efficiently implement K Stacks in a single Array?"},"content":{"rendered":"

\"\"<\/p>\n<\/p>\n

Our task is to Implement K stacks that should use only one array. The K stacks must support these functions <\/p>\n

    \n
  1. push(int x, int sn)<\/strong>: pushes element x to stack number \u2018sn\u2019 where sn ranges from 0 to k-1. <\/li>\n
  2. pop(int sn)<\/strong>: pops an element from stack number \u2018sn\u2019 where sn ranges from 0 to k-1.<\/li>\n<\/ol>\n

    Method 1:<\/h3>\n

    Divide the array<\/a> into sections of (n\/k) size:-<\/strong>
    \nA simple way to implement k stacks is to divide the array into k sections of size (n\/k) each and these (n\/k) sections are for different stacks.<\/p>\n

    \"\"<\/p>\n

    In the above example, we have constructed two stacks using a single array but the problem is that this approach is not using array spaces efficiently. Because in this example we still have free spaces in the first stack but still we cannot use those free spaces for stack 2.<\/p>\n

    Method 2:<\/h3>\n
      \n
    1. This method is space efficient, and the idea is to use two extra arrays for efficient implementation of k stacks in an array. In this approach, we are going to use two extra arrays named top and next.<\/li>\n
    2. The top array is used to store the index of the top element of the stack. Its size will be equal to the number of stacks.<\/li>\n
    3. The next array is an array of size N. This next array is used to keep track of two things:-
      \na. the next (lower) element of the stack. For example, let’s say ith index of arr i.e arr[i] stores the actual elements of the stack then next[i] stores the index of the next (lower) element in the stack.
      \nb. the next free space available in the array. If arr[i] is a free (i.e no element is stored there), then next[i] stores the index of the next free slot available in the array.<\/li>\n<\/ol>\n

      Input<\/strong>:
      \nS = Number of stacks, N = Size of array <\/p>\n

      Algorithm:<\/h3>\n
        \n
      1. Create an array arr of size S, Array that will store the content of the stacks.<\/li>\n
      2. Create an array top of size N, and initialize all the indices with -1. This will store the top element of every stack.<\/li>\n
      3. Create an array next of size S.<\/li>\n
      4. Initially, the complete array arr belongs to the free list i.e (No element is pushed yet). So, for every index \u2018i\u2019 in next, set next[i] = i + 1. <\/li>\n
      5. Set the last pointer of the free list to -1, i.e. next[S-1] = -1.<\/li>\n
      6. Create a variable to store the starting index of the free list. i.e free = 0.<\/li>\n<\/ol>\n

        Push Operation<\/strong>:<\/p>\n

          \n
        1. If free= – 1, means array is full. So, we cannot insert a new element.<\/li>\n
        2. Otherwise,
          \na. Store the index of the first free slot in a temporary variable, say index, i.e. index = free.
          \nb. Update the starting index of the free list as, free = next[freeStart].
          \nc. Store the new element in the free slot as arr[index] = X.
          \nd. Update the next pointer of the new element as next[index] = top[M-1].
          \ne. Add the element to the stack by updating the head\/top of the stack list as top[M-1] = index.
          \nf. Return true.<\/li>\n<\/ol>\n

          Pop Operation:<\/strong><\/p>\n

            \n
          1. If top[M-1] = – 1, the Mth stack is empty. So, just return -1.<\/li>\n
          2. Otherwise,
            \na. Find the index of the top element of the stack and store it in a variable say index, i.e. index = top[M-1].
            \nb. Remove the element from the stack by updating the head\/top of the stack list as top[M-1] = next[index].
            \nc. Add the free slot to the free list as next[index] = free.
            \nd. Update the starting index of the free list as, free = index.
            \ne. Return the popped element.<\/li>\n<\/ol>\n

            Code Implementation:<\/h3>\n\t\t\t\t\t\t