![]() ![]() Initialize all stacks as empty with -1 Initialize n and k, and allocate memory for all arrays Array of size n to store next entry in all stacks and free list top array store indexes of top elements of stacks Array of size n to store elements i.e elements that will be pushed in stack Update the starting index of the free list as, free = index. Add the free slot to the free list as next = free.ĭ. Remove the element from the stack by updating the head/top of the stack list as top = next.Ĭ. Find the index of the top element of the stack and store it in a variable say index, i.e. Add the element to the stack by updating the head/top of the stack list as top = index. Update the next pointer of the new element as next = top.Į. Store the new element in the free slot as arr = X.ĭ. Update the starting index of the free list as, free = next.Ĭ. Store the index of the first free slot in a temporary variable, say index, i.e. Create a variable to store the starting index of the free list.Set the last pointer of the free list to -1, i.e.So, for every index ‘i’ in next, set next = i + 1. ![]() Initially, the complete array arr belongs to the free list i.e (No element is pushed yet).This will store the top element of every stack. Create an array top of size N, and initialize all the indices with -1.Create an array arr of size S, Array that will store the content of the stacks.S = Number of stacks, N = Size of array Algorithm: If arr is a free (i.e no element is stored there), then next stores the index of the next free slot available in the array. the next free space available in the array. For example, let’s say ith index of arr i.e arr stores the actual elements of the stack then next stores the index of the next (lower) element in the stack.ī. This next array is used to keep track of two things:-Ī. Its size will be equal to the number of stacks. The top array is used to store the index of the top element of the stack.In this approach, we are going to use two extra arrays named top and next. This method is space efficient, and the idea is to use two extra arrays for efficient implementation of k stacks in an array.Because in this example we still have free spaces in the first stack but still we cannot use those free spaces for stack 2. 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. pop(int sn): pops an element from stack number ‘sn’ where sn ranges from 0 to k-1.ĭivide the array into sections of (n/k) size:-Ī 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.push(int x, int sn): pushes element x to stack number ‘sn’ where sn ranges from 0 to k-1.The K stacks must support these functions Our task is to Implement K stacks that should use only one array. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |