能否提供顺序栈实现数制转换和括号匹配以及链式栈实现数制转换和括号匹配的具体代码示例?包括必要的数据结构定义和核心函数实现。
时间: 2024-10-20 13:11:11 浏览: 34
当然可以,这里我会分别给出顺序栈和链式栈实现数制转换和括号匹配的简单示例。
**顺序栈实现** (基于数组)
```java
// 数据结构 - 数制栈
class IntStack {
int[] stack;
int top;
// 初始化栈
IntStack(int size) {
stack = new int[size];
top = -1;
}
// 入栈操作
void push(int x) {
if (top == stack.length - 1) {
throw new StackOverflowError("Stack is full");
}
stack[++top] = x;
}
// 出栈操作
int pop() {
if (isEmpty()) {
throw new EmptyStackException("Stack is empty");
}
return stack[top--];
}
// 判断栈是否为空
boolean isEmpty() {
return top == -1;
}
}
// 括号匹配 - 使用顺序栈
boolean isValid(String s) {
IntStack stack = new IntStack();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(0);
} else if (c == ')') {
if (stack.isEmpty() || stack.pop() != 0) {
return false;
}
}
}
return stack.isEmpty();
}
// 数制转换 - 非常基础,仅支持十进制到任意进制
int decimalToAnyBase(int num, int base) {
String result = "";
while (num > 0) {
result = Integer.toString(num % base) + result;
num /= base;
}
return Integer.parseInt(result);
}
```
**链式栈实现** (基于链表节点)
```java
// 数据结构 - 链式栈
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedListStack {
Node top;
// 初始化栈
LinkedListStack() {
top = null;
}
// 入栈操作
void push(int x) {
Node newNode = new Node(x);
newNode.next = top;
top = newNode;
}
// 出栈操作
int pop() {
if (isEmpty()) {
throw new EmptyStackException("Stack is empty");
}
int data = top.data;
top = top.next;
return data;
}
// 判断栈是否为空
boolean isEmpty() {
return top == null;
}
}
// 括号匹配 - 链式栈
boolean isValid(String s) {
LinkedListStack stack = new LinkedListStack();
for (char c : s.toCharArray()) {
if (c == '(') {
stack.push(0);
} else if (c == ')') {
if (stack.isEmpty() || stack.pop() != 0) {
return false;
}
}
}
return stack.isEmpty();
}
// 数制转换 - 与顺序栈一样,仅支持十进制到任意进制
int decimalToAnyBase(int num, int base) {
// ... (链式栈下的实现与顺序栈类似)
}
```
阅读全文