0
0
0
1. 云栖社区>
2. 博客>
3. 正文

## 栈的数组实现和链式实现

```1，堆栈ADT

package Stack;

public void push(Object element);//压栈

public Object pop();//出栈

public boolean isEmpty();

public int size();

public Object peek();//返回栈顶对象的一个引用

public String toString();
}

2，链式实现

private LinearNode top; //指向栈顶
private int count;//标记栈的大小

top--->元素1--->元素2--->元素3.........

package Stack;

import Bag.LinearNode;

//为了重点来实现算法，将异常情况直接打印出然后退出程序，不再声明异常类

private LinearNode top; //指向栈顶
private int count;//标记栈的大小

public static void main(String[] args){

System.out.println("将0到10依次压栈");
for(int i = 0;i < 10;i++)
stack.push(i);
System.out.println("连续执行5次出栈操作");
for(int i = 0;i < 5;i++)
stack.pop();

System.out.println("栈为空吗？： " + stack.isEmpty());
System.out.println("栈的大小为： " + stack.size());
System.out.println("栈顶元素为： " + stack.top.getElement());
System.out.println("栈顶元素为： " + stack.peek());
}

{
top = null;
count = 0;
}

public int size() {
return count;
}

public boolean isEmpty() {
return (size() == 0);
}

public void push(Object element) {
LinearNode node = new LinearNode(element);
node.setNext(top);
top = node;
count++;
}

public Object pop() {
if(isEmpty())
{
System.out.println("stack is empty!");
System.exit(1);
}
Object result = top.getElement();
top = top.getNext();
count--;

return result;
}

public Object peek() {

Object result =  top.getElement();
return result;
}

}

3，数组实现

private Object[] contents;
private int top;//top标记下一个入栈的位置，同时也表示栈的容量大小，跟链式实现的count比较一下！！！

package Stack;

public class ArrayStack implements StackADT {

private Object[] contents;
private int top;//top标记下一个入栈的位置，同时也表示栈的容量大小，跟链式实现的count比较一下！！！

private static int SIZE = 10;

public ArrayStack()
{
contents = new Object[SIZE];
top = 0;
}

public void expand(){//借助于申请一个辅助空间,每次扩展容量一倍
Object[] larger = new Object[size()*2];
for(int index = 0;index < top;index++)
larger[index] =  contents[index];

contents = larger;
}

public int size() {
}

public boolean isEmpty() {
return (size() == 0);
}

public void push(Object element) {
//if(isEmpty())
//expand();
if(top == contents.length)
expand();
contents[top] = element;
top++;
}

public Object pop() {
if(isEmpty())
{
System.out.println("stack is empty!");
System.exit(1);
}

Object result = contents[top-1];
contents[top-1] = null;//出栈
top--;

return result;

/*书上这样写简便一点：：：
* top--;
* Object result = contents[top];
* contents[top] = null;*/
}

public Object peek() {
Object result;
if(isEmpty())
result = null;
else
result = contents[top-1];
return result;
}

public static void main(String[] args) {
ArrayStack stack = new ArrayStack();
System.out.println("将0到24依次压栈，然后连续10次出栈");
for(int i = 0;i < 25;i++)
stack.push(i);
for(int i = 0;i < 10;i++)
stack.pop();
System.out.println("栈的大小为： " + stack.size());
System.out.println("栈为空吗？： " + stack.isEmpty());
System.out.println("栈顶元素为： " + stack.peek());
}

}

+ 关注