使用臨時堆棧對堆棧進行排序


難度級別
經常問 亞馬遜 高盛 IBM 庫利扎 雅虎
排序

問題陳述

問題“使用臨時堆棧對堆棧進行排序”表明您得到了一個 數據結構。 使用臨時堆棧對給定堆棧的元素進行排序。

使用臨時堆棧對堆棧進行排序

9 4 2 -1 6 20
20 9 6 4 2 -1
2 1 4 3 6 5
6 5 4 3 2 1

例如

令堆棧= [9 4 2 -1 6 20]和臨時堆棧= []

Steps for sorting -
1.Top of stack = 20
Stack = [9 4 2 -1 6]
Temporary stack = [20]

2. Top of stack = 6
Stack = [9 4 2 -1 20]
Temporary stack = [6]

3. Top of stack = 20
Stack = [9 4 2 -1]
Temporary stack = [6 20]

4. Top of stack = -1
Stack = [9 4 2 20 6]
Temporary stack = [-1]

5. Top of stack = 6
Stack = [9 4 2 20]
Temporary stack = [-1 6]

6. Top of stack = 20
Stack = [9 4 2]
Temporary stack = [-1 6 20]

7. Top of stack = 2
Stack = [9 4 20 6]
Temporary stack = [-1 2]

8. Top of stack = 6
Stack = [9 4 20]
Temporary stack = [-1 2 6]

9. Top of stack = 20
Stack = [9 4]
Temporary stack = [-1 2 6 20]

10. Top of stack = 4
Stack = [9 20 6]
Temporary stack = [-1 2 4]

11. Top of stack = 6
Stack = [9 20]
Temporary stack = [-1 2 4 6]

12. Top of stack = 20
Stack = [9]
Temporary stack = [-1 2 4 6 20]

13. Top of stack = 9
Stack = [20]
Temporary stack = [-1 2 4 6 9]

14. Top of stack = 20
Stack = []
Temporary stack = [-1 2 4 6 9 20]

由於堆棧為空且臨時堆棧已排序,因此請從頂部開始打印臨時堆棧。

因此,輸出:20 9 6 4 2 -1

使用臨時堆棧對堆棧進行排序的算法

  1. 初始化堆棧數據結構,然後將元素插入/推入其中。
  2. 之後,創建一個函數sort(),該函數接受一個堆棧作為其參數。 在其中初始化另一個臨時/輔助堆棧tmpStack。
  3. 在原始堆棧不為空的情況下遍歷,創建一個變量tmp並將原始堆棧的頂部存儲在其中。 之後,彈出原始堆棧的頂部。
  4. 在tmpStack不為空且tmpStack的頂部(即臨時堆棧)大於或等於變量tmp時再次遍歷,將臨時堆棧的頂部推入原始堆棧中,然後彈出臨時堆棧的頂部。
  5. 將變量tmp推送到臨時堆棧中。
  6. 當臨時堆棧不為空時,將其打印在頂部,然後將其彈出。

推薦碼

C ++程序使用遞歸對堆棧進行排序

#include <iostream> 
#include <stack>
using namespace std; 
  
stack<int> sort(stack<int> &input){ 
    stack<int> tmpStack; 
  
    while(!input.empty()){ 
        
        int tmp = input.top(); 
        input.pop(); 
  
        while(!tmpStack.empty() && tmpStack.top() > tmp){ 
            input.push(tmpStack.top()); 
            tmpStack.pop(); 
        } 
  
        tmpStack.push(tmp); 
    } 
  
    return tmpStack; 
} 
  
int main(){ 
    stack<int> input; 
    
    input.push(20); 
    input.push(6); 
    input.push(-1); 
    input.push(2); 
    input.push(4); 
    input.push(9); 
  
    stack<int> tmpStack = sort(input); 
    
    while (!tmpStack.empty()){ 
        cout << tmpStack.top()<< " "; 
        tmpStack.pop(); 
    } 
}
20 9 6 4 2 -1

Java程序使用遞歸對堆棧進行排序

import java.util.*; 
  
class SortStack{ 
    
    public static Stack<Integer> sort(Stack<Integer> input){
        
        Stack<Integer> tmpStack = new Stack<Integer>(); 
        
        while(!input.isEmpty()){ 
            int tmp = input.pop(); 
          
            while(!tmpStack.isEmpty() && tmpStack.peek() > tmp){ 
                input.push(tmpStack.pop()); 
            } 
              
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    public static void main(String args[]){
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        input.add(20); 
        input.add(6); 
        input.add(-1); 
        input.add(2); 
        input.add(4); 
        input.add(9); 
      
        Stack<Integer> tmpStack=sort(input); 
        
        while (!tmpStack.empty()){ 
            System.out.print(tmpStack.pop()+" "); 
        }  
    } 
}
20 9 6 4 2 -1

複雜度分析

時間複雜度

O(n ^ 2) 其中n是堆棧中元素的數量。 由於我們將元素從臨時堆棧推回原始堆棧,以防臨時堆棧的頂部小於要推入的元素。 為了更好地理解,請考慮降序序列並嘗試運行該算法。

空間複雜度

O(N) 因為我們為n個元素使用了臨時堆棧空間。 該算法不計算原始堆棧使用的空間。