小强斋太

# 栈与队列（一）

## 一、栈

### 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;
}
}``````

### 小强斋太

2017/11/28
0
0

zhixin9001
2018/02/07
0
0
Java实现栈Stack_栈内部使用数组存储结构

Java实现栈Stack_栈内部使用数组存储结构 抽象数据类型栈的定义： 栈（stack），是限定在表尾进行插入或删除操作的线性表，因此对栈来说表尾有其特殊的含义，称为栈顶，相应的，表头端称为栈...

2014/09/14
0
0

2018/06/29
0
0

qq_19259415
2017/11/22
0
0

import javax.servlet.ServletException;import javax.servlet.annotation.WebServlet;import javax.servlet.http.Cookie;import javax.servlet.http.HttpServlet;import javax.serv......

gwl_

1
0

stars永恒

1
0

NotFound403

3
0
day22:

1、写一个getinterface.sh 脚本可以接受选项[i，I]，完成下面任务： 1）使用格式：getinterface.sh [-i interface | -I ip] 2）当用户使用-i选项时，显示指定网卡的IP地址；当用户使用-I选项...

2
0
Spring Cloud Alibaba基础教程：使用Nacos实现服务注册与发现

4
0