栈
栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。
下面就用计算器作为示例进行讲解。
计算器需求
如上图:输入一个表达式 7*2*2-5+1-5+3-3
,然后计算出他的结果。
问:计算机底层是如何运算得到结果的?对于计算机而言他接受到的是一个 字符串,怎么计算出来的?
针对这个问题,我们讨论的就是 栈
栈介绍
stack 栈,是一个 先入后出(FILO,First In Last Out)的 有序列表。
是限制 线性表 中元素的插入和删除只能在线性表的 **同一端 **进行的一种特殊线性表:
- 栈顶(Top):允许插入和删除的一端,为 变化的一端。称为栈顶
- 栈底(Bottom):另一端为 固定的一端,称为栈底
根据上述定义,可知:
- 最先 放入栈中元素在 栈底
- 最后 放入栈中元素在 栈顶
而删除元素则刚好相反:
- 最先 放入栈中元素,最后 删除
- 最后 放入栈中元素,最先 删除
可以参考下图的,入栈和出栈图示:
栈的应用场景
-
子程序的调用
在跳往子程序前,会先将 下个指令的地址 存到堆栈中,直到子程序执行完后再 将地址取出,以 回到原来的程序中。
如方法中调用方法。
-
处理递归调用
和子程序调用类似,只是除了存储下一个指令的地址外,也将参数、区域变量等数据存入堆栈中。
-
表达式的转换(中缀表达式转后缀表达式)与求值(实际解决)
-
二叉树的遍历
-
图形的深度优先(depth-first)搜索法
数组模拟栈
参考前面的入栈和出栈的图,思路如下:
- 定义一个数组,来模拟栈
- 定义一个 top 变量表示栈顶,初始化为
-1
- 入栈:
stack[++top]=data
- 出栈:
return stack[top--]
/**
* 数组模拟栈
*/
//定义一个 ArrayStack 表示栈
class ArrayStack {
private int maxSize; // 栈的大小
private int[] stack; // 数组,数组模拟栈,数据就放在该数组
private int top = -1;// top表示栈顶,初始化为-1
//构造器
public ArrayStack(int maxSize) {
this.maxSize = maxSize;
stack = new int[this.maxSize];
}
//栈满
public boolean isFull() {
return top == maxSize - 1;
}
//栈空
public boolean isEmpty() {
return top == -1;
}
//入栈-push
public void push(int value) {
//先判断栈是否满
if(isFull()) {
System.out.println("栈满");
return;
}
top++;
stack[top] = value;
}
//出栈-pop, 将栈顶的数据返回
public int pop() {
//先判断栈是否空
if(isEmpty()) {
//抛出异常
throw new RuntimeException("栈空,没有数据~");
}
int value = stack[top];
top--;
return value;
}
//显示栈的情况[遍历栈], 遍历时,需要从栈顶开始显示数据
public void list() {
if(isEmpty()) {
System.out.println("栈空,没有数据~~");
return;
}
//需要从栈顶开始显示数据
for(int i = top; i >= 0 ; i--) {
System.out.printf("stack[%d]=%d\n", i, stack[i]);
}
}
}
测试用例
public class ArrayStackTest {
@Test
public void pushTest() {
ArrayStack stack = new ArrayStack(4);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.list();
stack.push(5);
}
@Test
public void popTest() {
ArrayStack stack = new ArrayStack(4);
stack.push(1);
stack.push(2);
stack.list();
System.out.println("pop 数据:" + stack.pop());
stack.list();
System.out.println("pop 数据:" + stack.pop());
stack.list();
}
}
输出信息
====== pushTest ======
stack[3]=4
stack[2]=3
stack[1]=2
stack[0]=1
栈满
====== popTest
stack[1]=2
stack[0]=1
pop 数据:2
stack[0]=1
pop 数据:1
栈空,没有数据~~
链表模拟栈
思路:
- 首先定义一个链表节点类
- 想的是怎么压入数据? 根据栈的特点,可以用头插法来添加链表的节点,实现先入后出。
- 定义一个链表栈类
- 入栈
push
通过头插法进行插入节点 - 出栈
pop
通过删除链表的第一个节点 - 展示栈内数据,遍历链表即可
- 入栈
链表节点类
class node{
private int data;//数据域
private node next = null;//下一个节点,默认为空
public node(int data) {
this.data = data;//设置数据
}
public int getData() {
return data;
}
public node getNext() {
return next;
}
public void setNext(node next) {
this.next = next;
}
//为了打印方便重写toString
@Override
public String toString() {
return data + "";
}
}
链表栈类
class LinkedListStack {
private int maxSize;//栈的最大容量
private int size;//用来记录栈中数据个数
private node head = new node(0);//头节点
private node helper;//定义一个辅助变量用来帮助实现头插法
public LinkedListStack(int maxSize) {
this.maxSize = maxSize;//设置栈的最大容量
}
//判断是否满栈
public boolean isFull() {
return size == maxSize;
}
//判断是否空栈
public boolean isEmpty() {
return size == 0;
}
//入栈
public void push(int data) {
//判断是否满栈
if (isFull()) {
System.out.println("栈满");
return;
}
//创建新节点
node node = new node(data);
//入栈
if (size == 0) {
head.setNext(node);
helper = node;//将辅助变量指向新添加的节点
size++;
} else {
head.setNext(node);//将头节点的next指向新的节点
node.setNext(helper);//将新的节点的next指向久节点
helper = node;//再将辅助变量指向新节点
size++;
}
}
//出栈
public int pop() {
//判断是否是空栈
if (isEmpty()) {
throw new RuntimeException("栈空,没有数据~~");
}
//获取第一个节点的数据,因为是头插法,所以满足栈的性质
int data = head.getNext().getData();
//将第一个节点删除
head.setNext(helper.getNext());//将头节点的next指向出栈节点的下一个节点
helper = helper.getNext();//将辅助变量移动到出栈节点的下一个节点
size--;
return data;
}
//显示栈的情况[遍历栈], 遍历时,需要从栈顶开始显示数据
public void list() {
if (isEmpty()) {
System.out.println("栈空,没有数据");
return;
}
//设置辅助变量,来遍历链表
node temp = helper;//helper就是指向链表中第一个节点
for (int i = size - 1; i >= 0; i--) {
System.out.printf("stack[%d]=%d\n", i, temp.getData());
temp = temp.getNext();
}
}
}
测试用例
/**
* 链表实现栈
*/
public class test {
public static void main(String[] args) {
//============push========================
LinkedListStack linkedListStack = new LinkedListStack(4);
System.out.println("================push==================");
linkedListStack.push(1);
linkedListStack.push(2);
linkedListStack.push(3);
linkedListStack.push(4);
linkedListStack.list();
linkedListStack.push(5);
//============pop========================
System.out.println("==================pop====================");
System.out.println(linkedListStack.pop());
System.out.println(linkedListStack.pop());
linkedListStack.list();
System.out.println(linkedListStack.pop());
System.out.println(linkedListStack.pop());
linkedListStack.list();
try {
System.out.println(linkedListStack.pop());
} catch (Exception e) {}
}
}
测试输出
================push==================
stack[3]=4
stack[2]=3
stack[1]=2
stack[0]=1
栈满
==================pop====================
4
3
stack[1]=2
stack[0]=1
2
1
栈空,没有数据