algorithm - tortuga - ¿Cómo implementar 3 pilas con una matriz?
tortuga en opengl (14)
A veces, me encuentro con la siguiente pregunta de la entrevista: ¿cómo implementar 3 pilas con una matriz? Por supuesto, cualquier asignación estática no es una solución.
Almacene la pila en el área de tal manera cuando la primera pila entra en el índice 0, luego 0 + 3 = 3, luego 3 + 3 = 6 ...; el segundo entra en los índices 1, 1 + 3 = 4, 4 + 3 = 7 ...; el tercero entra en los índices 2, 2 + 3 = 5, 5 + 3 = 8 Así que si marcamos los primeros elementos de la pila con a, como uno con b y allí con c obtenemos: a1 b1 c1 a2 b2 c2 a3 b3 c3 ...
Puede haber lagunas pero siempre conocemos los índices superiores que se almacenan en la matriz de 3 elementos topIndex.
Aquí está mi solución en C # -
/* Program: Implement 3 stacks using a single array
*
* Date: 12/26/2015
*/
using System;
namespace CrackingTheCodingInterview
{
internal class Item
{
public object data;
public int prev;
}
/// <summary>
/// Class implementing 3 stacks using single array
/// </summary>
public class Stacks
{
/// <summary>
/// Pushing an element ''data'' onto a stack ''i''
/// </summary>
public void Push(int i, object d)
{
i--;
if (available != null)
{
int ava = (int)available.DeleteHead();
elems[ava].data = d;
elems[ava].prev = top[i];
top[i] = ava;
}
else
{
Console.WriteLine("Array full. No more space to enter!");
return;
}
}
/// <summary>
/// Popping an element from stack ''i''
/// </summary>
public object Pop(int i)
{
i--;
if (top[i] != -1)
{
object popVal = elems[top[i]].data;
int prevTop = elems[top[i]].prev;
elems[top[i]].data = null;
elems[top[i]].prev = -1;
available.Insert(top[i]);
top[i] = prevTop;
return popVal;
}
else
{
Console.WriteLine("Stack: {0} empty!", i);
return null;
}
}
/// <summary>
/// Peeking top element of a stack
/// </summary>
public object Peek(int i)
{
i--;
if (top[i] != -1)
{
return elems[top[i]].data;
}
else
{
Console.WriteLine("Stack: {0} empty!", i);
return null;
}
}
/// <summary>
/// Constructor initializing array of Nodes of size ''n'' and the ability to store ''k'' stacks
/// </summary>
public Stacks(int n, int k)
{
elems = new Item[n];
top = new int[k];
for (int i = 0; i < k; i++)
{
top[i] = -1;
}
for (int i = 0; i < n; i++)
{
elems[i] = new Item();
elems[i].data = null;
elems[i].prev = -1;
}
available = new SinglyLinkedList();
for (int i = n - 1; i >= 0; i--)
{
available.Insert(i);
}
}
private Item[] elems;
private int[] top;
private SinglyLinkedList available;
}
internal class StacksArrayTest
{
static void Main()
{
Stacks s = new Stacks(10, 3);
s.Push(1, ''a'');
s.Push(1, ''b'');
s.Push(1, ''c'');
Console.WriteLine("After pushing in stack 1");
Console.WriteLine("Top 1: {0}", s.Peek(1));
s.Push(2, ''d'');
s.Push(2, ''e'');
s.Push(2, ''f'');
s.Push(2, ''g'');
Console.WriteLine("After pushing in stack 2");
Console.WriteLine("Top 1: {0}", s.Peek(1));
Console.WriteLine("Top 2: {0}", s.Peek(2));
s.Pop(1);
s.Pop(2);
Console.WriteLine("After popping from stack 1 and 2");
Console.WriteLine("Top 1: {0}", s.Peek(1));
Console.WriteLine("Top 2: {0}", s.Peek(2));
s.Push(3, ''h'');
s.Push(3, ''i'');
s.Push(3, ''j'');
s.Push(3, ''k'');
s.Push(3, ''l'');
Console.WriteLine("After pushing in stack 3");
Console.WriteLine("Top 3: {0}", s.Peek(3));
Console.ReadLine();
}
}
}
Salida:
After pushing in stack 1
Top 1: c
After pushing in stack 2
Top 1: c
Top 2: g
After popping from stack 1 and 2
Top 1: b
Top 2: f
After pushing in stack 3
Top 3: l
Me refiero a esta publicación para codificarla - http://codercareer.blogspot.com/2013/02/no-39-stacks-sharing-array.html
Creo que deberías dividir la matriz en 3 piezas, haciendo que la cabeza de la primera pila esté en 0, cabeza de la segunda pila en n / 3, cabeza de la 3ª pila en n-1.
así que implemente la operación de inserción en:
- primer y segundo stack hacen i ++ y para 3rd stack hacen i--;
- Si encuentra que la primera pila no tiene espacio para empujar, cambie la posición de la segunda pila k / 3 hacia adelante. Donde k es el número de posiciones que quedan por llenar en el conjunto.
- Si encuentra que la segunda pila no tiene espacio para empujar, cambie la 2da pila 2 * k / 3 posiciones hacia atrás. Donde k es el número de posiciones que quedan por llenar en el conjunto.
- Si encuentra que la tercera pila no tiene espacio para empujar, cambie la 2da pila 2 * k / 3 posiciones hacia atrás. Donde k es el número de posiciones que quedan por llenar en el conjunto.
Estamos desplazando k / 3 y 2 * k / 3 cuando no queda espacio, de modo que después del desplazamiento de la pila central, cada pila tenga el mismo espacio disponible para su uso.
Espacio (no tiempo) eficiente. Tú podrías:
1) Defina dos pilas que comienzan en los puntos finales de la matriz y crecen en direcciones opuestas.
2) Defina la tercera pila como comenzando en el medio y creciendo en la dirección que desee.
3) Redefina la operación de inserción, de modo que cuando la operación sobrescriba otra, cambie toda la pila del medio en la dirección opuesta antes de empujar.
Necesita almacenar la parte superior de la pila para las dos primeras pilas, y el comienzo y el final de la tercera pila en alguna estructura.
Editar
Arriba puedes ver un ejemplo. El cambio se realiza con una política de partición de espacio igual, aunque se pueden elegir otras estrategias dependiendo de la heurística de su problema.
Editar
Siguiendo la sugerencia de @ ruslik, la pila media podría implementarse usando una secuencia alterna para empujes posteriores. La estructura resultante de la pila será algo así como:
| Elem 6 | Elem 4 | Elem 2 | Elem 0 | Elem 1 | Elem 3 | Elem 5 |
En este caso, deberá almacenar el número n de elementos en la pila del medio y usar la función:
f[n_] := 1/4 ( (-1)^n (-1 + 2 n) + 1) + BS3
para saber el siguiente elemento de matriz para usar para esta pila.
Aunque probablemente esto llevará a menos cambios, la implementación no es homogénea para las tres pilas, y la falta de homogeneidad (ya sabe) conduce a casos especiales, más errores y dificultades para mantener el código.
Hay muchas soluciones a este problema ya mencionadas en esta página. Las preguntas fundamentales, en mi humilde opinión son:
¿Cuánto dura cada operación push / pop?
¿Cuánto espacio se usa? Específicamente, ¿cuál es la cantidad más pequeña de elementos que se pueden enviar a las tres pilas para que la estructura de datos se quede sin espacio?
Por lo que puedo decir, cada solución ya publicada en esta página puede tomar hasta un tiempo lineal para un push / pop o puede quedarse sin espacio con un número lineal de espacios aún vacíos.
En esta publicación, haré referencia a soluciones que funcionan mucho mejor, y presentaré la más simple.
Para describir el espacio de solución con más cuidado, me referiré a dos funciones de una estructura de datos de la siguiente manera:
Una estructura que toma O (f (n)) tiempo amortizado para realizar un push / pop y no se queda sin espacio a menos que las tres pilas tengan al menos n - O (g (n)) elementos se denominará ( f, g) estructura. Más pequeños f y g son mejores. Cada estructura ya publicada en esta página tiene n para el tiempo o el espacio. Demostraré una estructura (1, √n).
Esto está basado en:
Michael L. Fredman y Deborah L. Goldsmith, "Three Stacks", en Journal of Algorithms, Volumen 17, Número 1, julio de 1994, páginas 45-70
- Una versión anterior apareció en el 29 ° Simposio Anual sobre Fundamentos de la Informática (FOCS) en 1988
Deborah Louise Goldsmith tesis de doctorado de la Universidad de California, San Diego, Departamento de Ingeniería Eléctrica / Ciencias de la Computación en 1987, "Gestión de memoria eficiente para> = 3 pilas"
Muestran, aunque yo no presentaré, una estructura (log n / log S, S) para cualquier S. Esto es equivalente a una estructura (t, n 1 / t ) para cualquier t. Mostraré una versión simplificada que es una estructura (1, √n).
Divida la matriz en bloques de tamaño Θ (√n). Los bloques están numerados de 1 a Θ (√n), y el número de un bloque se llama su "dirección". Una dirección se puede almacenar en una ranura de matriz en lugar de un elemento real. Se puede hacer referencia a un elemento dentro de un bloque determinado con un número menor que O (√n), y dicho número se denomina índice. Un índice también cabe en una ranura de matriz.
El primer bloque se reservará para almacenar direcciones e índices, y ningún otro bloque almacenará direcciones o índices. El primer bloque se llama directorio . Cada bloque que no sea de directorio estará vacío o contendrá elementos de solo una de las tres pilas; es decir, ningún bloque tendrá dos elementos de diferentes pilas. Además, cada pila tendrá como máximo un bloque que está parcialmente lleno; todos los demás bloques asociados con una pila estarán completamente llenos o completamente vacíos.
Siempre que haya un bloque vacío, se permitirá una operación de inserción en cualquier pila. Las operaciones pop siempre están permitidas. Cuando falla una operación de inserción, la estructura de datos está llena. En ese punto, el número de ranuras que no contienen elementos de una de las pilas es como máximo O (√n): dos bloques parcialmente llenos de las pilas que no se empujan y un bloque de directorios.
Cada bloque se ordena de modo que los elementos más cercanos al frente del bloque (índices más bajos) estén más cerca de la parte inferior de la pila.
El directorio contiene:
Tres direcciones para los bloques en la parte superior de las tres pilas, o 0 si todavía no hay bloques en una pila particular
Tres índices para el elemento en la parte superior de las tres pilas, o 0 si aún no hay elementos en una pila particular.
Para cada bloque completo o parcialmente lleno, la dirección del bloque más bajo que en la misma pila, o 0 si es el bloque más bajo en la pila.
La dirección de un bloque libre, llamado bloque líder, o 0 si no hay bloques libres
Para cada bloque libre, la dirección de otro bloque libre, o 0 si no hay más bloques libres
Estos dos últimos constituyen una pila, almacenada como una lista de enlaces libres, de bloques libres. Es decir, seguir las direcciones de los bloques libres que comienzan con el bloque líder dará una ruta a través de todos los bloques libres, que terminan en un 0.
Para insertar un elemento en una pila, encuentre su bloque superior y elemento superior dentro de ese bloque utilizando el directorio. Si hay espacio en ese bloque, coloque el artículo allí y regrese.
De lo contrario, extraiga la pila de bloques libres cambiando la dirección del bloque líder a la dirección del siguiente bloque libre en la pila de bloques libres. Cambie la dirección y el índice para que la pila sea la dirección del bloque libre que acaba de aparecer y 1, respectivamente. Agregue el artículo al bloque que acaba de aparecer en el índice 1 y vuelva.
Todas las operaciones toman O (1) vez. Pop es simétrico.
Mantenga un solo escenario para las tres pilas. Cada elemento insertado en la pila tiene un puntero hacia atrás a su elemento anterior. La parte inferior de cada pila tiene un puntero a NULL / None.
La arena mantiene un puntero al siguiente elemento en el espacio libre. Un impulso agrega este elemento a la pila respectiva y lo marca como no más en el espacio libre. Un pop elimina el elemento de la pila respectiva y lo agrega a la lista libre.
A partir de este boceto, los elementos en pilas necesitan un puntero reverso y espacio para los datos. Los elementos en el espacio libre necesitan dos punteros, por lo que el espacio libre se implementa como una lista doblemente vinculada.
El objeto que contiene las tres pilas necesita un puntero a la parte superior de cada pila más un puntero al encabezado de la lista libre.
Esta estructura de datos utiliza todo el espacio y empuja y aparece en tiempo constante. Hay una sobrecarga de un único puntero para todos los elementos de datos en una pila y los elementos de la lista libre usan el máximo de (dos punteros, un puntero + un elemento).
Más tarde: el código python es algo como esto. Tenga en cuenta el uso de índices enteros como punteros.
class StackContainer(object):
def __init__(self, stack_count=3, size=256):
self.stack_count = stack_count
self.stack_top = [None] * stack_count
self.size = size
# Create arena of doubly linked list
self.arena = [{''prev'': x-1, ''next'': x+1} for x in range(self.size)]
self.arena[0][''prev''] = None
self.arena[self.size-1][''next''] = None
self.arena_head = 0
def _allocate(self):
new_pos = self.arena_head
free = self.arena[new_pos]
next = free[''next'']
if next:
self.arena[next][''prev''] = None
self.arena_head = next
else:
self.arena_head = None
return new_pos
def _dump(self, stack_num):
assert 0 <= stack_num < self.stack_count
curr = self.stack_top[stack_num]
while curr is not None:
d = self.arena[curr]
print ''/t'', curr, d
curr = d[''prev'']
def _dump_all(self):
print ''-'' * 30
for i in range(self.stack_count):
print "Stack %d" % i
self._dump(i)
def _dump_arena(self):
print "Dump arena"
curr = self.arena_head
while curr is not None:
d = self.arena[curr]
print ''/t'', d
curr = d[''next'']
def push(self, stack_num, value):
assert 0 <= stack_num < self.stack_count
# Find space in arena for new value, update pointers
new_pos = self._allocate()
# Put value-to-push into a stack element
d = {''value'': value, ''prev'': self.stack_top[stack_num], ''pos'': new_pos}
self.arena[new_pos] = d
self.stack_top[stack_num] = new_pos
def pop(self, stack_num):
assert 0 <= stack_num < self.stack_count
top = self.stack_top[stack_num]
d = self.arena[top]
assert d[''pos''] == top
self.stack_top[stack_num] = d[''prev'']
arena_elem = {''prev'': None, ''next'': self.arena_head}
# Link the current head to the new head
head = self.arena[self.arena_head]
head[''prev''] = top
# Set the curr_pos to be the new head
self.arena[top] = arena_elem
self.arena_head = top
return d[''value'']
if __name__ == ''__main__'':
sc = StackContainer(3, 10)
sc._dump_arena()
sc.push(0, ''First'')
sc._dump_all()
sc.push(0, ''Second'')
sc.push(0, ''Third'')
sc._dump_all()
sc.push(1, ''Fourth'')
sc._dump_all()
print sc.pop(0)
sc._dump_all()
print sc.pop(1)
sc._dump_all()
Para simplificar el uso de la memoria, si no es muy eficiente, podría [*] dividir la matriz en nodos de lista, agregarlos a una lista de nodos libres y luego implementar sus pilas como listas vinculadas, tomando nodos de la lista gratuita según sea necesario. Sin embargo, no hay nada especial sobre el número 3 en este enfoque.
[*] en un lenguaje de bajo nivel donde la memoria se puede usar para almacenar punteros, o si los elementos de la pila son de un tipo como int que puede representar un índice en la matriz.
Pitón
class Stack:
def __init__(self):
self.pos_1 = 0
self.pos_2 = 1
self.pos_3 = 2
self.stack = [None, None, None]
def pop_1(self):
if self.pos_2 - 1 > 0:
to_ret = self.stack.pop(self.pos_1)
self.pos_2 -= 1
self.pos_3 -= 1
return to_ret
def push_1(self, value):
self.stack.insert(self.pos_1, value)
self.pos_2 += 1
self.pos_3 += 1
return None
def pop_2(self):
if self.pos_2 - 1 < self.pos_3:
to_ret = self.stack.pop(self.pos_2)
self.pos_3 -= 1
return to_ret
def push_2(self, value):
self.stack.insert(self.pos_2, value)
self.pos_3 += 1
return None
def pop_3(self):
if self.pos_3 - 1 > self.pos_2:
to_ret = self.stack.pop(self.pos_3)
return to_ret
def push_3(self, value):
self.stack.insert(self.pos_3, value)
return None
if __name__ == "__main__":
stack = Stack()
stack.push_2(22)
stack.push_1(1)
stack.push_1(2)
print stack.pop_1()
print stack.pop_1()
print stack.pop_2()
impresiones: 2 1 22
Siempre que intente organizar todos los elementos de una pila en un "extremo" de la matriz, le falta espacio para la tercera pila.
Sin embargo, podrías "intercalar" los elementos de la pila. Los elementos de la primera pila están en los índices i * 3 , los elementos de la segunda pila están en los índices i * 3 + 1 , los elementos de la tercera pila están en los índices i * 3 + 2 (donde i es un número entero).
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
| A1 : B1 : C1 | A2 : B2 : C2 | : B3 | C3 | : B4 : | :
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
^ ^ ^
A´s top C´s top B´s top
Por supuesto, este esquema va a desperdiciar espacio, especialmente cuando las pilas tienen tamaños desiguales. Podría crear esquemas arbitrariamente complejos similares al descrito anteriormente, pero sin conocer más restricciones para la pregunta formulada, me detendré aquí.
Actualizar:
Debido a los comentarios a continuación, que tienen un muy buen punto, se debe agregar que la intercalación no es necesaria, e incluso puede degradar el rendimiento en comparación con un diseño de memoria mucho más simple, como el siguiente:
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
| A1 : A2 : : : | B1 : B2 : B3 : B4 : | C1 : C2 : C3 :
+----+----+----+----+----+----+----+----+----+----+----+----+----+..
^ ^ ^
A´s top B´s top C´s top
es decir, dando a cada pila su propio bloque de memoria contiguo. Si la verdadera pregunta es, de hecho, cómo hacer el mejor uso posible de una cantidad fija de memoria, para no limitar cada pila más de lo necesario, entonces mi respuesta no será muy útil.
En ese caso, yo iría con la respuesta de @belisarius : una pila va al extremo "inferior" del área de memoria, creciendo "hacia arriba"; otra pila va al extremo "superior" del área de memoria, creciendo "hacia abajo", y una pila está en el medio que crece en cualquier dirección pero puede moverse cuando se acerca demasiado a una de las otras pilas.
Tengo una solución para esta pregunta. El siguiente programa hace el mejor uso de la matriz (en mi caso, una matriz de Objetos StackNode). Avíseme si tienen alguna pregunta sobre esto. [Ya es bastante tarde, así que no me molesté en documentar el código, lo sé, debería :))
public class StackNode {
int value;
int prev;
StackNode(int value, int prev) {
this.value = value;
this.prev = prev;
}
}
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--;
}
public static void main(String args[]) {
// Test Driver
StackMFromArray mulStack = new StackMFromArray();
try {
mulStack.push(1, 11);
mulStack.push(1, 12);
mulStack.push(2, 21);
mulStack.push(3, 31);
mulStack.push(3, 32);
mulStack.push(2, 22);
mulStack.push(1, 13);
StackNode node = mulStack.pop(1);
node = mulStack.pop(1);
System.out.println(node.value);
mulStack.push(1, 13);
} catch (Exception e) {
e.printStackTrace();
}
}
}
Una variante de una respuesta anterior: la pila # 1 crece desde la izquierda, y la pila # 2 crece desde la derecha.
La pila n. ° 3 está en el centro, pero los elementos crecen en orden alterno a la izquierda y a la derecha. Si N es el índice central, la pila crece como: N, N-1, N + 1, N-2, N + 2, etc. Una función simple convierte el índice de la pila en un índice de matriz.
paquete job.interview; importar java.util.Arrays;
public class NStack1ArrayGen<T> {
T storage[];
int numOfStacks;
Integer top[];
public NStack1ArrayGen(int numOfStks, T myStorage[]){
storage = myStorage;
numOfStacks = numOfStks;
top = new Integer[numOfStks];
for(int i=0;i<numOfStks;i++){top[i]=-1;}
}
public void push(int stk_indx, T value){
int r_indx = stk_indx -1;
if(top[r_indx]+numOfStacks < storage.length){
top[r_indx] = top[r_indx] < 0 ? stk_indx-1 : top[r_indx]+numOfStacks;
storage[top[r_indx]] = value;
}
}
public T pop(int stk_indx){
T ret = top[stk_indx-1]<0 ? null : storage[top[stk_indx-1]];
top[stk_indx-1] -= numOfStacks;
return ret;
}
public void printInfo(){
print("The array", Arrays.toString(storage));
print("The top indices", Arrays.toString(top));
for(int j=1;j<=numOfStacks;j++){
printStack(j);
}
}
public void print(String name, String value){
System.out.println(name + " ==> " + value);
}
public void printStack(int indx){
String str = "";
while(top[indx-1]>=0){
str+=(str.length()>0 ? "," : "") + pop(indx);
}
print("Stack#"+indx,str);
}
public static void main (String args[])throws Exception{
int count=4, tsize=40;
int size[]={105,108,310,105};
NStack1ArrayGen<String> mystack = new NStack1ArrayGen<String>(count,new String[tsize]);
for(int i=1;i<=count;i++){
for(int j=1;j<=size[i-1];j++){
mystack.push(i, "stk"+i+"_value"+j);
}
}
}
}
Esto imprime:
La matriz ==> [stk1_value1, stk2_value1, stk3_value1, stk4_value1, stk1_value2, stk2_value2, stk3_value2, stk4_value2, stk1_value3, stk2_value3, stk3_value3, stk4_value3, stk1_value4, stk2_value4, stk3_value4, stk4_value4, stk1_value5, stk2_value5, stk3_value5, stk4_value5, stk1_value6, stk2_value6, stk3_value6, stk4_value6, stk1_value7, stk2_value7, stk3_value7, stk4_value7, stk1_value8, stk2_value8, stk3_value8, stk4_value8, stk1_value9, stk2_value9, stk3_value9, stk4_value9, stk1_value10, stk2_value10, stk3_value10, stk4_value10] Los índices superiores ==> [36, 37, 38, 39 ] Pila # 1 ==> stk1_value10, stk1_value9, stk1_value8, stk1_value7, stk1_value6, stk1_value5, stk1_value4, stk1_value3, stk1_value2, stk1_value1 Pila # 2 ==> stk2_value10, stk2_value9, stk2_value8, stk2_value7, stk2_value6, stk2_value5, stk2_value4, stk2_value3, stk2_value2, stk2_value1 Stack # 3 ==> stk3_value10, stk3_value9, stk3_value8, stk3_value7, stk3_value6, stk3_value5, stk3_value4, stk3_value3, stk3_value2, stk3_value1 Stack # 4 ==> stk4_value10, stk4_value9, stk4_value8, stk4_value7, stk4_value6, stk4_value5, stk4_value4, stk4_value3, stk4_value2, stk4_value1
Solución: la implementación de dos pilas es fácil. La primera pila crece de principio a fin, mientras que la segunda crece de principio a fin. El desbordamiento de cualquiera de ellos no ocurrirá a menos que realmente no quede espacio en la matriz.
Para tres pilas, se requiere lo siguiente: Una matriz auxiliar para mantener la matriz para cada nodo. Variables para almacenar la parte superior actual de cada pila. Con estos dos en su lugar, los datos de todas las pilas se pueden intercalar en la matriz original y todavía se pueden hacer operaciones de empuje / pop / tamaño para todas las pilas.
Al insertar cualquier elemento, insértelo al final de todos los elementos en la matriz normal. Almacene la parte superior actual de esa pila como principal para el nuevo elemento (en la matriz de los padres) y actualice current-top a la nueva posición.
Al eliminar, inserte NULL en la matriz de pilas para el elemento eliminado y restablezca la pila superior de esa pila al elemento primario.
Cuando la matriz está llena, tendrá algunos agujeros correspondientes a los elementos eliminados. En este punto, la matriz se puede compactar para juntar todo el espacio libre o se puede realizar una búsqueda lineal de espacio libre al insertar elementos nuevos.
para más detalles, consulte este enlace: - https://coderworld109.blogspot.in/2017/12/how-to-implement-3-stacks-with-one-array.html
enum stackId{LEFT, MID, RIGHT };
clase threeStacks {
int* arr;
int leftSize;
int rightSize;
int midSize;
int mid;
int maxSize;
public:
threeStacks(int n):leftSize(0), rightSize(0), midSize(0), mid(n/2), maxSize(n)
{
arr = new int[n];
}
void push(stackId sid, int val){
switch(sid){
case LEFT:
pushLeft(val);
break;
case MID:
pushMid(val);
break;
case RIGHT:
pushRight(val);
}
}
int pop(stackId sid){
switch(sid){
case LEFT:
return popLeft();
case MID:
return popMid();
case RIGHT:
return popRight();
}
}
int top(stackId sid){
switch(sid){
case LEFT:
return topLeft();
case MID:
return topMid();
case RIGHT:
return topRight();
}
}
void pushMid(int val){
if(midSize+leftSize+rightSize+1 > maxSize){
cout << "Overflow!!"<<endl;
return;
}
if(midSize % 2 == 0){
if(mid - ((midSize+1)/2) == leftSize-1){
//left side OverFlow
if(!shiftMid(RIGHT)){
cout << "Overflow!!"<<endl;
return;
}
}
midSize++;
arr[mid - (midSize/2)] = val;
}
else{
if(mid + ((midSize+1)/2) == (maxSize - rightSize)){
//right side OverFlow
if(!shiftMid(LEFT)){
cout << "Overflow!!"<<endl;
return;
}
}
midSize++;
arr[mid + (midSize/2)] = val;
}
}
int popMid(){
if(midSize == 0){
cout << "Mid Stack Underflow!!"<<endl;
return -1;
}
int val;
if(midSize % 2 == 0)
val = arr[mid - (midSize/2)];
else
val = arr[mid + (midSize/2)];
midSize--;
return val;
}
int topMid(){
if(midSize == 0){
cout << "Mid Stack Underflow!!"<<endl;
return -1;
}
int val;
if(midSize % 2 == 0)
val = arr[mid - (midSize/2)];
else
val = arr[mid + (midSize/2)];
return val;
}
bool shiftMid(stackId dir){
int freeSpace;
switch (dir){
case LEFT:
freeSpace = (mid - midSize/2) - leftSize;
if(freeSpace < 1)
return false;
if(freeSpace > 1)
freeSpace /= 2;
for(int i=0; i< midSize; i++){
arr[(mid - midSize/2) - freeSpace + i] = arr[(mid - midSize/2) + i];
}
mid = mid-freeSpace;
break;
case RIGHT:
freeSpace = maxSize - rightSize - (mid + midSize/2) - 1;
if(freeSpace < 1)
return false;
if(freeSpace > 1)
freeSpace /= 2;
for(int i=0; i< midSize; i++){
arr[(mid + midSize/2) + freeSpace - i] = arr[(mid + midSize/2) - i];
}
mid = mid+freeSpace;
break;
default:
return false;
}
}
void pushLeft(int val){
if(midSize+leftSize+rightSize+1 > maxSize){
cout << "Overflow!!"<<endl;
return;
}
if(leftSize == (mid - midSize/2)){
//left side OverFlow
if(!shiftMid(RIGHT)){
cout << "Overflow!!"<<endl;
return;
}
}
arr[leftSize] = val;
leftSize++;
}
int popLeft(){
if(leftSize == 0){
cout << "Left Stack Underflow!!"<<endl;
return -1;
}
leftSize--;
return arr[leftSize];
}
int topLeft(){
if(leftSize == 0){
cout << "Left Stack Underflow!!"<<endl;
return -1;
}
return arr[leftSize - 1];
}
void pushRight(int val){
if(midSize+leftSize+rightSize+1 > maxSize){
cout << "Overflow!!"<<endl;
return;
}
if(maxSize - rightSize - 1 == (mid + midSize/2)){
//right side OverFlow
if(!shiftMid(LEFT)){
cout << "Overflow!!"<<endl;
return;
}
}
rightSize++;
arr[maxSize - rightSize] = val;
}
int popRight(){
if(rightSize == 0){
cout << "Right Stack Underflow!!"<<endl;
return -1;
}
int val = arr[maxSize - rightSize];
rightSize--;
return val;
}
int topRight(){
if(rightSize == 0){
cout << "Right Stack Underflow!!"<<endl;
return -1;
}
return arr[maxSize - rightSize];
}
};