一.簡(jiǎn)介
??棧是一種LIFO結(jié)構(gòu)苫昌，使用數(shù)組頭部添加元素的時(shí)間復(fù)雜度是O(n),而向尾部添加元素或刪除元素的時(shí)間復(fù)雜度為O(1),所以我們使用數(shù)組的尾部作為棧的top府怯，元素出棧即刪除數(shù)組的尾部元素鹦肿，入棧即在數(shù)組尾部添加元素逼泣。
二.數(shù)組棧的代碼實(shí)現(xiàn)
- 這里為了方便我封裝了自己的數(shù)組結(jié)構(gòu)MyArray药磺，實(shí)現(xiàn)了數(shù)據(jù)的動(dòng)態(tài)擴(kuò)容和縮容
public class MyArray<T> {
private T[] data;
private int size;
@SuppressWarnings("unchecked")
public MyArray(int capacity) {
this.data = (T[]) new Object[capacity];
this.size = 0;
}
/**
* 無(wú)參構(gòu)造函數(shù)初始容量10
*/
@SuppressWarnings("unchecked")
public MyArray() {
this(10);
}
/**
* 獲取元素個(gè)數(shù)
*/
public int getSize() {
return size;
}
/**
* 獲取數(shù)組容量
*/
public int getCapacity() {
return data.length;
}
/**
* 數(shù)組是否是空的
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 在index 索引位置添加一個(gè)元素t
* O(n/2)=O(n)時(shí)間復(fù)雜度
*/
public void add(int index, T t) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add fail,Require index >=0 and index <=size");
}
if(size==data.length){
resizeArray(2*data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = t;
size++;
}
/**
* 在數(shù)組開(kāi)始位置添加一個(gè)元素t
* O(n)時(shí)間復(fù)雜度
*/
public void addFirst(T t) {
add(0, t);
}
/**
* 在當(dāng)前所有元素后添加一個(gè)元素t
* O(1)均攤復(fù)雜度
*/
public void addLast(T t) {
add(size, t);
}
/**
* 獲取index索引位置的元素
* 0(1)
*/
public T get(int index) {
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("Get failed,index is illegal");
}
return data[index];
}
public T getFirst(){
return get(0);
}
public T getLast(){
return get(size-1);
}
/**
* 查找數(shù)組中元素e所在的索引告组，如果不存在元素e，則返回-1
* O(n)
*/
public int find(T t) {
for (int i = 0; i < size; i++) {
if (data[i].equals(t) ) {
return i;
}
}
return -1;
}
/**
* 是否包含某個(gè)元素
* O(n)
* @param t
* @return
*/
public boolean contains(T t) {
return find(t) != -1;
}
/**
* 修改index索引位置的元素
* O(1)時(shí)間復(fù)雜度
*/
public void set(int index, T t) {
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("Get failed,index is illegal");
}
data[index] = t;
}
/**
* 刪除index索引的元素癌佩，并返回該元素
* O(n/2)=O(n)時(shí)間復(fù)雜度
*/
public T remove(int index) {
if (index < 0 || index > size - 1) {
throw new IllegalArgumentException("Get failed,index is illegal");
}
T ret = data[index];
for (int i = index; i < size; i++) {
data[i] = data[i + 1];
}
data[size] = null;
size--;
//防止復(fù)雜度震蕩木缝，防止創(chuàng)建0size的數(shù)組
if (size == data.length / 4&& data.length / 2 != 0) {
resizeArray(data.length/2);
}
return ret;
}
public void removeElement(T t) {
int i = find(t);
if (i != -1) {
remove(i);
}
}
/**
* 移除所有元素中的第一個(gè)元素
* O(n)時(shí)間復(fù)雜度
*/
public T removeFirst() {
return remove(0);
}
/**
* 移除所有元素中的最后個(gè)元素
* O(1)時(shí)間復(fù)雜度
*/
public T removeLast() {
return remove(size - 1);
}
@SuppressWarnings("unchecked")
public T[] resizeArray(int length) {
T[] newArray = (T[]) new Object[length];
for (int i = 0; i < size; i++) {
newArray[i] = data[i];
}
data=newArray;
return newArray;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(String.format("Array : size = %d ,capacity = %d \n", size, data.length));
builder.append("[");
for (int i = 0; i < size; i++) {
builder.append(data[i]);
if (i != size - 1) {
builder.append(",");
}
}
builder.append("]");
return builder.toString();
}
}
- 使用MyArray實(shí)現(xiàn)棧
public interface Stack<E> {
int getSize();
boolean isEmpty();
E peek();
E pop();
void push(E e);
}
/**
* 數(shù)組棧 時(shí)間復(fù)雜度O(1)
* @param <E>
*/
public class ArrayStack<E> implements Stack<E> {
private MyArray<E> array;
public ArrayStack(int capacity) {
array = new MyArray<>(capacity);
}
public ArrayStack(){
array = new MyArray<>();
}
@Override
public int getSize() {
return array.getSize();
}
@Override
public boolean isEmpty() {
return array.isEmpty();
}
/**
* 查看棧頂元素
* @return
*/
@Override
public E peek() {
return array.getLast();
}
/**
* 彈出棧頂元素便锨，出棧
* @return
*/
@Override
public E pop() {
return array.removeLast();
}
/**
* 入棧
* @param e
*/
@Override
public void push(E e) {
array.addLast(e);
}
/**
* 查看棧的容量
* @return
*/
public int capacity(){
return array.getCapacity();
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Stack :" );
builder.append("[");
for (int i = 0; i < array.getSize(); i++) {
builder.append(array.get(i));
if (i != array.getSize() - 1) {
builder.append(",");
}
}
builder.append("]top");
return builder.toString();
}
三.時(shí)間復(fù)雜度分析
??數(shù)組棧的出棧和入棧皆為O(1)操作，所以總體來(lái)說(shuō)數(shù)組棧是一個(gè)時(shí)間復(fù)雜度為O(1)的數(shù)據(jù)結(jié)構(gòu)我碟。
