¿Cómo podemos revertir una pila usando solo las operaciones push () y pop () sin usar ningún DS secundario?

En primer lugar es posible.

  #include 
 #include 
 usando el espacio de nombres estándar;

 apilar  s;

 int BottomInsert (int x) {
     if (s.size () == 0) s.push (x);
     más{
         int a = s.top ();
         s.pop ();
         BottomInsert (x);
         s.push (a);
     }
 }
 int reverse () {
     if (s.size ()> 0) {
         int x = s.top ();
         s.pop ();
         marcha atrás();
         BottomInsert (x);
     }
 }
 int main ()
 {
     int n, a;
     cin >> n;
     para (int i = 0; i > a;
         s.push (a);
     }
     marcha atrás();
     devuelve 0;
 }

Si no comprende ninguna parte, no dude en preguntar en los comentarios.

Por supuesto que es posible. Sin embargo, podría no ser la mejor idea. Aquí está el código completo en C #

  Programa de clase
     {
         vacío estático Main (string [] args)
         {
             Pila  pila = nueva Pila  ();
             stack.Push ("a");
             stack.Push ("b");
             stack.Push ("c");
             stack.Push ("d");
             stack.Push ("e");
             stack.Push ("f");

             ReverseStack (pila);
         }

         vacío estático privado ReverseStack  (pila Stack )
         {
             for (int i = 0; i  (pila  pila, int intit, int currentLevel, T targetElement)
         {
             if (currentLevel == limit)
             {
                 stack.Push (targetElement);
             }
             más
             {
                 Elemento T = stack.Pop ();
                 ReverseStackStep (stack, limit, currentLevel + 1, targetElement);
                 stack.Push (elemento);
             }
         }
     }

No utiliza una pila DS adicional, pero sí utiliza la pila de llamadas. La complejidad del tiempo está lejos de ser ideal, [matemáticas] O (n ^ 2) [/ matemáticas].

La idea es hacer estallar el elemento superior de la pila, ponerlo en la parte inferior de la pila y restaurar el resto de la pila encima, luego repetir lo mismo con la parte de la pila sobre el elemento movida.

Si está utilizando la recursividad para resolver esto (como es la mayoría de los enfoques aquí) … entonces está utilizando una Estructura de datos secundaria en la pila del sistema, que empuja las llamadas recursivas, y esto mientras regresa de la recursividad nos da una opción para atravesar el apilar en orden inverso, donde solo estamos agregando esos elementos nuevamente. Así que hay una pila oculta que está resolviendo tu propósito …

Esto se puede hacer de forma recursiva. Primero haga estallar el primer elemento de la pila e invierta recursivamente la pila. Una vez que se invierte la pila restante, tendremos 2 elementos, uno el elemento que desplegamos (digamos temp) y otro la pila restante que se invierte. Ahora, invierta su orden. Para invertir el orden, escriba otra función recursiva en la que seguiremos desplegando los elementos y cuando la pila se vacíe, presione ‘temp’ en la parte inferior y luego todos los elementos que se desplegaron recursivamente. El pseudocódigo se puede escribir como:

  Reverso (pila s)
 {
         si (s no está vacío)
         {
                 pop primer elemento de la pila (por ejemplo, temp);
                 Recurrentemente invierte la pila restante.  (Reverso (s))
                 // una vez que se invierte la pila restante, cambie el orden. 
                 ReverseOrder (temp, s);
         }
 }

 ReverseOrder (temp, s)
 { 
         si (s está vacío)
         {
                  empujar la temperatura a la pila;
         }
         si (s no está vacío)
         {
                  elemento pop de la pila (digamos x);
                  ReverseOrder (temp, s);
                  empujar x a la pila;
         }
 } 

Esta segunda función seguirá sacando elementos de la pila y la almacenará en la propia pila del compilador. Cuando la pila ‘s’ se vacía, ‘temp’ se empujará a ‘s’ y luego todos los elementos que se almacenan actualmente en la propia pila del compilador se empujan en el mismo orden en que estaban inicialmente presentes.

Esta respuesta es una trampa y específica de Java, la complejidad es O (1).

En Java, las pilas se implementan utilizando una Deque o una cola de doble extremo. Esto permite la operación tanto en la cabeza como en la cola de una cola. Para una deque hay métodos addFirst(e) y removeFirst(e) que son equivalentes a push(e) y pop() . También tiene métodos addLast(e) y removeLast(e) que actúan en el otro extremo de la estructura. Hay una clase de pila heredada, pero no debe usarla ya que se sincronizó, lo que la hace mucho más lenta.

Para voltear un Deque solo necesita una clase de contenedor que cambie el significado de estos dos operadores

  La clase FlippedDeque  implementa Deque  {
     Deque  raíz;
     Public FlippedDeque (cola Deque ) {
          raíz = cola;
     }

     public void addFirst (T e) {root.addLast (e);  }

     public T removeFirst () {return root.removeLast ();  }

     public void addLast (T e) {root.addFirst (e);  }

     public T removeLast () {return root.removeFirst ();  }

     // algunos otros métodos especiales con nombre deben redefinirse

     public void push (T e) {root.addLast (e);  }
     public T pop () {return root.removeLast ();  }
     oferta pública nula (T e) {root.addFirst (e);  }
     encuesta pública T () {return root.removeFirst ();  }
     ....
 }

Se necesita bastante trabajo para implementar todos los métodos requeridos.

Ya compartido por muchas personas aquí. Esto puede ser fácil de leer. Solución en Java. La complejidad del tiempo es O (N ^ 2).

  clase pública StackReversal  {
    
     public static void main (String [] args) {
         Stack  stack = new Stack <> ();
         stack.push (1);
         stack.push (2);
         stack.push (3);
         System.out.println (pila);
         reverseStack (pila);
         System.out.println (pila);
     }
    
     public static  void reverseStack (pila  pila) {
         if (stack.isEmpty ()) {
             regreso;
         }
         E e = stack.pop ();
         reverseStack (pila);
         addBottom (pila, e);
     }
     private static  void addBottom (Stack  stack, E e) {
         if (stack.isEmpty ()) {
             stack.push (e);
             regreso;
         }
         E temp = stack.pop ();
         addBottom (pila, e);
         stack.push (temp);
     }
 } 

Verifique los enlaces a continuación:

Utiliza la recursividad.

Invertir una pila usando recursividad – GeeksforGeeks

Invierte una pila usando

Pregunta de la entrevista de Amazon para ingenieros / desarrolladores de software

Bueno, me han hecho esta pregunta en una entrevista (invertir una pila sin usar memoria externa), se vería así.

  #include 
 #include 

 usando el espacio de nombres estándar;

 void insert_at_bottom (stack  & stk, int item) {
        if (stk.empty ()) {
                  stk.push (elemento);
        }
        más {
                  int temp = stk.top ();
                  stk.pop ();
                  insert_at_bottom (stk, item);
                  stk.push (temp);
        }
 }

 anular el reverso (stack  & stk) {
           if (! stk.empty ()) {
                  int temp = stk.top ();
                  stk.pop ();
                  reverso (stk);
                  insert_at_bottom (stk, temp);
          }
 }

 // Función del controlador
 int main () {
           stack  stk;
           para (int i = 0; i <4; i ++) stk.push (i + 1);
           reverso (stk);
           while (! stk.empty ()) {
                     cout << stk.top () << "";
                     stk.pop ();
           }
           cout << endl;
           devuelve 0;
 }

Aquí, mediante el uso de dos funciones y la ventaja de la recursividad, podemos resolver este problema. Pero no vi ningún sentido en este enfoque en lugar de usar una estructura de datos adicional porque cada llamada de función recursiva se almacenará en una pila interna que consume mucha memoria.

Bueno, prácticamente me parece imposible, pero aquí hay una solución alternativa.

Supongamos que tienes una pila como esta:
a B C D
Sigue sacando elementos y agregando valores al que está debajo de él hasta que te quede solo 1 elemento algo así como:
(Cada línea representa un elemento que se elimina)
a B C D
a B C D
a B C D
a B C D

Ahora comience a agregar elementos para obtener una pila inversa como
(Cada línea representa un elemento que se agrega)
a B C D
d abc
dc ab
dcba

Pero supongo que terminarías usando más tiempo y memoria que usando otra pila.

Esto es mucho más fácil de resolver usando una cola (segunda estructura de datos). Me referiré a esto como “q”. Todo lo que necesitaría hacer es llamar a q.insert (s.pop ()) y luego, después de hacer estallar todos los elementos en la cola, llamaría a s.push (q.remove ()) para insertar elementos de q a apilar s. Debe usar un ciclo while para ejecutar solo estos comandos mientras stack y queue no están vacíos.

¡Es posible , intercambiando el primer y el último elemento de la pila y continúa el proceso hasta llegar al punto medio de esa pila! El código está escrito en Python 3.

  pila de clase ():
     def __init __ (self):
     self.items = []
    
     def push (self, item):
     self.items.insert (0, artículo)

     def pop (self):
     self.items.pop (0)

     def show (auto):
     print (self.items)

     def reversa (auto):
     pos = 0
     neg = -1
     para i en rango (len (self.items) // 2):
         temp = self.items [pos]
         self.items [pos] = self.items [neg]
         self.items [neg] = temp
         pos = pos + 1
         neg = neg - 1
     print (self.items)

 s = pila ()
 s.push (0)
 s.push (1)
 s.push (2)
 s.push (3)
 s.push (4)
 s.push (5)
 s.push (6)

 s.show ()
 s.reverse ()

Puede revertir fácilmente una pila usando solo operaciones push y pop.

  public static void main (String [] args) {
	 Stack  stack = new Stack  ();
	 stack.push (1);
	 stack.push (2);
	 stack.push (3);
	
	 pila = reverseStack (pila);
 }

 Public Stack Stack  reverseStack (Stack stack) {
	 Stack  reverse = new Stack  ();
	 while (! stack.empty ()) {
		 reverse.push (stack.pop ());
	 }
	 volver al revés;
 }

Aquí estoy creando una nueva función que crea una nueva pila y saca los elementos de la pila anterior y los empuja a la nueva pila. Después de eso, la pila anterior se reemplaza por la nueva pila.

Hay dos funciones
Reverse e InsertAtBottom.
Tome un ejemplo y lo obtendrá.
toma O (n ^ 2) tiempo.

Retire el elemento de la parte superior de la pila y cada vez que recursivamente llame al reverso (), significa que todos los elementos están en el marco de la pila del sistema, cuando la pila está vacía, sáquela del marco de la pila del sistema y empújela hacia nuestra pila.

Podemos hacerlo usando la recursividad.