栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈可以类比成现实生活中的弹夹或者羽毛球桶
用数组模拟栈的思路分析如图：
1.定义一个top变量（指针）表示栈顶初始化为-1.
2.定义一个变量来记录栈的大小。
3.入栈操作有数据加入到栈中：top++; arr[top]=value;
4.出栈操作： int value=arr[top]; top–; return value;
下面看完整代码示例：
class Stack{
public int maxsize;//栈的大小
public int top=-1;//栈顶
public int[] arr;
public Stack(int maxsize) {
this.maxsize = maxsize;
arr=new int[maxsize];
}
//判断栈是否为空
public boolean isEmpty(){
return top==-1;
}
//判断栈是否满
public boolean isFull(){
return top==maxsize-1;
}
//添加一个元素
public void push(int value){
if(isFull()){
throw new RuntimeException("栈满");
}
top++;
arr[top]=value;
}
//弹出一个元素
public int pop(){
if(isEmpty())
throw new RuntimeException("栈空");
int value=arr[top];
top--;
return value;
}
//遍历栈中的元素
public void traverse(){
if (isEmpty()){
return;
}
//需要从栈顶开始显示数据
for(int i = top; i >= 0 ; i--) {
System.out.printf("stack[%d]=%d\n", i, arr[i]);
}
}
}
入栈操作 top++;arr[top]=value;其实可以直接改写为arr[++top]=value;
出栈操作可以将 int value=arr[top]; top–;return value;改为return arr[top–];
思路分析：
入栈操作：用一个临时节点保存当前栈顶节点，将入栈的新节点作为栈顶元素，并将next域指向原来的旧节点。 Node temp=top; top.setNext(temp);
出栈操作：先判断栈是否为空，不为空则将top节点的数据返回，并将top指向top的下一个next域：top=top.getNext();
public class LinkedListStack<V> {
static class Node<V>{
private V data;
private Node<V> next;
public V getData() {
return data;
}
public void setData(V data) {
this.data = data;
}
public Node<V> getNext() {
return next;
}
public void setNext(Node<V> next) {
this.next = next;
}
}
public int stackSize;//栈内元素的个数
public Node<V> top;//栈顶元素
public LinkedListStack() {
stackSize = 0;
top = null;
}
//入栈
public void push(V element){
Node<V> temp=top;
top=new Node<>();
top.setData(element);
top.setNext(temp);
stackSize++;
}
//出栈
public V pop(){
if (isEmpty())
throw new RuntimeException("empty stack");
V value=top.getData();
//栈顶指向下一个元素
top=top.getNext();
stackSize--;
return value;
}
//查看栈顶元素
public V peek(){
return top.getData();
}
//判断是否为空
public boolean isEmpty(){
return stackSize==0;
}
//查看栈内元素个数
public int getStackSize(){
return stackSize;
}
}
public class Test {
public static void main(String[] args) {
LinkedListStack<String> stack = new LinkedListStack<>();
stack.push("a");
stack.push("b");
stack.push("c");
System.out.println(stack.pop());
System.out.println(stack.peek());
System.out.println(stack.getStackSize());
}
}
测试结果:
c
b
2
