在不使用O(n)多餘空間的情況下反轉堆棧


難度級別 容易獎學金
經常問 事實集 印孚瑟斯 空氣質量
鍊錶

問題陳述

問題“在不使用O(n)的額外空間的情況下反轉堆棧”問題表明您得到了一個 數據結構。 反轉給定的堆棧,而不使用額外的O(n)空間。

在不使用O(n)多餘空間的情況下反轉堆棧

5 4 3 2 1
1 2 3 4 5
80 60 10 20
20 10 60 80

在O(n)中不使用額外空間的情況下反轉堆棧的算法

  1. 創建一個包含整數變量和下一個指針的類節點。 創建一個接受構造函數的類構造函數 整數 作為參數。 將參數值分配給整數變量,然後在構造函數中將next指針設置為null。
  2. 之後,創建類 並在其中初始化類型節點的指針頂部。
  3. 創建一個函數push(),該函數接受一個整數作為參數。 檢查top是否等於null創建一個具有給定整數作為數據的新節點,並將新節點存儲在top中並返回。
  4. 否則創建一個新節點 s 以給定的整數作為數據。 將s的next更新為top,並且top等於s。
  5. 同樣,創建一個函數pop()。 創建一個新節點並將其存儲在頂部。 將top更新為top的next,然後返回新的node。
  6. 之後,創建函數reverse()。 創建三個分別代表前一個,當前和後續節點的節點。 將當前節點和上一個節點更新為頂部節點。
  7. 將當前節點更新為當前節點的下一個節點,並將上一個節點的下一個更新為null。
  8. 噹噹前節點不為null時,將後繼節點更新為當前節點的下一個節點,將當前節點的下一個節點更新為previos節點,將前一個節點更新為當前節點,將當前節點更新為後續節點。
  9. 將頂部節點更新為上一個節點。
  10. 最後,創建一個函數display()以顯示反轉的堆棧。 創建一個新節點並將其存儲在頂部。 當s不等於null時,打印s的數據並將s更新為s的下一個。

推薦碼

C ++程序可在不使用O(n)多餘空間的情況下反轉堆棧

#include<bits/stdc++.h> 
using namespace std; 
  
class Node { 
    public: 
        int data; 
        Node *next; 
          
        Node(int data){ 
            this->data = data; 
            this->next = NULL; 
        } 
}; 
  
class Stack{ 
      
    Node *top; 
      
    public: 
      
        void push(int data){ 
            if (top == NULL) { 
                top = new Node(data); 
                return; 
            } 
            Node *s = new Node(data); 
            s->next = top; 
            top = s; 
        } 
          
        Node* pop(){ 
            Node *s = top; 
            top = top->next; 
            return s; 
        } 
      
        void display(){ 
            Node *s = top; 
            while (s != NULL) { 
                cout << s->data << " "; 
                s = s->next; 
            } 
            cout << endl; 
        } 
      
        void reverse(){ 
            Node *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; 
        } 
}; 
  
int main(){ 
    Stack *s = new Stack(); 
    
    s->push(1); 
    s->push(2); 
    s->push(3); 
    s->push(4);
    s->push(5);
    
    s->reverse(); 
  
    s->display(); 
      
    return 0; 
}
1 2 3 4 5

Java程序可在不使用O(n)多餘空間的情況下反轉堆棧

class Node{ 
    int data; 
    Node next; 
    
    public Node(int data){ 
        this.data = data; 
        this.next = null; 
    } 
} 
  
class Stack{ 
    Node top; 
  
    public void push(int data){ 
        if (this.top == null){ 
            top = new Node(data); 
            return; 
        } 
        
        Node s = new Node(data); 
        s.next = this.top; 
        this.top = s; 
    } 
    
    public Node pop(){ 
        Node s = this.top; 
        this.top = this.top.next; 
        return s; 
    } 
  
    public void display(){ 
        Node s = this.top; 
        
        while (s != null){ 
            System.out.print(s.data + " "); 
            s = s.next; 
        } 
        
    } 
  
    public void reverse(){
        
        Node 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; 
    } 
} 
  
class reverseStack{ 
    
    public static void main(String[] args){ 
        
        Stack s = new Stack(); 
        
        s.push(1); 
        s.push(2); 
        s.push(3); 
        s.push(4);
        s.push(5);
        
        s.reverse(); 
  
        s.display(); 
    } 
}
1 2 3 4 5

複雜度分析

時間複雜度

O(N) 其中n是數據結構堆棧中元素的數量。 由於我們使用了單個循環來運行堆棧的元素。 時間複雜度是線性的。

空間複雜度

O(1) 因為我們正在使用恆定的額外空間。 由於用於存儲輸入的空間將不計入該算法。 因此,空間複雜度是恆定的。 但是整個程序需要線性空間複雜度。