栈的分类
- 栈是特殊的线性表
- 栈的典型应用递归，四则运算表达式求值。
栈的分类有两种：
- 静态栈(数组实现)
- 动态栈(链表实现)
我们接下来会分别实现这两种栈。
栈的操作
数组方式
代码GitHub地址 - 欢迎star
栈节点
public class Node {
private int value;
public Node() {
}
public Node(int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
由于是数组方式存储的，每个节点都能方便的存取它的前驱后继节点。所以我们声明的栈节点只需要存在一个存值的value属性即可。
栈
public class Stacks {
private static final int MAX_SIZE = 100;
private static final int MIN_SIZE = -1;
/**
* 空栈默认 top = 1
*/
private int top = -1;
/**
* 顺序栈默认最大 100
*/
private Node[] nodes = new Node[MAX_SIZE];
public Stacks() {
}
public Stacks(int top) {
this.top = top;
}
public Stacks(Node[] nodes) {
this.nodes = nodes;
}
public Stacks(int top, Node[] nodes) {
this.top = top;
this.nodes = nodes;
}
}
由于是数组形式声明的栈，所以我们需要规定栈最大容量，并且设立top变量来定位栈顶元素。
入栈
/**
* 入栈
*
* @param stacks
* @param value
* @return
*/
public static int push(Stacks stacks, int value) {
Node node = new Node(value);
if (stacks.top == MAX_SIZE) {
return 0;
}
stacks.top++;
stacks.nodes[stacks.top] = node;
return 1;
}
很简单，只需要注意代码执行顺序即可，需要明白栈顶指针指向栈顶元素。每次入栈操作执行完top必然会++那么它又需要在入栈后指向最新插入的新元素，就必然在赋值前++,同时赋值的时候找数组的top索引处给就是最方便快捷的。
出栈
/**
* 出栈
*
* @param stacks
* @return
*/
public static int pop(Stacks stacks) {
if (stacks.top == MIN_SIZE) {
return 0;
}
stacks.nodes[stacks.top] = null; //
stacks.top--;
return 1;
}
和入栈操作相反，需要把栈的top索引处的元素置空，在top还在指向该节点的时候置空，然后top--即可。
遍历
/**
* 遍历
*
* @param stacks
*/
public static void traverse(Stacks stacks) {
int top = stacks.top;
while (top > MIN_SIZE) {
System.out.println(stacks.nodes[top--].getValue());
}
}
根据top从顶到底，从最大值到0遍历即可。
需要注意的是：不要直接操作Stack.top变量，而是把他取出来换其他局部变量操作。否则在你遍历完之后，栈中就真的没有元素了。因为Stack.top变量已经被你指向了栈底。
判断是否为空
/**
* 判断是否为空
*
* @param stacks
* @return
*/
public static boolean isEmpty(Stacks stacks) {
return stacks.top == MIN_SIZE;
}
清空栈
/**
* 清空栈
*
* @param stacks
*/
public static void clean(Stacks stacks) {
while (stacks.top > MIN_SIZE) {
stacks.nodes[stacks.top] = null;
stacks.top--;
}
}
也可以循环调用出栈(pop)方法。通过while循环来判断top变量是否大于0来判断是否空栈。
共享栈
共享栈一般的使用场景是两个栈的空间有相反的需求关系的时候。也就是一个栈增长的时候另一个栈在缩短的情况。比如购买股票，有人买入就一定有人卖出，总量放在那里不变。不可能两面都有人一直买入，那么栈很快就会溢出了。所以在使用共享栈的时候考虑好使用场景是否符合。
public class SharedStack {
private static final int MAX_SIZE = 100;
private static final int MIN_SIZE = -1;
public Node[] stackElement = new Node[MAX_SIZE];
/**
* 栈1的栈顶指针初始为-1
*/
public int top_1 = MIN_SIZE;
/**
* 栈2的栈顶指针 初始为n
*/
public int top_2 = MAX_SIZE;
public SharedStack() {
}
}
共享栈 - 入栈
/**
* 入栈
*
* @param stack 栈
* @param value 插入的元素值
* @param stackNumber 栈序号，栈1，还是栈2
* @return 成功与否，失败0，成功返回插入的值
*/
public static int push(SharedStack stack, int value, int stackNumber) {
Node newNode = new Node(value);
if (stack.top_1 + 1 == stack.top_2) {
return 0;
}
if (stackNumber == 1) {
// 栈1插入元素
stack.stackElement[++stack.top_1] = newNode;
} else if (stackNumber == 2) {
// 栈2插入元素
stack.top_2--;
stack.stackElement[--stack.top_2] = newNode;
}
return value;
}
共享栈 - 出栈
/**
* 出栈
*
* @param stack
* @param stackNumber
* @return 删除的栈顶元素的值
*/
public static int pop(SharedStack stack, int stackNumber) {
int value = 0;
if (stackNumber == 1) {
if (stack.top_1 == MIN_SIZE) {
return 0;
}
value = stack.stackElement[stack.top_1--].getValue();
} else if (stackNumber == 2) {
if (stack.top_2 == MAX_SIZE) {
return 0;
}
value = stack.stackElement[stack.top_2++].getValue();
}
return value;
}
链表方式
代码GitHub地址 - 欢迎star
栈节点
public class Node {
private int value;
private Node nextNode;
public Node() {
}
public Node(int value) {
this.value = value;
}
public Node(Node nextNode) {
this.nextNode = nextNode;
}
public Node(int value, Node nextNode) {
this.value = value;
this.nextNode = nextNode;
}
getter/setter
可以看出相比于数据方式，栈节点多了一个nextNode指针域。指向它的后继节点
栈
public class Stacks {
/**
* 栈顶结点
*/
private Node topElement;
/**
* 栈底节点
*/
private Node bottmElement;
public Stacks() {
}
public Stacks(Node topElement, Node bottmElement) {
this.topElement = topElement;
this.bottmElement = bottmElement;
}
}
此时栈如果是空栈的话topElement = bottmElement
入栈
/**
* 入栈
*
* @param stacks
* @param value
* @return
*/
public static int push(Stacks stacks, int value) {
Node node = new Node(value);
// 下一节点为根节点
node.setNextNode(stacks.topElement);
stacks.topElement = node;
return 1;
}
需要记住的一个思路就是，新插入节点的后继节点是当前栈的栈顶元素。插入之后才能移动该栈顶元素的指针topElement。
出栈
/**
* 出栈
*
* @param stacks
* @return
*/
public static int pop(Stacks stacks) {
if (stacks.topElement == stacks.bottmElement) {
return 0;
}
stacks.topElement = stacks.topElement.getNextNode();
return 1;
}
栈顶指针指向其后继节点即可。
遍历
/**
* 遍历
*
* @param stacks
*/
public static void traverse(Stacks stacks) {
Node node = stacks.topElement;
while (node != stacks.bottmElement) {
System.out.println(node.getValue());
node = node.getNextNode();
}
}
换一个节点指向当前栈顶节点的节点即可。然后一直遍历输出到栈底节点为止。
判断是否为空
/**
* 判断是否为空
*
* @param stacks
* @return
*/
public static boolean isEmpty(Stacks stacks) {
return stacks.topElement == stacks.bottmElement;
}
清空
/**
* 清空
*
* @param stacks
*/
public static void clean(Stacks stacks) {
stacks.bottmElement = null;
stacks.topElement = stacks.bottmElement;
}
