• 发表于 1年前
• 阅读 3
• 收藏 0
• 评论 0

# 栈与队列（一）

## 一、栈

### 1.1栈的定义和抽象数据类型

Stack接口

``````package stack;

//Stack 接口
public interface Stack {
// 返回堆栈的大小
public int getSize();

// 判断堆栈是否为空
public boolean isEmpty();

// 数据元素e 入栈
public void push(Object e);

// 栈顶元素出栈
public Object pop() throws StackEmptyException;

// 取栈顶元素
public Object peek() throws StackEmptyException;
}``````

StackEmptyException堆栈为空时出栈或取栈顶元素抛出此异常

``````package stack;

//StackEmptyException 堆栈为空时出栈或取栈顶元素抛出此异常
public class StackEmptyException extends RuntimeException {
public StackEmptyException(String err) {
super(err);
}
}``````

### 1.2 栈的顺序存储实现

``````package stack;

public class StackArray implements Stack {
private final int LEN = 8; // 数组的默认大小
private Object[] elements; // 数据元素数组
private int top; // 栈顶指针

public StackArray() {
top = -1;
elements = new Object[LEN];
}

// 返回堆栈的大小
public int getSize() {
}

// 判断堆栈是否为空
public boolean isEmpty() {
}

// 数据元素e 入栈
public void push(Object e) {
if (getSize() >= elements.length)
expandSpace();
elements[++top] = e;
}

private void expandSpace() {
Object[] a = new Object[elements.length * 2];
for (int i = 0; i < elements.length; i++)
a[i] = elements[i];
elements = a;
}

// 栈顶元素出栈
public Object pop() throws StackEmptyException {
if (getSize() < 1)
throw new StackEmptyException("错误，堆栈为空。");
Object obj = elements[top];
elements[top--] = null;
return obj;
}

// 取栈顶元素
public Object peek() throws StackEmptyException {
if (getSize() < 1)
throw new StackEmptyException("错误，堆栈为空。");
return elements[top];
}
}``````

### 1.3 栈的链式存储实现

``````package stack;

//Stack 的链式存储实现
public class StackSLinked implements Stack {
private SLNode top; // 链表首结点引用
private int size; // 栈的大小

top = null;
size = 0;
}

// 返回堆栈的大小
public int getSize() {
return size;
}

// 判断堆栈是否为空
public boolean isEmpty() {
return size == 0;
}

// 数据元素e 入栈
public void push(Object e) {
SLNode q = new SLNode(e, top);
top = q;
size++;
}

// 栈顶元素出栈
public Object pop() throws StackEmptyException {
if (size < 1)
throw new StackEmptyException("错误，堆栈为空。");
Object obj = top.getData();
top = top.getNext();
size--;
return obj;
}

// 取栈顶元素
public Object peek() throws StackEmptyException {
if (size < 1)
throw new StackEmptyException("错误，堆栈为空。");
}
}``````

``````package stack;

public class SLNode {
private Object element;
private SLNode next;

public SLNode() {
this(null, null);
}

public SLNode(Object ele, SLNode next) {
this.element = ele;
this.next = next;
}

public SLNode getNext() {
return next;
}

public void setNext(SLNode next) {
this.next = next;
}

/**************** Methods of Node Interface **************/
public Object getData() {

return element;
}

public void setData(Object obj) {
element = obj;
}
}``````

×