栈的顺序存储结构及Java实现
//MyStack.java
public class MyStack {
int MAX_SIZE = 100;
int top;
String[] stack;
public void init(String[] array){
stack = new String[100];
top = -1;
for (int i = 0; i < array.length; i++) {
stack[i] = array[i];
top = i;
}
}
public boolean push(String pusher){
if (top > MAX_SIZE) {
return false;
}else {
top = top + 1;
stack[top] = pusher;
return true;
}
}
public String pop(){
if (top == -1) {
return "Error";
}else {
String poper = stack[top];
stack[top]=null;
top = top - 1;
return poper;
}
}
public void displayStack(){
for (int i = 0; i <=top; i++) {
System.out.print(stack[i]+" ");
}
System.out.println();
}
public static void main(String args[]){
String[] array = {"1","2","3"};
MyStack myStack = new MyStack();
myStack.init(array);
myStack.displayStack();
myStack.push("4");
myStack.displayStack();
myStack.pop();
myStack.pop();
myStack.displayStack();
}
}
### 栈的Java语言实现详解
#### 一、栈的基本概念
栈是一种特殊的线性表，只允许在表的一端进行插入和删除操作，这一端称为栈顶（Top）。另一端称为栈底（Bottom），当表中无任何元素时称为空栈。栈遵循后进先出（Last In First Out, LIFO）的原则。
#### 二、栈的顺序存储结构
栈可以采用顺序存储或链式存储。其中，顺序存储是指利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针`top`指示栈顶位置。在本案例中，我们主要探讨的是顺序存储方式下的栈实现。
#### 三、MyStack类详解
##### 1. 类成员变量
- `int MAX_SIZE`: 定义了栈的最大容量，默认为100。
- `int top`: 栈顶指针，初始值为-1，表示栈为空。
- `String[] stack`: 用于存储栈中的元素的数组。
##### 2. 方法介绍
- **init()**：初始化方法，用于初始化栈。
```java
public void init(String[] array){
stack = new String[100];
top = -1;
for (int i = 0; i < array.length; i++) {
stack[i] = array[i];
top = i;
}
}
```
- 初始化一个长度为100的新数组。
- 将传入的数组元素依次存入新数组，并更新`top`值。
- **push()**：入栈操作。
```java
public boolean push(String pusher){
if (top > MAX_SIZE) {
return false;
}else {
top = top + 1;
stack[top] = pusher;
return true;
}
}
```
- 当栈满时返回`false`。
- 否则将元素添加至栈顶，并更新`top`。
- **pop()**：出栈操作。
```java
public String pop(){
if (top == -1) {
return "Error";
}else {
String poper = stack[top];
stack[top]=null;
top = top - 1;
return poper;
}
}
```
- 栈空时返回“Error”。
- 否则返回栈顶元素，并更新`top`。
- **displayStack()**：显示栈中所有元素。
```java
public void displayStack(){
for (int i = 0; i <=top; i++) {
System.out.print(stack[i]+" ");
}
System.out.println();
}
```
- **main()**：主函数演示栈的基本操作。
```java
public static void main(String args[]){
String[] array = {"1","2","3"};
MyStack myStack = new MyStack();
myStack.init(array);
myStack.displayStack();
myStack.push("4");
myStack.displayStack();
myStack.pop();
myStack.pop();
myStack.displayStack();
}
```
#### 四、共享栈的实现
共享栈是一种特殊类型的栈，可以在同一数组中支持多个栈的并发操作，本例中实现了两个栈共享同一个数组空间。
##### 1. 类成员变量
- `int MAX_SIZE`: 定义共享栈的最大容量。
- `String[] stack`: 存储元素的数组。
- `int top1`: 栈1的栈顶指针。
- `int top2`: 栈2的栈顶指针。
##### 2. 构造方法
```java
public MyShareStack(int MAX_SIZE){
this.MAX_SIZE = MAX_SIZE;
stack = new String[MAX_SIZE];
top1 = -1;
top2 = MAX_SIZE;
}
```
##### 3. 方法介绍
- **push()**：入栈操作。
```java
public boolean push(int stackNum, String pusher){
if(top1+1==top2){
return false;
}
if(stackNum==1){
top1 = top1 + 1;
stack[top1] = pusher;
} elseif(stackNum==2){
top2 = top2 - 1;
stack[top2] = pusher;
} else {
return false;
}
return true;
}
```
- 当栈间无空间时返回`false`。
- 否则根据指定栈号入栈。
- **pop()**：出栈操作。
```java
public String pop(int stackNum){
String result;
if(stackNum==1){
if(top1 == -1){
System.out.println("1空栈");
return "1ERROR";
} else {
result = stack[top1];
stack[top1] = null;
top1 = top1 - 1;
return result;
}
} elseif(stackNum==2){
if(top2 == MAX_SIZE){
System.out.println("2空栈");
return "2ERROR";
} else {
result = stack[top2];
stack[top2] = null;
top2 = top2 + 1;
return result;
}
} else {
System.out.println("no this stack");
return "ERROR";
}
}
```
- 当指定栈为空时返回错误信息。
- 否则返回出栈元素，并更新对应栈顶指针。
- **displayStack()**：显示栈中所有元素。
```java
public void displayStack(){
System.out.print("stack1:");
if(top1 == -1){
System.out.print("没有元素");
System.out.println();
} else {
for(int i = 0; i <= top1; i++){
```
#### 五、总结
本文通过具体的Java代码示例介绍了栈的基本概念、顺序存储结构以及栈的操作方法，包括初始化、入栈、出栈和显示栈内容等。此外，还扩展介绍了共享栈的概念及其实现方法。这些内容不仅有助于理解栈的工作原理，还能帮助读者掌握栈的Java实现技巧，为进一步学习算法和数据结构打下坚实的基础。
