-
简介
给线性表的操作加上限定,只能从末尾删除(出栈),添加(入栈)。这种特殊的线性表就叫做栈(stack)又称后进后出(LILO:Last In Last Out)线性表。
栈的逻辑结构如下图所示:
栈的逻辑结构
-
栈的API
public interface Stack<E> {
/**
* 获取栈顶元素
* @return 栈为空返回null,否则返回栈顶元素
*/
E getTop();
/**
* 入栈操作,将元素放入栈顶
* @param item 放入元素
*/
void push(E item);
/**
* 出栈操作
* @return 栈为空返回null,否则返回栈顶元素
*/
E pop();
/**
* 销毁栈
*/
void destroy();
/**
* 判断栈是否为空
* @return true<br/>栈不为空<br/>false<br/>栈为空
*/
boolean isEmpty();
/**
* 返回栈的元素数量
* @return 栈的元素数量
*/
int length();
}
-
伪代码
节点
class node
elem;
prev;
出栈操作伪代码,rear尾节点,head头结点
pop()
node save = rear;
save = rear;
rear = rear.prev;
save.prev = null;
入栈操作伪代码,rear尾节点,head头节点
push(elem)
node push = new node;
node.elem = elem;
node.prev = rear;
prev = node;
-
Java代码描述
public class StackImpl<E> implements Stack<E> {
private Node<E> head;
private Node<E> rear;
private int size;
private class Node<E> {
E elem;
Node<E> prev;
}
StackImpl() {
head = rear = new Node<>();
}
@Override
public E getTop() {
if (head == rear) {
return null;
}
return rear.elem;
}
@Override
public void push(E item) {
if (item == null) {
return;
}
Node<E> push = new Node<>();
push.elem = item;
push.prev = rear;
rear = push;
size++;
}
@Override
public E pop() {
if (size == 0) {
return null;
}
//保存尾节点
Node<E> pop = rear;
//尾节点指向上一个节点
rear = rear.prev;
//断开上一个尾节点的连接
pop.prev = null;
size--;
return pop.elem;
}
@Override
public void destroy() {
head = rear = new Node<>();
size = 0;
//help GC
rear.prev = null;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int length() {
return size;
}
}
