2.2 顺序栈和链栈的实现（Java）
首先定义栈的ADT（抽象数据类型），定义如下：
public interface StackADT<E> {
public void clear();//清空栈中所有元素
public void push(E it);//压栈
public E pop();//出栈
public E topValue();//返回栈顶元素
public boolean isEmpty();//判断栈是否空
public void print();//打印栈中的所有元素
}
2.2.1 顺序栈的实现
顺序栈的实现有两种，一种是将数组的第0个位置作为栈顶，此时的插入和删除操作的时间代价都为O（n）；另一种是将有n个元素的数组的n-1个位置作为栈顶，插入和删除都是在表尾进行操作，此时的时间复杂度为O(1)。图示如下，显然第二种方式较好。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
具体的实现代码如下：
public class AStack<E> implements StackADT<E> {
//构造顺序栈
private final int DEFAULT_SIZE = 10;
private int size;//栈最多能容纳的元素个数
private int top;//可插入位置的下标
private E[] listArray;//存储栈中元素的数组
//初始化
private void setUp(int size) {
this.size = size;
top = 0;
listArray = (E[]) new Object[size];
}
//构造器
public AStack() {
setUp(DEFAULT_SIZE);
}
public AStack(int size) {
setUp(size);
}
@Override
public void clear() {
top = 0;
}
@Override
public void push(E it) {
if (top >= size) {
System.out.println("stack overflow");
return;
}
listArray[top++] = it;
}
@Override
public E pop() {
if (isEmpty()){return null;}
return listArray[--top];//top-1才是存储最顶元素的位置
}
@Override
public E topValue() {
if (isEmpty()){return null;}
return listArray[top-1];
}
@Override
public boolean isEmpty() {
return top==0;
}
@Override
public void print() {
if (isEmpty()){
System.out.println("empty");
}
for (int i=top-1;i>=0;i--){
System.out.println(listArray[i]);
}
}
}
在以上代码中，top定义为栈中的第一个空闲位置，push和pop都是在top指示的位置进行插入和删除。push操作先将元素插入到top所在位置，然后对top加一；pop首先将top减一，top-1下标所在的元素才是真正的栈顶元素，然后删除栈顶元素。
top同样可以定义为栈中最上面元素的值，这样的话top需要初始化为-1.
测试代码如下
public class AStackTest {
public static void main(String[] args) {
AStack<Integer> myAStack=new AStack<>();
myAStack.push(1);
myAStack.push(2);
myAStack.push(3);
myAStack.push(4);
myAStack.push(5);
System.out.println("after pushing, the stack is: ");
myAStack.print();
System.out.print("top value: ");
System.out.println(myAStack.topValue());
System.out.println("after popping two elements: ");
myAStack.pop();
myAStack.pop();
myAStack.print();
System.out.print("top value: ");
System.out.println(myAStack.topValue());
}
}
测试结果如下
after pushing, the stack is:
5
4
3
2
1
top value: 5
after popping two elements:
3
2
1
top value: 3
2.2.2 链栈的实现
链栈的实现比链表的实现简单得多，唯一一个数据成员就是top，它是一个指向链式栈第一个结点（栈顶）的指针
为方便阅读，Link类的定义如下：
public class Link <E> {
//结点类
private E element;
private Link next; //指向的下一个结点
//构造方法
public Link(E element, Link next) {
this.element = element;
this.next = next;
}
public Link(Link next) {
this.next = next;
}
//getter和setter
public E getElement() {
return element;
}
public void setElement(E element) {
this.element = element;
}
public Link getNext() {
return next;
}
public void setNext(Link next) {
this.next = next;
}
}
LStack的实现代码如下：
public class LStack<E> implements StackADT<E> {
private Link<E> top;//栈顶元素
//初始化与构造器
private void setUp() {
top = null;
}
public LStack() {
setUp();
}
public LStack(int size) {
setUp();
}
@Override
public void clear() {
top = null;
}
@Override
public void push(E it) {
top = new Link<E>(it, top);
}
@Override
public E pop() {
if (isEmpty()) {
System.out.println("stack is empty");
return null;
}
E it = top.getElement();
top = top.getNext();
return it;
}
@Override
public E topValue() {
if (isEmpty()) {
System.out.println("no top value");
return null;
}
return top.getElement();
}
@Override
public boolean isEmpty() {
return top == null;
}
@Override
public void print() {
if (isEmpty()) {
System.out.println("empty");
return;
}
Link<E> temp = top;
while (temp != null) {
System.out.println(temp.getElement());
temp = temp.getNext();
}
}
}