自由的角马

# (堆)栈概述

``栈的定义和特点``

1清空(堆)栈

（2）判断是否为空

3）元素的个数

4）入

5

（6）取栈顶元素

## 接口

``````package stack;
/**
* (堆)栈
*
*/
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,栈空，此时出栈，则下溢（underflow)；

top=M,栈满，此时入栈，则上溢（overflow)；

## 源代码

``````package stack;
/**
* 顺序(堆)栈
*
*/
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() {
}

public String toString() {
String s = "[";
for(int i=Top-1; i>=0 ; i--) {
s = s + array[i];
s = s + ",  ";
}
s = s + "]";
return s;
}

}``````

# 链式(堆)栈

## 源代码

``````package stack;

/**
* 链式(堆)栈的结点
* @author luoweifu
*
*/
class Node{
Object data;	//数据元素
Node next;		//后驱结点
public Node() {
this(null);
}
public Node(Object data) {
this.data = data;
this.next = null;
}
}

/**
* 链式(堆)栈, 无头结点
*
*/
public class LinkStack implements Stack {
private Node top;	//栈顶指针
private int size;	//栈的大小

top = null;
size = 0;
}

@Override
public void clear() {
top = null;
size = 0;
}

@Override
public void push(Object obj) {
Node p = new Node(obj);
if(top == null) {
top = p;
} else {
p.next = top;
top = p;
}
size ++;
}

@Override
public Object pop() {
Node p = top;
top = top.next;
size --;
return p.data;
}

@Override
public boolean isEmpty() {
if(size == 0)
return true;
else
return false;
}

@Override
public int size() {
return size;
}

@Override
public Object peek() {
}

public String toString() {
StringBuilder sb = new StringBuilder("[");
Node p = top;
if(p == null) {
sb.append("");
} else {
do{
sb.append(p.data + ",  ");
}while((p = p.next) != null);
}
sb.append("]");
return sb.toString();
}
}``````

# 测试(堆)栈

``````package stack;

public class Test {
/**
* 测试堆栈
* @param args
*/
public static void main(String[] args) {
//Stack stack = new ArrayStack();
for(int i=0; i<10; i++) {
stack.push(i);
}
System.out.println(stack.toString());
Object a = stack.pop();
System.out.println(a + stack.toString());
stack.push(20);
Object b = stack.peek();
System.out.println( b + stack.toString());
stack.clear();
System.out.println( "数据数量：" + stack.size()
+ "  isEmpty? " + stack.isEmpty() + "  数据为：" + stack.toString());
}

}``````

## 结果

[9,  8,  7,  6,  5,  4,  3,  2,  1,  0,  ]
9[8,  7,  6,  5,  4,  3,  2,  1,  0,  ]
20[20,  8,  7,  6,  5,  4,  3,  2,  1,  0,  ]

### 自由的角马

C/C++程序内存分配整理二——堆和栈的区别

1、申请方式 stack: 由系统自动分配。 例如，声明在函数中一个局部变量int b; 系统自动在栈中为b开辟空间。 heap: 需要程序员自己申请，并指明大小，在C中malloc函数，C++中是new运算符。 如...

2013/09/09
0
0
C++用new来创建对象和非new来创建对象的区别

DannyCoder
2018/09/05
0
0
Stack vs. Heap：了解 Java 的内存分配机制

oschina
2017/08/14
2.9K
8

geek_loser
2016/07/04
36
0

AlphaJay
2010/06/12
0
0

GMTC2019|闲鱼-基于Flutter的架构演进与创新

27分钟前
2
0

近来,华为创始人任正非多次提及人工智能。即便在华为生死攸关的关键时刻,任正非依旧不忘强调教育的重要性,“如果不重视教育,实际上我们会重返贫穷的,因为这个社会,最终是要走向人工智能的...

29分钟前
0
0
iOS开发之EventKitUI框架的应用

iOS开发之EventKitUI框架的应用 前面博客，有介绍EventKit这个框架的使用，使用EventKit可以与系统的日历和提醒应用进行交互，读写用户的日程事件。EventKitUI，顾名思义，其实基于EventKit框...

37分钟前
0
0

37分钟前
0
0
WebService学习笔记

54分钟前
2
0