数据结构学习----顺序栈(Java实现)

时间:2022-04-16 12:38:57

栈抽象数据结构 栈接口, 描述栈抽象数据类型,泛型参数T表示数据元素的数据类型:

package com.clarck.datastructure.stack;

/**
* 栈抽象数据结构 栈接口, 描述栈抽象数据类型,泛型参数T表示数据元素的数据类型
*
* @author clarck
*
* @param <T>
*/
public interface SStack<T> {
/**
* 判断栈是否为空
*
* @return
*/
boolean isEmpty();

/**
* 元素x入栈
*
* @param x
*/
void push(T x);

/**
* 出栈,返回栈顶元素
*
* @return
*/
T pop();

/**
* 取栈顶元素, 未出栈
*
* @return
*/
T get();
}
顺序栈:

package com.clarck.datastructure.stack;

/**
* 顺序栈
*
* @author clarck
*
* @param <T>
*/
public class SeqStack<T> implements SStack<T> {
/**
* 存储栈数据元素的数组
*/
private Object element[];

/**
* 栈顶元素下标
*/
private int top;

/**
* 构造容量为size的空栈
*/
public SeqStack(int size) {
this.element = new Object[Math.abs(size)];
this.top = -1;
}

/**
* 构造默认容量的空栈
*/
public SeqStack() {
this(64);
}

/**
* 判断栈是否空,若空返回true
*/
@Override
public boolean isEmpty() {
return this.top == -1;
}

/**
* 元素x入栈,空对象不能入栈
*/
@Override
public void push(T x) {
if (x == null)
return;

// 若栈满,则扩充栈容量
if (this.top == element.length - 1) {
Object[] temp = this.element;
// 重新申请一个容量更大的数组
this.element = new Object[temp.length * 2];
// 复制数组元素,O(n)
for (int i = 0; i < temp.length; i++) {
this.element[i] = temp[i];
}
}
this.top++;
this.element[this.top] = x;
}

/**
* 出栈,返回栈顶元素,若栈空返回null
*/
@SuppressWarnings("unchecked")
@Override
public T pop() {
return this.top == -1 ? null : (T) this.element[this.top--];
}

/**
* 取栈顶元素,未出栈,若栈空返回null
*/
@SuppressWarnings("unchecked")
@Override
public T get() {
return this.top == -1 ? null : (T) this.element[this.top];
}

/**
* 返回栈所有元素的描述字符串,形式为“(,)”,算法同顺序表
*/
@Override
public String toString() {
String str = "(";
if (this.top != -1)
str += this.element[this.top].toString();
for (int i = this.top - 1; i >= 0; i--) {
str += ", " + this.element[i].toString();
}
return str + ") ";
}

}
顺序栈的测试类:

package com.clarck.datastructure.stack;

/**
* 栈的测试类
*
* @author clarck
*
*/
public class Stack_test {
public static void main(String args[]) {
SeqStack<String> stack = new SeqStack<String>(20);
System.out.print("Push: ");
char ch = 'a';
for (int i = 0; i < 5; i++) {
String str = (char) (ch + i) + "";
stack.push(str);
System.out.print(str + " ");
}
System.out.println(stack.toString());
}

}

测试结果如下:

Push: a b c d e (e, d, c, b, a)