Invierta una pila sin usar recursividad y espacio adicional. Incluso la pila funcional no está permitida.
Ejemplos:
Input : 1->2->3->4 Output : 4->3->2->1 Input : 6->5->4 Output : 4->5->6
Hemos discutido una forma de revertir una pila en la publicación a continuación.
Invertir una pila usando recursividad
La solución anterior requiere O(n) espacio extra. Podemos invertir una pila en tiempo O(1) si representamos internamente la pila como una lista enlazada. Invertir una pila requeriría invertir una lista enlazada que se puede hacer con O(n) tiempo y O(1) espacio adicional.
Tenga en cuenta que las operaciones push() y pop() aún toman tiempo O(1).
Implementación:
C++
// C++ program to implement Stack
// using linked list so that reverse
// can be done with O(1) extra space.
#include<bits/stdc++.h>
using namespace std;
class StackNode {
public:
int data;
StackNode *next;
StackNode(int data)
{
this->data = data;
this->next = NULL;
}
};
class Stack {
StackNode *top;
public:
// Push and pop operations
void push(int data)
{
if (top == NULL) {
top = new StackNode(data);
return;
}
StackNode *s = new StackNode(data);
s->next = top;
top = s;
}
StackNode* pop()
{
StackNode *s = top;
top = top->next;
return s;
}
// prints contents of stack
void display()
{
StackNode *s = top;
while (s != NULL) {
cout << s->data << " ";
s = s->next;
}
cout << endl;
}
// Reverses the stack using simple
// linked list reversal logic.
void reverse()
{
StackNode *prev, *cur, *succ;
cur = prev = top;
cur = cur->next;
prev->next = NULL;
while (cur != NULL) {
succ = cur->next;
cur->next = prev;
prev = cur;
cur = succ;
}
top = prev;
}
};
// driver code
int main()
{
Stack *s = new Stack();
s->push(1);
s->push(2);
s->push(3);
s->push(4);
cout << "Original Stack" << endl;;
s->display();
cout << endl;
// reverse
s->reverse();
cout << "Reversed Stack" << endl;
s->display();
return 0;
}
// This code is contribute by Chhavi.
Java
// Java program to implement Stack using linked
// list so that reverse can be done with O(1)
// extra space.
class StackNode {
int data;
StackNode next;
public StackNode(int data)
{
this.data = data;
this.next = null;
}
}
class Stack {
StackNode top;
// Push and pop operations
public void push(int data)
{
if (this.top == null) {
top = new StackNode(data);
return;
}
StackNode s = new StackNode(data);
s.next = this.top;
this.top = s;
}
public StackNode pop()
{
StackNode s = this.top;
this.top = this.top.next;
return s;
}
// prints contents of stack
public void display()
{
StackNode s = this.top;
while (s != null) {
System.out.print(s.data + " ");
s = s.next;
}
System.out.println();
}
// Reverses the stack using simple
// linked list reversal logic.
public void reverse()
{
StackNode prev, cur, succ;
cur = prev = this.top;
cur = cur.next;
prev.next = null;
while (cur != null) {
succ = cur.next;
cur.next = prev;
prev = cur;
cur = succ;
}
this.top = prev;
}
}
public class reverseStackWithoutSpace {
public static void main(String[] args)
{
Stack s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
System.out.println("Original Stack");
s.display();
// reverse
s.reverse();
System.out.println("Reversed Stack");
s.display();
}
}
Python3
# Python3 program to implement Stack
# using linked list so that reverse
# can be done with O(1) extra space.
class StackNode:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.top = None
# Push and pop operations
def push(self, data):
if (self.top == None):
self.top = StackNode(data)
return
s = StackNode(data)
s.next = self.top
self.top = s
def pop(self):
s = self.top
self.top = self.top.next
return s
# Prints contents of stack
def display(self):
s = self.top
while (s != None):
print(s.data, end = ' ')
s = s.next
# Reverses the stack using simple
# linked list reversal logic.
def reverse(self):
prev = self.top
cur = self.top
cur = cur.next
succ = None
prev.next = None
while (cur != None):
succ = cur.next
cur.next = prev
prev = cur
cur = succ
self.top = prev
# Driver code
if __name__=='__main__':
s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.push(4)
print("Original Stack")
s.display()
print()
# Reverse
s.reverse()
print("Reversed Stack")
s.display()
# This code is contributed by rutvik_56
C#
// C# program to implement Stack using linked
// list so that reverse can be done with O(1)
// extra space.
using System;
public class StackNode
{
public int data;
public StackNode next;
public StackNode(int data)
{
this.data = data;
this.next = null;
}
}
public class Stack
{
public StackNode top;
// Push and pop operations
public void push(int data)
{
if (this.top == null)
{
top = new StackNode(data);
return;
}
StackNode s = new StackNode(data);
s.next = this.top;
this.top = s;
}
public StackNode pop()
{
StackNode s = this.top;
this.top = this.top.next;
return s;
}
// prints contents of stack
public void display()
{
StackNode s = this.top;
while (s != null)
{
Console.Write(s.data + " ");
s = s.next;
}
Console.WriteLine();
}
// Reverses the stack using simple
// linked list reversal logic.
public void reverse()
{
StackNode prev, cur, succ;
cur = prev = this.top;
cur = cur.next;
prev.next = null;
while (cur != null)
{
succ = cur.next;
cur.next = prev;
prev = cur;
cur = succ;
}
this.top = prev;
}
}
public class reverseStackWithoutSpace
{
// Driver code
public static void Main(String []args)
{
Stack s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
Console.WriteLine("Original Stack");
s.display();
// reverse
s.reverse();
Console.WriteLine("Reversed Stack");
s.display();
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// JavaScript program to implement Stack
// using linked list so that reverse can
// be done with O(1) extra space.
class StackNode
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class Stack
{
top = null;
// Push and pop operations
push(data)
{
if (this.top == null)
{
this.top = new StackNode(data);
return;
}
var s = new StackNode(data);
s.next = this.top;
this.top = s;
}
pop()
{
var s = this.top;
this.top = this.top.next;
return s;
}
// Prints contents of stack
display()
{
var s = this.top;
while (s != null)
{
document.write(s.data + " ");
s = s.next;
}
document.write("<br>");
}
// Reverses the stack using simple
// linked list reversal logic.
reverse()
{
var prev, cur, succ;
cur = prev = this.top;
cur = cur.next;
prev.next = null;
while (cur != null)
{
succ = cur.next;
cur.next = prev;
prev = cur;
cur = succ;
}
this.top = prev;
}
}
// Driver code
var s = new Stack();
s.push(1);
s.push(2);
s.push(3);
s.push(4);
document.write("Original Stack <br>");
s.display();
// Reverse
s.reverse();
document.write("Reversed Stack <br>");
s.display();
// This code is contributed by rdtank
</script>
Producción
Original Stack 4 3 2 1 Reversed Stack 1 2 3 4
Complejidad de tiempo: O(n) , ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Este artículo es una contribución de Niharika Sahai . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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