好的网站你们会感谢我的,住建局官网查询系统,广西南宁房产网站建设,wordpress 头像本地化1. 栈(Stack)
1.1 概念 栈 #xff1a;一种特殊的线性表#xff0c;其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶#xff0c;另一端称为栈底。栈中的数据元素遵守后进先出LIFO #xff08; Last In First Out #xff09;的原则…1. 栈(Stack)
1.1 概念 栈 一种特殊的线性表其 只允许在固定的一端进行插入和删除元素操作 。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFO Last In First Out 的原则。 压栈栈的插入操作叫做进栈 / 压栈 / 入栈 入数据在栈顶 。 出栈栈的删除操作叫做出栈。 出数据在栈顶 。 1.2 栈的使用
方法功能Stack()构造一个空的栈E push(E e)将e入栈并返回eE pop()将栈顶元素出栈并返回E peek() 获取栈顶元素 int size() 获取栈中有效元素个数 boolean empty() 检测栈是否为空
1.3 栈的模拟实现
栈和ArrayList类似都是动态的顺序表 我们用数组来实现。
首先我们自己创建一个类MyStack里面定义一个数组成员变量用来模拟实现栈 代码
public class MyStack implements IStack{private int[] elem;private int usedSize; //数组中元素的个数private static final int DEFAULT_CAPACITY 10; //默认数组大小public MyStack() {elem new int[DEFAULT_CAPACITY];}
}
对于栈的实现入栈操作
在入栈的时候要先判断数组是否已满如果满则对数组进行扩容不满则直接在数组的最后加入元素。 public void push(int x) {if (full()) {elem Arrays.copyOf(elem,2*elem.length);}elem[usedSize]x;usedSize;}public boolean full() {if (usedSize elem.length) {return true;}return false;}
对于栈的实现出栈操作
在出栈的时候首先判断一下栈是否为空为空的话抛出EmptyException异常实现栈是否为空代码 public boolean empty() {//栈为空也就是数组里面没有元素return usedSize 0;}
出栈操作 public int pop() {if(empty()) {throw new EmptyException(栈为空); //自定义异常}int old elem[usedSize-1];usedSize--; //相当于删除return old;}自定义异常
public class EmptyException extends RuntimeException{public EmptyException(String msg) {super(msg);}
}对栈的实现peek()操作
peek()操作是查看栈顶元素的值若栈为空则抛出EmptyException异常不空直接返回数组最后一个元素的值即可。 public int peek() {if(empty()) {throw new EmptyException(栈为空);}return elem[usedSize-1];} 对栈的实现栈的大小
栈的大小直接返回数组元素的个数即可。 public int size() {return usedSize;}
1.4 栈的应用场景
1. 改变元素的序列 1. 若进栈序列为 1,2,3,4 进栈过程中可以出栈则下列不可能的一个出栈序列是C A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1 2. 一个栈的初始状态为空。现将元素 1 、 2 、 3 、 4 、 5 、 A 、 B 、 C 、 D 、 E 依次入栈然后再依次出栈则元素出栈的顺序是B 。 A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA 2. 将递归转化为循环
比如逆序打印链表
// 递归方式
void printList(Node head){if(null ! head){printList(head.next);System.out.print(head.val );}
}
// 循环方式
void printList(Node head){if(null head){return;}StackNode s new Stack();// 将链表中的结点保存在栈中Node cur head;while(null ! cur){s.push(cur);cur cur.next;}// 将栈中的元素出栈while(!s.empty()){System.out.print(s.pop().val );}
}
