Java栈的两种实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.Arrays;
/*
* 用数组来实现一个栈
* 栈：后进先出
* 主要有push pop peek isEmpty
* peek 负责获取栈顶元素 在数组的实现中 peek负责获取最新存放在数组中的元素 stack[size-1]
* 这样在pop取出元素的时候直接获取peek()的值就好
* push往数组中存放元素的时候 直接将size+1 并且将这个元素放在stack[size++]的位置
* 最后要注意数组的容量 在向数组中放元素的时候不要超过初始化的定义
*/
public class Stack<E> {
int size;//数组中存储元素的个数
private Object[] stack;
public Stack(){
stack=new Object[10];
}
public Boolean isEmpty(){
return size==0;
}
@SuppressWarnings("unchecked")
public E peek(){
if(isEmpty()){
return null;
}
return (E) stack[size-1];
}
public E push(E item){
stack[size++]=item;
return item;
}
public E pop(){
ensureCapacity(size+1);//往数组中添加元素的时候 先进行容量检测 如果已经放满了 那么就再+10个容量
E e= peek();
stack[size-1]=null;
size--;
return e;
}
public void ensureCapacity(int size){
int len =stack.length;
if (len>size){
int newLen=10;
stack=Arrays.copyOf(stack,newLen);
}
}
public static void main(String[] args){
Stack<Integer> s=new Stack<>();
s.push(56);
s.push(6785);
s.push(342);
System.out.println(s.size);
System.out.println("栈顶元素为"+s.pop());// 打印 342
System.out.println("栈顶元素为"+s.pop());//打印 6785
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
* 用链表来实现栈
*/
class
Node<E>{
Node<E>next=null;
E data;
public Node(E data){this.data=data;}
}
public class LinkedStack<E> {
Node<E>top=null;
//头结点设置为空
public boolean isEmpty(){
return top==null;
}
/*
* push时候相当于new一个头结点 让新的结点指向单链表的头结点
* 以新结点作为单链表的头结点即可
*/
public void push(E data){
Node<E>newNode=new Node<E>(data);
newNode.next=top;//将现在栈顶的元素的值放在第二个
top=newNode;
//新的栈顶元素的值放在top中
}
/*
* pop时候将链表的头结点指向next 将next作为新的头结点即可
*/
public E pop(){
if(this.isEmpty()){
return null;
}
E data= top.data;
top=top.next;
return data;
}
public E peek(){
if(this.isEmpty()){
return null;
}
E data=top.data;
return data;
}//peek和pop的思路很相似 都是返回top元素 在pop完元素之后还需要将下一个top指针指到top上
public static void main(String [] args){
LinkedStack<Integer> stack=new LinkedStack<>();
stack.push(22);
stack.push(23);
stack.push(24);
stack.pop();
System.out.print(stack.peek());//输出：
23
}
}