开发笔记:结构与算法栈

package com.jkqiang.demo;
public class MyStack {
private int[] array; // 容量
private int maxSize; // 最大
private int top; // 栈顶
public MyStack(int size) {
this.maxSize = size;
array = new int[size];
top = -1;
}
// 压入数据
public void push(int value) {
if (top ) {
array[++top] = value;
}
}
// 弹出栈顶数据
public int pop() {
return array[top--];
}
// 访问栈顶数据
public int peek() {
return array[top];
}
// 判断栈是否为空
public boolean isEmpty() {
return (top == -1);
}
// 判断栈是否满了
public boolean isFull() {
return (top == maxSize - 1);
}
}

public class Test {
public static void main(String[] args) {
MyStack stack = new MyStack(3);
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.peek());
while(!stack.isEmpty()){
System.out.println(stack.pop());
}

}
}

package com.jkqiang.demo;
import java.util.Arrays;
import java.util.EmptyStackException;
public class ArrayStack {
// 存储元素的数组,声明为Object类型能存储任意类型的数据
private Object[] elementData;
private int top; // 指向栈顶的指针
private int size; // 栈的总容量
// 默认构造一个容量为10的栈
public ArrayStack() {
this.elementData = new Object[10];
this.top = -1;
this.size = 10;
}
public ArrayStack(int initialCapacity) {
if (initialCapacity <0) {
throw new IllegalArgumentException("栈初始容量不能小于0: " + initialCapacity);
}
this.elementData = new Object[initialCapacity];
this.top = -1;
this.size = initialCapacity;
}
// 压入元素
public Object push(Object item) {
isGrow(top + 1); // 是否需要扩容
elementData[++top] = item;
return item;
}
// 弹出栈顶元素
public Object pop() {
Object obj = peek();
remove(top);
return obj;
}
// 获取栈顶元素
public Object peek() {
if (top == -1) {
throw new EmptyStackException();
}
return elementData[top];
}
// 判断栈是否为空
public boolean isEmpty() {
return (top == -1);
}
// 删除栈顶元素
public void remove(int top) {
// 栈顶元素置为null
elementData[top] = null;
this.top--;
}
/**
* 是否需要扩容，如果需要，则扩大一倍并返回true，不需要则返回false
*
* @param minCapacity
* @return
*/
public boolean isGrow(int minCapacity) {
int oldCapacity = size;
// 如果当前元素压入栈之后总容量大于前面定义的容量，则需要扩容
if (minCapacity >= oldCapacity) {
// 定义扩大之后栈的总容量
int newCapacity = 0;
// 栈容量扩大两倍(左移一位)看是否超过int类型所表示的最大范围
if ((oldCapacity <<1) - Integer.MAX_VALUE > 0) {
newCapacity = Integer.MAX_VALUE;
} else {
newCapacity = (oldCapacity <<1); // 左移一位，相当于*2
}
this.size = newCapacity;
int[] newArray = new int[size];
elementData = Arrays.copyOf(elementData, size);
return true;
} else {
return false;
}
}
}

public class Test {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(3);
stack.push(1);
//System.out.println(stack.peek());
stack.push(2);
stack.push(3);
stack.push("abc");
System.out.println(stack.peek());
stack.pop();
stack.pop();
stack.pop();
System.out.println(stack.peek());

}
}

public class Test {
public static void main(String[] args) {
ArrayStack stack = new ArrayStack();
String str = "how are you";
char[] cha = str.toCharArray();
for(char c : cha){
stack.push(c); //入栈
}
while(!stack.isEmpty()){
System.out.print(stack.pop()); //出栈
}

}
}

public class Test {
////分隔符匹配
//遇到左边分隔符了就push进栈，遇到右边分隔符了就pop出栈，看出栈的分隔符是否和这个有分隔符匹配
public static void main(String[] args) {
ArrayStack stack = new ArrayStack(3);
String str = "12";
char[] cha = str.toCharArray();
for(char c : cha){
switch (c) {
case ‘{‘:
case ‘[‘:
case ‘<‘:
stack.push(c);
break;
case ‘}‘:
case ‘]‘:
case ‘>‘:
if(!stack.isEmpty()){
char ch = stack.pop().toString().toCharArray()[0];
if(c==‘}‘ && ch != ‘{‘
|| c==‘]‘ && ch != ‘[‘
|| c==‘)‘ && ch != ‘(‘){
System.out.println("Error:"+ch+"-"+c);
}
}
break;
default:
break;
}
}

}
}