栈(Stack)
概述
- 栈就是一种 只允许在表尾进行插入和删除操作 的 线性表
- 栈的特点
- 先进后出 ,在表尾进行插入和删除操作
数组实现栈
- crown
- crown:使用crown来确定栈顶所在数组的下标,默认为 -1
- 空栈
- 当空栈时 ,crown = -1
- 栈是否为空
- 当 crown = -1 时 ,栈为空 ,不能 遍历 ,出栈 , 获取栈顶元素
- 栈是否已满
- 当 crown = 数组.length - 1 时 ,栈已满 , 不能 入栈
- 入栈
- 栈未满,才能入栈
- 先将 crown上移 ,再给数组下标为crown的元素赋值
- 栈满 ,不能入栈
- 出栈
- 栈不为空 ,才能出栈
- 将 crown往下移即可
- 栈为空 ,不能出栈
- 获取栈顶元素
- 栈不为空 ,才能获取栈顶元素
- 获得数组下标为crown的元素
- 栈为空 ,不能出栈
- 重置栈
- 让crown = -1 即可
- 打印栈
- 遍历数组下标范围为 [ 0 , crown ] ,即可
public class ArrayStack {
private int[] satck;
private int size;
private int crown = -1; // 栈顶
public ArrayStack(int size){
this.size = size;
satck = new int[size];
}
//入栈操作
public void push(int value){
if (!isFull()){
satck[++crown] = value;
}
}
//出栈
public void pop(){
if (!isEmpty()){
crown--;
}
}
//判断是否为空
public boolean isEmpty(){
return crown == -1;
}
//判断栈是否已满
public boolean isFull(){
return crown == size-1;
}
//获取栈顶元素
public int getTop(){
if (!isEmpty()){
return satck[crown];
}
return -1;
}
//重置栈
public void reset(){
crown = -1;
}
//打印栈 , 从栈顶开始打印
public void print(){
int j = 0;
for (int i = crown; i >= 0; i--) {
System.out.println("第"+(++j)+"个元素为:" + satck[i]);
}
}
}
/**
* @author 发着呆看星
* @create 2023/4/18
**/
public class ArrayStackTest {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ArrayStack arrayStack = new ArrayStack(5);
boolean p = true;
while (p){
System.out.println("==================栈的功能检测===================");
System.out.println("1) 入栈");
System.out.println("2) 出栈");
System.out.println("3) 重置栈");
System.out.println("4) 打印栈");
System.out.println("5) 取出栈顶元素");
System.out.println("6) 退出程序");
System.out.print("请选择你需要的功能(1~~6):");
int i = scanner.nextInt();
int j;
switch (i){
case 1:
System.out.print("请选择你要入栈的数字:");
j = scanner.nextInt();
arrayStack.push(j);
break;
case 2:
arrayStack.pop();
break;
case 3:
arrayStack.reset();
break;
case 4:
arrayStack.print();
break;
case 5:
int top = arrayStack.getTop();
System.out.println("栈顶元素为:"+top);
break;
case 6:
p = false;
break;
}
}
}
}
链表实现栈
- 实现思路
- 入栈:将每一个入栈的元素添加为链表的首节点
- 出栈:出栈则将链表的首节点进行删除
- 由于链表可以无限长,所以不用担心栈满的问题
- crown:代表栈顶元素的上一个元素 ,val属性默认为 -1 ,next 属性即为 栈顶元素
- 当 next == null 时 ,代表空栈
- 判断栈是否为空
- 当crown.next == null 时 ,栈为空
- 重置栈
- 即将 crown的next属性置为null
- 获取栈顶元素
- 即获取链表首节点(获取crown的next属性所代表的节点)
- 打印栈
- 即遍历链表
/**
* @author 发着呆看星
* @create 2023/4/18
**/
public class LinkedListStack {
private ListNode crown = new ListNode(-1,null);
// 判断是否为空
public boolean isEmpty(){
return crown.next == null;
}
// 入栈操作
public void push(int value){
ListNode temp = crown.next;
crown.next = new ListNode(value, temp);
}
// 出栈操作
public void pop(){
if (!isEmpty()){
crown.next = crown.next.next;
}
}
// 取出栈顶元素
public ListNode getTop(){
return crown.next;
}
// 重置栈
public void reset(){
crown.next = null;
}
// 打印栈 ,从栈顶开始
public void print(){
ListNode temp = crown;
int i = 0;
while (temp.next != null){
System.out.println("第"+(++i)+"个元素为:"+temp.next.val);
temp = temp.next;
}
}
}
/**
* @author 发着呆看星
* @create 2023/4/18
**/
public class LinkedListStackTest {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
LinkedListStack stack = new LinkedListStack();
boolean p = true;
while (p){
System.out.println("==================栈的功能检测===================");
System.out.println("1) 入栈");
System.out.println("2) 出栈");
System.out.println("3) 重置栈");
System.out.println("4) 打印栈");
System.out.println("5) 取出栈顶元素");
System.out.println("6) 退出程序");
System.out.print("请选择你需要的功能(1~~6):");
int i = scanner.nextInt();
int j;
switch (i){
case 1:
System.out.print("请选择你要入栈的数字:");
j = scanner.nextInt();
stack.push(j);
break;
case 2:
stack.pop();
break;
case 3:
stack.reset();
break;
case 4:
stack.print();
break;
case 5:
ListNode top = stack.getTop();
System.out.println("栈顶元素为:"+top);
break;
case 6:
p = false;
break;
}
}
}
}
春去秋来,岁岁平安
热门相关:地球第一剑 薄先生,情不由己 天启预报 豪门闪婚:帝少的神秘冷妻 霸皇纪