在不使用O(n)多余空间的情况下反转堆栈

本文概述

• 建议：在继续解决方案之前, 请先在{IDE}上尝试使用你的方法。
• C ++
• Java
• C#

反转一个stack而无需使用递归和额外的空间。甚至连功能栈都不允许。

例子：

Input : 1->2->3->4
Output : 4->3->2->1

Input :  6->5->4
Output : 4->5->6

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。

我们在下面的文章中讨论了一种反转字符串的方法。

使用递归反转堆栈

上述解决方案需要O(n)额外空间。如果我们内部将堆栈表示为链表, 则可以在O(1)时间内反转字符串。反转堆栈需要反转链表, 这可以用O(n)时间和O(1)额外空间来完成。

请注意, push()和pop()操作仍然需要O(1)时间。

C ++

// CPP 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();
     }
}

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

输出如下：

Original Stack 
4 3 2 1
Reversed Stack 
1 2 3 4

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。