還是在上一節的基礎上進行寫，這堆疊基本上也是陣列的一個子集，閹割了陣列的功能，是后進先出
一、堆疊的實作
1. 自定義陣列
package com.md.java2;
/**
* @author md
* @Desc
* @date 2020/9/13 22:21
*/
public class Array<E> {
private E[] data;
private int size;
// 0. 初始化，默認引數
public Array(int capacity) {
data = https://www.cnblogs.com/mengd/p/(E[]) new Object[capacity];
size = 0;
}
public Array(){
this(10);
}
// 1. 獲取陣列長度
public int getCapacity(){
return data.length;
}
public int getSize(){
return size;
}
// 補充：動態陣列
private void resize(int newCapacity){
E[] newData = (E[]) new Object[newCapacity];
// 把之前陣列中存放的資料放入到新的陣列當中
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
// 新的陣列再指向原來的陣列
data = newData;
}
// 2. 指定位置添加資料
public void add(int index , E e){
if (size == getCapacity())
// throw new IllegalArgumentException("add failed");
// 如果此時陣列滿的話，就進行擴容
resize(2 * data.length);
if (index < 0 || index > size)
throw new IllegalArgumentException("add failed");
for (int i = size - 1; i >=index ; i--) {
data[i+1] = data[i];
}
data[index] = e;
size++;
}
// 3. 向末尾添加資料
public void addLast(E e){
add(size,e);
}
// 4. 向開頭添加資料
public void addFirst(E e){
add(0,e);
}
// 5. 獲取指定索引位置的元素
public E get(int index){
if (index < 0 || index >= size)
throw new IllegalArgumentException("get failed");
return data[index];
}
// 查看最后一個元素
public E getLast(){
return get(size-1);
}
// 6. 洗掉指定位置的資料,并回傳該資料
public E remove(int index ){
if (index < 0 || index > size-1)
throw new IllegalArgumentException("remove failed");
// 先保存要洗掉的資料
E num = data[index];
for (int i = index+1; i < size ; i++) {
data[i-1] = data[i];
}
size--;
// 如果此時陣列中剩余的是當前陣列長度的一半，那么把陣列的長度縮成一半
// 由于時間復雜度的緣故，均攤復雜度，所以修改成下面的才合適
if (size == data.length / 4 && data.length / 2 != 0)
resize(data.length/2);
return num;
}
// 7. 洗掉最后一個資料
public E removeLast(){
return remove(size-1);
}
// 8. 洗掉第一個資料
public E removeFirst(){
return remove(0);
}
// 9. 判斷是否為空
public boolean isEmpty(){
return size == 0;
}
// 重新toString
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Arr: size=%d , capacity=%d/n",size,getCapacity()));
res.append("[");
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size-1)
res.append(",");
}
res.append("]");
return res.toString();
}
}
2. 寫介面
package com.md.java2;
/**
* @author md
* @Desc
* @date 2020/9/13 22:22
*/
public interface Stack<E> {
/**
* 獲取堆疊中元素的個數
* @return
*/
int getSize();
/**
* 判斷堆疊是否為空
* @return
*/
boolean isEmpty();
/**
* 入堆疊
* @param e
*/
void push(E e);
/**
* 彈堆疊
* @return
*/
E pop();
/**
* 查看堆疊頂元素
* @return
*/
E peek();
}
3. 實作介面
package com.md.java2;
/**
* @author md
* @Desc
* @date 2020/9/13 22:22
*/
public class ArrayStack<E> implements Stack<E> {
private Array<E> array;
// 1. 在建構式中進行初始化
public ArrayStack(int capacity){
array = new Array<>(capacity);
}
public ArrayStack(){
array = new Array<>();
}
// 2. 獲取堆疊中元素的個數
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
// 3. 入堆疊，只需要呼叫自定義陣列的向最后位置添加元素的方法即可
@Override
public void push(E e) {
array.addLast(e);
}
// 4. 彈堆疊，只需洗掉最后一個元素
@Override
public E pop() {
return array.removeLast();
}
// 5. 查看元素，只需要查看堆疊頂元素，也就是陣列中的最后一個元素
@Override
public E peek() {
return array.getLast();
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack: ");
res.append("[");
for (int i = 0; i < array.getSize(); i++) {
res.append(array.get(i));
if (i != array.getSize()-1)
res.append(",");
}
res.append("] top");
return res.toString();
}
}
4. 測驗
package com.md.java2;
/**
* @author md
* @Desc
* @date 2020/9/13 22:31
*/
public class Main {
public static void main(String[] args) {
ArrayStack<Integer> stack = new ArrayStack<>();
for (int i = 0; i < 10; i++) {
stack.push(i);
}
System.out.println(stack);
stack.pop();
System.out.println(stack);
Integer i = stack.peek();
System.out.println("此時堆疊頂元素為："+i);
}
}
二、堆疊的應用：括號匹配
具體的可以看https://leetcode-cn.com/problemset/all/
package com.md.java1;
import java.util.Stack;
/**
* @author md
* @Desc 堆疊的應用：括號匹配
* @date 2020/9/13 16:46
*/
public class Solution {
public boolean isValid(String s){
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
// 遍歷獲取到傳入的字符
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{')
stack.push(c);
else{
if (stack.isEmpty())
return false;
char topChar = stack.pop();
if (c == ')' && topChar != '(')
return false;
if (c == ']' && topChar != '[')
return false;
if (c == '}' && topChar != '{')
return false;
}
}
return stack.isEmpty();
}
public static void main(String[] args) {
System.out.println((new Solution()).isValid("(){}[]"));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/39692.html
標籤：Java