(堆)栈
(堆)栈概述
栈是一种特殊的线性表,是操作受限的线性表
栈的定义和特点
•定义:限定仅在表尾进行插入或删除操作的线性表,表尾—栈顶,表头—栈底,不含元素的空表称空栈
•特点:先进后出(FILO)或后进先出(LIFO)
栈的结构
如下图所示:
线性表的操作主要包括:
(1)清空(堆)栈
(2)判断是否为空
(3)元素的个数
(4)入栈
(5)出栈
(6)取栈顶元素
接口
由此,对队列的抽象数据类型定义Queue接口如下:
[java]
package stack;
/**
* (堆)栈
* @author Administrator
*
*/
public interface Stack {
/**
* 清空堆栈
*/
public void clear();
/**
* 入栈
* @param obj 入栈的元素
*/
public void push(Object obj);
/**
* 出栈
* @return 出栈的结果
*/
public Object pop();
/**
* 判断是否为空
* @return
*/
public boolean isEmpty();
/**
* 求元素的个数
* @return 元素的个数
*/
public int size();
/**
* 取栈顶元素
* @return 栈顶元素
*/
public Object peek();
}
顺序(堆)栈
结构模型
栈顶指针top,指向实际栈顶后的空位置,初值为0。
栈的初始空间大小为M
top=0,栈空,此时出栈,则下溢(underflow);
top=M,栈满,此时入栈,则上溢(overflow);
源代码
[java]
package stack;
/**
* 顺序(堆)栈
* @author Administrator
*
*/
public class ArrayStack implements Stack{
private static int DEFAULT_SIZE = 100;
private int Top;
Object array[];
public ArrayStack() {
Top = 0;
array = new Object[DEFAULT_SIZE];
}
public boolean isEmpty() {
return 0 == Top ;
}
public void expand() {
Object[] newArray = new Object[2 * array.length];
for(int i=0; i<array.length; i++) {
newArray[i] = array[i];
}
array = newArray;
}
/*
public void expand() {
try {
Object[] newArray = new Object[2*DEFAULT_SIZE];
for(int i=0; i<array.length; i++) {
newArray[i] = array[i];
}
array = newArray;
}catch(OutOfMemoryError e) {
System.out.println("error in expand of Stack class!");
//e.printStackTrace();
}
DEFAULT_SIZE = 2*DEFAULT_SIZE;
}
*/
public void push(Object obj) {
if(Top == array.length) {
expand();
}
array[Top] =obj;
Top ++;
}
public Object pop() {
if(0 == Top) throw new IllegalStateException();
Object val = array[-- Top];
array[Top] = null;
return val;
}
public void clear() {
for(int i=0; i<array.length; i++) {
array[i] = null;
Top = 0;
}
}
public Object peek() {
if(0 == Top) throw new IllegalStateException();
return array[Top - 1];
}
public int size() {
return Top;
}
public String toString() {
String s = "[";
for(int i=Top-1; i>=0 ; i--) {
s = s + array[i];
s = s + ", ";
}
s = s + "]";
return s;
}
}
链式(堆)栈
结构模型
源代码
补充:软件开发 , Java ,