JAVA中堆栈是什么

堆栈是一种执行“后进先出”算法的数据结构。

设想有一个直径不大、一端开口一端封闭的竹筒。有若干个写有编号的小球，小球的直径比竹筒的直径略小。现在把不同编号的小球放到竹筒里面，可以发现一种规律：先放进去的小球只能后拿出来，反之，后放进去的小球能够先拿出来。所以“先进后出”就是这种结构的特点。

堆栈就是这样一种数据结构。它是在内存中开辟一个存储区域，数据一个一个顺序地存入(也就是“压入——push”)这个区域之中。有一个地址指针总指向最后一个压入堆栈的数据所在的数据单元，存放这个地址指针的寄存器就叫做堆栈指示器。开始放入数据的单元叫做“栈底”。数据一个一个地存入，这个过程叫做“压栈”。在压栈的过程中，每有一个数据压入堆栈，就放在和前一个单元相连的后面一个单元中，堆栈指示器中的地址自动加1。读取这些数据时，按照堆栈指示器中的地址读取数据，堆栈指示器中的地址数自动减 1。这个过程叫做“弹出pop”。如此就实现了后进先出的原则。

堆栈是计算机中最常用的一种数据结构，比如函数的调用在计算机中是用堆栈实现的。

堆栈可以用数组存储，也可以用以后会介绍的链表存储。

下面是一个堆栈的结构体定义，包括一个栈顶指针，一个数据项数组。栈顶指针最开始指向-1,然后存入数据时，栈顶指针加1，取出数据后，栈顶指针减1。

#define MAX_SIZE 100

typedef int DATA_TYPE;

struct stack

{

DATA_TYPE data[MAX_SIZE];

int top;

};

数组实现的堆栈：ArrayStack.java

public class ArrayStack {

Object[] m_elements;

int m_size;

public ArrayStack(int len) {

m_elements = new Object[len];

m_size = 0;

}

public ArrayStack() {

this(50);

}

// insert onto stack

public void push(Object element) {

m_elements[m_size] = element;

m_size++;

}

// return and remove the top element

public Object pop() {

if (!this.isEmpty()) {

Object obj = m_elements[m_size - 1];

m_elements[m_size - 1] = null;

m_size--;

return obj;

} else {

return null;

}

}

// return the top element

public Object top() {

if (!this.isEmpty()) {

return m_elements[m_size - 1];

} else {

return null;

}

}

// return 1 --> is empty

// return 0 --> is not empty我爱编程网

public boolean isEmpty() {

return this.size() == 0;

}

public int size() {

return m_size;

}

}

使用链表实现(单链表) ：

public class Stacklist {

Node m_header;

int m_size;

public ListStack() {

m_header = null;

m_size = 0;

}

public void push(Object value) {

m_header = new Node(value, m_header);

}

public Object pop() {

if (!this.isEmpty()) {

throw new RuntimeException("Stack underflow");

}

Object obj = m_header.element;

m_header = m_header.next;

return obj;

}

// return reference to most recently added elemenet

public Object peek() {

if (!this.isEmpty()) {

throw new RuntimeException("Stack underflow");

}

return m_header.element;

}

public boolean isEmpty() {

return this.size() == 0;

}

//return the number of the queue's elements;

public int size() {

return m_size;

}

}

链表的需要用到一个结点类 Node.java 代码如下

public class Node {

Object element;

Node next;

public Node(Object theElement) {

this(theElement, null);

}

public Node(Object theElement, Node n) {

element = theElement;

next = n;

}

public Object getElement() {

return element;

}

public void setElement(Object element) {

this.element = element;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

}

/** 堆栈 */

class Stack {

private String name;

private String[] buffer=new String[100];

int point=-1;

public Stack(String name){this.name=name;}

public String getName(){return name;}

public synchronized int getPoint(){return point;}

public synchronized String pop() {

this.notifyAll();

while(point==-1){

System.out.println(Thread.currentThread().getName()+": wait");

try{

this.wait();

}catch(InterruptedException e){throw new RuntimeException(e);}

}

String goods = buffer[point];

buffer[point]=null;

Thread.yield();

point--;

return goods;

}

public synchronized void push(String goods) {

this.notifyAll();

while(point==buffer.length-1){

System.out.println(Thread.currentThread().getName()+": wait");

try{

this.wait();

}catch(InterruptedException e){throw new RuntimeException(e);}

}

point++;

Thread.yield();

buffer[point]=goods;

}

}