# 基于可增长数组的堆栈

## 问题陈述

• 严格策略–在这种情况下，将常量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```

```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.```

## 代码

### 用于可增长的基于数组的堆栈的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```