En este artículo, veremos cómo crear una estructura de datos que pueda manejar múltiples pilas con un tamaño creciente. La estructura de datos necesita manejar tres operaciones:
- push(x, stackNum) = empuja el valor x a la pila numerada stackNum
- pop(stackNum) = extrae el elemento superior de la pila numerada stackNum
- top(stackNum) = muestra el elemento superior de la pila stackNum.
Supongamos que la pila múltiple dada es [{1, 2}, {4, 6}, {9, 10}]
Entrada: empujar (3, 0), arriba (0)
empujar (7, 1), arriba (1)
pop (2), arriba (2)Salida: 3, 7, 9
Explicación: cuando se empuja 3 en la pila 0, la pila se convierte en {1, 2, 3}. Entonces, el elemento superior es 3.
Cuando se empuja 7 en la pila 1, la pila se convierte en {4, 6, 7}. Entonces, el elemento superior es 7.
Cuando el elemento superior se extrae de la pila 2, la pila se convierte en {9}. Entonces el elemento superior es 9
Enfoque: Siga el enfoque mencionado a continuación para implementar la idea.
- Almacene el tamaño y el índice superior de cada pila en arreglos sizes[] y topIndex[] .
- Los tamaños se almacenarán en una array de suma de prefijos (usar una suma de array de prefijos nos ayudará a encontrar el inicio/tamaño de una pila en tiempo O(1))
- Si el tamaño de una pila alcanza la capacidad máxima reservada, amplíe el tamaño reservado (multiplíquelo por 2)
- Si el tamaño de una pila se reduce a una cuarta parte del tamaño reservado, reduzca el tamaño reservado (divídalo entre 2)
- Cada vez que necesitamos expandir/reducir una pila en la estructura de datos, los índices de otras pilas pueden cambiar, por lo que debemos ocuparnos de eso. Eso se soluciona incrementando/disminuyendo el valor de las arrays de tamaños [] y topIndex [] (podemos hacerlo en tiempo O (número de pilas)).
A continuación se muestra la implementación:
C++
#include <bits/stdc++.h>
using namespace std;
template <typename T>
// Class to implement multistack
class MultiStack {
int numberOfStacks;
vector<T> values;
vector<int> sizes, topIndex;
public:
// Constructor to create k stacks
// (by default 1)
MultiStack(int k = 1)
: numberOfStacks(k)
{
// reserve 2 elements for each stack first
values = vector<T>(numberOfStacks << 1);
// For each stack store the index
// of the element on the top
// and the size (starting point)
sizes = vector<int>(numberOfStacks);
topIndex = vector<int>(numberOfStacks);
// Sizes is a prefix sum vector
for (int size = 2, i = 0; i < numberOfStacks;
i++, size += 2)
sizes[i] = size, topIndex[i] = size - 2;
}
// Push a value in a stack
void push(int stackNum, T val)
{
// Check if the stack is full,
// if so Expand it
if (isFull(stackNum))
Expand(stackNum);
// Add the value to the top of the stack
// and increment the top index
values[topIndex[stackNum]++] = val;
}
// Pop the top value and
// return it form a stack
T pop(int stackNum)
{
// If the stack is empty
// throw an error
if (empty(stackNum))
throw("Empty Stack!");
// Save the top value
T val = values[topIndex[stackNum] - 1];
// Set top value to default data type
values[--topIndex[stackNum]] = T();
// Shrink the reserved size if needed
Shrink(stackNum);
// Return the pop-ed value
return val;
}
// Return the top value form a stack
// Same as pop (but without removal)
T top(int stackNum)
{
if (empty(stackNum))
throw("Empty Stack!");
return values[topIndex[stackNum] - 1];
}
// Return the size of a stack
// (the number of elements in the stack,
// not the reserved size)
int size(int stackNum)
{
if (!stackNum)
return topIndex[0];
return topIndex[stackNum] - sizes[stackNum - 1];
}
// Check if a stack is empty or not
// (has no elements)
bool empty(int stackNum)
{
int offset;
if (!stackNum)
offset = 0;
else
offset = sizes[stackNum - 1];
int index = topIndex[stackNum];
return index == offset;
}
// Helper function to check
// if a stack size has reached
// the reserved size of that stack
bool isFull(int stackNum)
{
int offset = sizes[stackNum];
int index = topIndex[stackNum];
return index >= offset;
}
// Function to expand the reserved size
// of a stack (multiply by 2)
void Expand(int stackNum)
{
// Get the reserved_size of the stack()
int reserved_size = size(stackNum);
// Update the prefix sums (sizes)
// and the top index of the next stacks
for (int i = stackNum + 1; i < numberOfStacks; i++)
sizes[i] += reserved_size,
topIndex[i] += reserved_size;
// Update the size of the recent stack
sizes[stackNum] += reserved_size;
// Double the size of the stack by
// inserting 'reserved_size' elements
values.insert(values.begin() + topIndex[stackNum],
reserved_size, T());
}
// Function to shrink the reserved size
// of a stack (divide by2)
void Shrink(int stackNum)
{
// Get the reserved size and the current size
int reserved_size, current_size;
if (!stackNum)
reserved_size = sizes[0],
current_size = topIndex[0];
else
reserved_size
= sizes[stackNum] - sizes[stackNum - 1],
current_size
= topIndex[stackNum] - sizes[stackNum - 1];
// Shrink only if the size is
// lower than a quarter of the
// reserved size and avoid shrinking
// if the reserved size is 2
if (current_size * 4 > reserved_size
|| reserved_size == 2)
return;
// Divide the size by 2 and update
// the prefix sums (sizes) and
// the top index of the next stacks
int dif = reserved_size / 2;
for (int i = stackNum + 1; i < numberOfStacks; i++)
sizes[i] -= dif, topIndex[i] -= dif;
sizes[stackNum] -= dif;
// Erase half of the reserved size
values.erase(values.begin() + topIndex[stackNum],
values.begin() + topIndex[stackNum]
+ dif);
}
};
// Driver code
int main()
{
// create 3 stacks
MultiStack<int> MStack(3);
// push elements in stack 0:
MStack.push(0, 21);
MStack.push(0, 13);
MStack.push(0, 14);
// Push one element in stack 1:
MStack.push(1, 15);
// Push two elements in stack 2:
MStack.push(2, 1);
MStack.push(2, 2);
MStack.push(2, 3);
// Print the top elements of the stacks
cout << MStack.top(0) << '\n';
cout << MStack.top(1) << '\n';
cout << MStack.top(2) << '\n';
return 0;
}
Producción
14 15 3
Complejidades del tiempo:
- O(1) para la función top() .
- O(1) amortizado para las funciones push() y pop() .
Espacio auxiliar: O(N) donde N es el número de pilas
Publicación traducida automáticamente
Artículo escrito por davidgatea21 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA