A. java 基础堆栈
你就简单的来理解就可以了
堆栈就是两种存放数据的方式
不要new直接来定义的是栈
用new来定义的就是堆
首先来讲解栈
栈的优势是，存取速度比堆要快。但缺点是缺乏灵活性
而堆测试速度慢
但是灵活性好
比如八大基本数据类型
在你int
sum
=
0;的时候
就是sum是一个指向
int
类型的引用，指向0这个字面值
你在顶一个
int
i=0;他会去找有没有0
有的话就会指向它
所以栈具有共享数据的特性
而当你String
str
=
new
String("a");的时候
它就会在堆中建立一个对象
其实你就理解成两种方式的存放数据的方式就行
B. 用java编写出来：用数组实现一个栈
public class Stack {
private Object[] stack;
//这个不需要;
//private int top = 0; //初始化栈顶
//这个也不需要;
//写一个栈出来,最好是可以动态的,可以自己改变大小的,即数组的长度;
//private int size = 0; // 初始化大小
//元素个数;
private int size;
//默认长度为10;
public Stack(){
this(10);
}
//也可以自己设置长度,即容量;
public Stack(int len){
stack = new Object[len];
}
//返回元素个数;
public int size(){
return size;
}
//返回数组长度,即容量;
public int capacity(){
return stack.length;
}
//实现动态的数组;
public void ensureCapacity(){
if(size() == capacity()){
Object[] newStack = new Object[size() * 3 / 2 + 1];
System.array(stack, 0, newStack, 0, size());
stack = newStack;
}
}
//入栈;
public void push(Object o){
size++;
ensureCapacity();
stack[size - 1] = o;
}
/*
public void push(Object object) {
if (isFull()) {
System.out.println("栈满! 入栈失败");
}
stack[top++] = object;
}
*/
//判空;
public boolean isEmpty(){
return size == 0;
}
//出栈;
public Object pop(){
//首先要判空;
if(isEmpty()){
throw new ("不能为空");
}
Object o = stack[--size];
stack[size] = null;
return o;
}
/*
// 出栈
public Object pop() {
Object object = stack[--top];
stack[top] = null;
return object;
}
*/
/*
// 计算栈当前大小
public int size() {
return top;
}
// 判断是否是空栈
public boolean isEmpey() {
return top == 0;
}
// 判断是否栈满
public boolean isFull() {
return top >= size;
}
public Stack(int size) {
this.size = size;
}
*/
public static void main(String[] args) {
Stack stack = new Stack(3);
String[] data = new String[] { "a", "b", "c" };
for (int i = 0; i < data.length; i++) {
stack.push(data[i]);
System.out.println(data[i] + "");
}
System.out.println("***********");
while (!stack.isEmpty()) {
System.out.println(stack.pop() + "");
}
//}
}
}
你自己对比一下,我是在你的里面修改的
C. Java编程思想里的泛型实现一个堆栈类 分享
觉得作者写得太好了，不得不收藏一下。
对这个例子的理解：
//类型参数不能用基本类型，T和U其实是同一类型。
//每次放新数据都成为新的top，把原来的top往下压一级，通过指针建立链接。
//末端哨兵既是默认构造器创建出的符合end()返回true的节点。
复制代码
代码如下:
//:
generics/LinkedStack.java
//
A
stack
implemented
with
an
internal
linked
structure.
package
generics;
public
class
LinkedStack<T>
{
private
static
class
Node<U>
{
U
item;
Node<U>
next;
Node()
{
item
=
null;
next
=
null;
}
Node(U
item,
Node<U>
next)
{
this.item
=
item;
this.next
=
next;
}
boolean
end()
{
return
item
==
null
&&
next
==
null;
}
}
private
Node<T>
top
=
new
Node<T>();
//
End
sentinel
public
void
push(T
item)
{
top
=
new
Node<T>(item,
top);
}
public
T
pop()
{
T
result
=
top.item;
if(!top.end())
top
=
top.next;
return
result;
}
public
static
void
main(String[]
args)
{
LinkedStack<String>
lss
=
new
LinkedStack<String>();
for(String
s
:
"Phasers
on
stun!".split("
"))
lss.push(s);
String
ss;
while((ss
=
lss.pop())
!=
null)
System.out.println(ss);
//-----
if
put
integer
into
the
LinkedList
LinkedStack<Integer>
lii
=
new
LinkedStack<Integer>();
for(Integer
i
=
0;
i
<
10;
i++){
lii.push(i);
}
Integer
end;
while((end
=
lii.pop())
!=
null)
System.out.println(end);
//-----
integer
test
end!
}
}
/*
Output:
stun!
on
Phasers
*/
D. java语言中用LinkList实现堆栈
栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。
LinkedList数据结构是一种双向的链式结构，每一个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素，和数组的顺序存储结构（如：ArrayList）相比，插入和删除比较方便，但速度会慢一些。
栈的定义
栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。
实现代码：
package com.weisou.dataStruct;
import java.util.LinkedList;
@SuppressWarnings("unchecked")
public class MyStack {
LinkedList linkList = new LinkedList<Object>();
public void push(Object object) {
linkList.addFirst(object);
}
public boolean isEmpty() {
return linkList.isEmpty();
}
public void clear() {
linkList.clear();
}
// 移除并返回此列表的第一个元素
public Object pop() {
if (!linkList.isEmpty())
return linkList.removeFirst();
return "栈内无元素";
}
public int getSize() {
return linkList.size();
}
public static void main(String[] args) {
MyStack myStack = new MyStack();
myStack.push(2);
myStack.push(3);
myStack.push(4);
System.out.println(myStack.pop());
System.out.println(myStack.pop());
}
}
队列定义
队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表
（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
实现代码：
package com.weisou.dataStruct;
import java.util.LinkedList;
/**
*
* @author gf
* @date 2009-11-13
*/
public class MyQueue {
LinkedList linkedList = new LinkedList();
//队尾插
public void put(Object o){
linkedList.addLast(o);
//队头取 取完并删除
public Object get(){
if(!linkedList.isEmpty())
return linkedList.removeFirst();
else
return "";
}
public boolean isEmpty(){
return linkedList.isEmpty();
}
public int size(){
return linkedList.size();
}
public void clear(){
linkedList.clear();
}
/**
* @param args
*/
public static void main(String[] args) {
MyQueue myQueue= new MyQueue();
myQueue.put(1);
myQueue.put(2);
myQueue.put(3);
System.out.println(myQueue.get());
}
}
E. Java队列入队和堆栈出栈算法实现
class LinkedList //定义双项链表{char data;LinkedList back;LinkedList forward;}interface Access //定义从队列和栈存取操作的接口{void put(char c);char get();}class Queue implements Access //定义队列类{private LinkedList QHead=new LinkedList();private LinkedList QRear=QHead; //初始化队头和队尾public void put(char c) //实现向队列存数的方法{QRear.forward=new LinkedList();QRear.forward.data=c;QRear.forward.back=QRear;QRear=QRear.forward;}public char get() //实现从队列取数的方法{if(QHead!=QRear) //如果队列不为空则取数{QHead.forward.back=null;QHead=QHead.forward;return QHead.data;}else{System.out.println("The queue is empty! ");return '\0';}}}class Stack implements Access //定义栈类{private LinkedList bottom=new LinkedList();private LinkedList top=bottom; //初始化栈顶与斩底public void put(char c) //实现从栈中存数的方法{top.forward=new LinkedList();top.forward.data=c;top.forward.back=top;top=top.forward;}public char get() //实现从栈中取数的方法{if(top!=bottom) //如果栈不为空则取数{char ch=top.data;top.back.forward=null;top=top.back;return ch;}else{System.out.println("The stack is empty! ");return '\0';}}}public class StackQueue{public static void main(String[] args){char ch;Queue q=new Queue(); //创建一个队列qStack s=new Stack(); //创建一个栈sq.put('x');q.put('y');q.put('z'); //向队列q存入3个字符s.put('x');s.put('y');s.put('z'); //向栈s存入3个字符System.out.println("Queue: ");if((ch=q.get())!='\0')System.out.println(ch);if((ch=q.get())!='\0')System.out.println(ch);if((ch=q.get())!='\0')System.out.println(ch);if((ch=q.get())!='\0')System.out.println(ch);//从队列q中取数并显示System.out.println("Stack: ");if((ch=s.get())!='\0')System.out.println(ch);if((ch=s.get())!='\0')System.out.println(ch);if((ch=s.get())!='\0')System.out.println(ch);if((ch=s.get())!='\0')System.out.println(ch);//从栈s中取数并显示}}引自： http://wenwen.soso.com/z/q104863.htm?ch=w.xg.ll
F. 用一维整数数组实现数据结构中的堆栈(Stack)。（用java语言）
public class IntStack {
private int[] stack;
private int top;
/**
*初始化栈，传入一个非负的整数，否则抛出一个错误
*/
public IntStack(int size) throws StackErrorException{
if(size<0){
throw new StackErrorException("错误的大小");
}
init(size);
}
private void init(int size) {
stack = new int[size];
top = 0;
}
/**
*判断栈是否为空，true则为空，反之则反
*/
public boolean isEmpty(){
return top==0;
}
/**
*判断栈是否已满，true则已满，反之则反
*/
public boolean isFull(){
return top==stack.length;
}
/**
*向栈顶添加元素，满则抛出异常
*/
public void push(int value) throws StackErrorException{
if(isFull()){
throw new StackErrorException("栈已满");
}
stack[top++] = value;
}
/**
*移除栈顶元素并返回，空则抛出异常
*/
public int pop() throws StackErrorException{
if(isEmpty()){
throw new StackErrorException("已到栈底!");
}
return stack[--top];
}
/**
*返回栈顶元素，空则抛出异常
*/
public int peek() throws StackErrorException{
if(isEmpty()){
throw new StackErrorException("已在栈底!");
}
return stack[top-1];
}
/**
*返回栈大小
*/
public int size(){
return stack.length;
}
class StackErrorException extends Exception{
public StackErrorException(String msg) {
super(msg);
}
}
}