基于可增长数组的堆栈


难度级别 中等
经常问 空气质量 沃尔玛实验室
排列

问题陈述

在“堆栈已满”的情况下,使用基于数组的可增长堆栈。 在这里,旧阵列替换为新的较大阵列。 新阵列的大小是使用以下两种策略确定的:

  • 严格策略–在这种情况下,将常量c表示为已添加到现有堆栈中,即n = n + c,其中n是现有堆栈的大小。
  • 增长策略–在这种情况下,我们将现有堆栈的大小增加一倍,即n = 2n。

编写程序以实现可增长的基于数组的堆栈。

基于可增长数组的堆栈

使用案列

push(100)

push(200)

push(300)

display()

push(400)

display()
Stack: 100 200 300

Stack: 100 200 300 400

说明:我们已经执行了堆栈的基本操作。 因此,首先,我们压入100、200、300,然后显示堆栈内容。 在按下400之后,我们再次显示堆栈内容。

push(1)

push(2)

display()

push(3)

display()
Stack: 1 2

Stack: 1 2 3

基于可增长数组的堆栈算法

1. Create three global variables bound, top, and length, and initialize them as 3, -1, and 0 respectively.
2. After that, create a function to create extra space for an array-based stack that accepts an integer array as it's parameter.
3. Initialize a new array inside the function of length equals the sum of the length of given array and the bound variable.
4. Traverse through the given array and update the value at the current index in the new array as the value at the current index in the given array.
5. Update the variable-length as the sum of variable length itself and the bound variable and return the new array.
6. Similarly, create a function to push/insert the elements which accept an integer array and an integer variable as it's parameter.
7. Check if the value of top is equal to the length - 1, call the function to create a new array. Store the integer variable in the array at index equals to top + 1 and return the array.
8. After that, create a function to pop/remove the top element from the array. Decrement the variable top by 1.
9. Similarly, create a function to print the elements in the array which accepts an integer array as it's a parameter.
10. Check if the top is equal to -1, print "Stack is Empty".
11. Else print the array.

在这里,我们采用了严格的策略,每当需要增加规模时,。 我们只是每次都继续添加相同的BOUND。 因此,每当需要添加额外的尺寸时, 排列,我们需要将原始数组复制到新数组中,然后添加新元素。 如果我们的空间有限,那么这种方法是好的。 但是,如果我们想要更好的时间复杂性,我们应该采用增长策略。

代码

用于可增长的基于数组的堆栈的C ++程序

#include <iostream> 
using namespace std; 
  
#define BOUND 3
  
int top = -1; 
  
int length = 0; 
  
int* create_new(int* a){ 
    int* new_a = new int[length + BOUND]; 
  
    for(int i = 0; i < length; i++){ 
        new_a[i] = a[i]; 
    }
  
    length += BOUND; 
    return new_a; 
} 
  
int* push(int* a, int element){ 
    if(top == length - 1){ 
        a = create_new(a);
    }
  
    a[++top] = element; 
    return a; 
} 
  
void pop(int* a){ 
    top--; 
} 
  
void display(int* a){ 
    if(top == -1){ 
        cout << "Stack is Empty" << endl; 
    }
    
    else{ 
        cout << "Stack: "; 
        for(int i = 0; i <= top; i++){ 
            cout << a[i] << " "; 
        }
        cout << endl; 
    } 
} 
  
int main(){ 
    int *a = create_new(a); 
  
    a = push(a, 100); 
    a = push(a, 200); 
    a = push(a, 300); 
    display(a); 
    a = push(a, 400); 
    display(a); 
  
    return 0; 
}
Stack: 100 200 300 
Stack: 100 200 300 400

Java程序,用于基于数组的可扩展堆栈

class GrowableStack{ 
  
    static final int BOUND = 3; 
      
    static int top = -1; 
      
    static int length = 0; 
      
    static int[] create_new(int[] a){ 
        int[] new_a = new int[length + BOUND]; 
      
        for(int i = 0; i < length; i++){ 
            new_a[i] = a[i]; 
        }
      
        length += BOUND; 
        return new_a; 
    } 
      
    static int[] push(int[] a, int element){ 
        if(top == length - 1){ 
            a = create_new(a);
        }
      
        a[++top] = element; 
        return a; 
    } 
      
    static void pop(int[] a){ 
        top--; 
    } 
      
    static void display(int[] a){ 
        if(top == -1){ 
            System.out.println("Stack is Empty");
        }
        
        else{ 
            System.out.print("Stack: "); 
            for(int i = 0; i <= top; i++){ 
                System.out.print(a[i] + " ");
            }
            System.out.println(); 
        } 
    } 
      
    public static void main(String args[]){ 
        int []a = create_new(new int[length + BOUND]); 
      
        a = push(a, 100); 
        a = push(a, 200); 
        a = push(a, 300); 
        display(a); 
      
        a = push(a, 400); 
        display(a); 
    } 
}
Stack: 100 200 300 
Stack: 100 200 300 400

复杂度分析

时间复杂度

上),因为我们只是将元素推入堆栈。 这里N是要推送的元素数。 由于所有这些操作都是O(1),因此是恒定时间操作。 因此,将这些操作进行N次操作将导致线性时间复杂度算法。

空间复杂度

上),其中N是堆栈中元素的数量。 因为我们使用了存储N个元素的单个堆栈。 因此,该算法具有线性空间复杂度。