Hemos discutido la implementación eficiente del espacio de 2 pilas en una sola array . En esta publicación, se analiza una solución general para k pilas. A continuación se presenta el enunciado detallado del problema. Cree una estructura de datos kStacks que represente k pilas. La implementación de kStacks debe usar solo una array, es decir, las pilas k deben usar la misma array para almacenar elementos.
Las siguientes funciones deben ser compatibles con kStacks. push(int x, int sn) -> empuja x al número de pila ‘sn’ donde sn es de 0 a k-1 pop(int sn) -> extrae un elemento del número de pila ‘sn’ donde sn es de 0 a k -1
Método 1 (Dividir la array en ranuras de tamaño n/k) Una forma sencilla de implementar k pilas es dividir la array en k ranuras de tamaño n/k cada una y arreglar las ranuras para diferentes pilas, es decir, usar arr[0 ] a arr[n/k-1] para la primera pila, y arr[n/k] a arr[2n/k-1] para stack2 donde arr[] es la array que se usará para implementar dos pilas y el tamaño de la array ser n. El problema con este método es el uso ineficiente del espacio de la array. Una operación de inserción de pila puede provocar un desbordamiento de pila incluso si hay espacio disponible en arr[]. Por ejemplo, supongamos que k es 2 y el tamaño de la array (n) es 6 y empujamos 3 elementos al primero y no empujamos nada a la segunda pila. Cuando empujamos el cuarto elemento al primero, habrá un desbordamiento incluso si tenemos espacio para 3 elementos más en la array.
C++
// A C++ program to demonstrate implementation of k stacks in a single // array in time and space efficient way #include<bits/stdc++.h> using namespace std; // A C++ class to represent k stacks in a single array of size n class kStacks { 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 public: //constructor to create k stacks in an array of size n kStacks(int k, int n); // A utility function to check if there is space available bool 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); // To pop an from stack number 'sn' where sn is from 0 to k-1 int pop(int sn); // To check whether stack number 'sn' is empty or not bool isEmpty(int sn) { return (top[sn] == -1); } }; //constructor to create k stacks in an array of size n kStacks::kStacks(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 } // To push an item in stack number 'sn' where sn is from 0 to k-1 void kStacks::push(int item, int sn) { // Overflow check if (isFull()) { cout << "\nStack Overflow\n"; 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 kStacks::pop(int sn) { // Underflow check if (isEmpty(sn)) { cout << "\nStack Underflow\n"; return INT_MAX; } // 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]; } /* Driver program to test twoStacks class */ int main() { // Let us create 3 stacks in an array of size 10 int k = 3, n = 10; kStacks ks(k, n); // Let us put some items in stack number 2 ks.push(15, 2); ks.push(45, 2); // Let us put some items in stack number 1 ks.push(17, 1); ks.push(49, 1); ks.push(39, 1); // Let us put some items in stack number 0 ks.push(11, 0); ks.push(9, 0); ks.push(7, 0); cout << "Popped element from stack 2 is " << ks.pop(2) << endl; cout << "Popped element from stack 1 is " << ks.pop(1) << endl; cout << "Popped element from stack 0 is " << ks.pop(0) << endl; return 0; }
Java
// Java program to demonstrate implementation of k stacks in a single // array in time and space efficient way public class GFG { // A Java class to represent k stacks in a single array of size n 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); } } // Driver program public static void main(String[] args) { // Let us create 3 stacks in an array of size 10 int k = 3, n = 10; KStack ks = new KStack(k, n); ks.push(15, 2); ks.push(45, 2); // Let us put some items in stack number 1 ks.push(17, 1); ks.push(49, 1); ks.push(39, 1); // Let us put some items in stack number 0 ks.push(11, 0); ks.push(9, 0); ks.push(7, 0); System.out.println("Popped element from stack 2 is " + ks.pop(2)); System.out.println("Popped element from stack 1 is " + ks.pop(1)); System.out.println("Popped element from stack 0 is " + ks.pop(0)); } } // This code is Contributed by Sumit Ghosh
Python3
# Python 3 program to demonstrate implementation # of k stacks in a single array in time and space # efficient way class KStacks: def __init__(self, k, n): self.k = k # Number of stacks. self.n = n # Total size of array holding # all the 'k' stacks. # Array which holds 'k' stacks. self.arr = [0] * self.n # All stacks are empty to begin with # (-1 denotes stack is empty). self.top = [-1] * self.k # Top of the free stack. self.free = 0 # Points to the next element in either # 1. One of the 'k' stacks or, # 2. The 'free' stack. self.next = [i + 1 for i in range(self.n)] self.next[self.n - 1] = -1 # Check whether given stack is empty. def isEmpty(self, sn): return self.top[sn] == -1 # Check whether there is space left for # pushing new elements or not. def isFull(self): return self.free == -1 # Push 'item' onto given stack number 'sn'. def push(self, item, sn): if self.isFull(): print("Stack Overflow") return # Get the first free position # to insert at. insert_at = self.free # Adjust the free position. self.free = self.next[self.free] # Insert the item at the free # position we obtained above. self.arr[insert_at] = item # Adjust next to point to the old # top of stack element. self.next[insert_at] = self.top[sn] # Set the new top of the stack. self.top[sn] = insert_at # Pop item from given stack number 'sn'. def pop(self, sn): if self.isEmpty(sn): return None # Get the item at the top of the stack. top_of_stack = self.top[sn] # Set new top of stack. self.top[sn] = self.next[self.top[sn]] # Push the old top_of_stack to # the 'free' stack. self.next[top_of_stack] = self.free self.free = top_of_stack return self.arr[top_of_stack] def printstack(self, sn): top_index = self.top[sn] while (top_index != -1): print(self.arr[top_index]) top_index = self.next[top_index] # Driver Code if __name__ == "__main__": # Create 3 stacks using an # array of size 10. kstacks = KStacks(3, 10) # Push some items onto stack number 2. kstacks.push(15, 2) kstacks.push(45, 2) # Push some items onto stack number 1. kstacks.push(17, 1) kstacks.push(49, 1) kstacks.push(39, 1) # Push some items onto stack number 0. kstacks.push(11, 0) kstacks.push(9, 0) kstacks.push(7, 0) print("Popped element from stack 2 is " + str(kstacks.pop(2))) print("Popped element from stack 1 is " + str(kstacks.pop(1))) print("Popped element from stack 0 is " + str(kstacks.pop(0))) kstacks.printstack(0) # This code is contributed by Varun Patil
C#
using System; // C# program to demonstrate implementation of k stacks in a single // array in time and space efficient way public class GFG { // A c# class to represent k stacks in a single array of size n public class KStack { public int[] arr; // Array of size n to store actual content to be stored in stacks public int[] top; // Array of size k to store indexes of top elements of stacks public int[] next; // Array of size n to store next entry in all stacks // and free list public int n, k; public int free; // To store beginning index of free list //constructor to create k stacks in an array of size n public 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 public virtual bool Full { get { return (free == -1); } } // To push an item in stack number 'sn' where sn is from 0 to k-1 public virtual void push(int item, int sn) { // Overflow check if (Full) { Console.WriteLine("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 public virtual int pop(int sn) { // Underflow check if (isEmpty(sn)) { Console.WriteLine("Stack Underflow"); return int.MaxValue; } // 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 public virtual bool isEmpty(int sn) { return (top[sn] == -1); } } // Driver program public static void Main(string[] args) { // Let us create 3 stacks in an array of size 10 int k = 3, n = 10; KStack ks = new KStack(k, n); ks.push(15, 2); ks.push(45, 2); // Let us put some items in stack number 1 ks.push(17, 1); ks.push(49, 1); ks.push(39, 1); // Let us put some items in stack number 0 ks.push(11, 0); ks.push(9, 0); ks.push(7, 0); Console.WriteLine("Popped element from stack 2 is " + ks.pop(2)); Console.WriteLine("Popped element from stack 1 is " + ks.pop(1)); Console.WriteLine("Popped element from stack 0 is " + ks.pop(0)); } } // This code is contributed by Shrikant13
Javascript
<script> // javascript program to demonstrate implementation of k stacks in a single // array in time and space efficient way // A javascript class to represent k stacks in a single array of size n class KStack { // constructor to create k stacks in an array of size n constructor(k1 , n1) { // Initialize n and k, and allocate memory for all arrays this.k = k1; this.n = n1; this.arr = Array(n).fill(0); this.top = Array(k).fill(-1); this.next = Array(n).fill(0); // Initialize all spaces as free this.free = 0; for (var i = 0; i < n - 1; i++) this.next[i] = i + 1; this.next[n - 1] = -1; // -1 is used to indicate end of free list } // A utility function to check if there is space available isFull() { return (this.free == -1); } // To push an item in stack number 'sn' where sn is from 0 to k-1 push(item , sn) { // Overflow check if (this.isFull()) { document.write("Stack Overflow"); return; } var i = this.free; // Store index of first free slot // Update index of free slot to index of next slot in free list this.free = this.next[i]; // Update next of top and then top for stack number 'sn' this.next[i] = this.top[sn]; this.top[sn] = i; // Put the item in array this.arr[i] = item; } // To pop an from stack number 'sn' where sn is from 0 to k-1 pop(sn) { // Underflow check if (this.isEmpty(sn)) { document.write("Stack Underflow"); return Number.MAX_VALUE; } // Find index of top item in stack number 'sn' var i = this.top[sn]; this.top[sn] = this.next[i]; // Change top to store next of previous top // Attach the previous top to the beginning of free list this.next[i] = this.free; this.free = i; // Return the previous top item return this.arr[i]; } // To check whether stack number 'sn' is empty or not isEmpty(sn) { return (this.top[sn] == -1); } } // Driver program // Let us create 3 stacks in an array of size 10 var k = 3; n = 10; var ks = new KStack(k, n); ks.push(15, 2); ks.push(45, 2); // Let us put some items in stack number 1 ks.push(17, 1); ks.push(49, 1); ks.push(39, 1); // Let us put some items in stack number 0 ks.push(11, 0); ks.push(9, 0); ks.push(7, 0); document.write("Popped element from stack 2 is " + ks.pop(2)); document.write("<br/>Popped element from stack 1 is " + ks.pop(1)); document.write("<br/>Popped element from stack 0 is " + ks.pop(0)); // This code is contributed by gauravrajput1 </script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA