概述
- 堆疊就是一種 只允許在表尾進行插入和洗掉操作 的 線性表
- 堆疊的特點
- 先進后出 ，在表尾進行插入和洗掉操作
陣列實作堆疊
- 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;
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/550512.html
標籤：其他
上一篇：堆疊(Stack)
下一篇：軟體安全之CRC檢測