Skip to content

Commit cd3a4dd

Browse files
shinezejianshinezejian
committed
栈的实现源码更新
1 parent ee7669f commit cd3a4dd

10 files changed

Lines changed: 441 additions & 0 deletions

File tree

‎src/com/zejian/structures/LinkedList/singleLinked/Node.java‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,10 @@ public class Node<T> {
88
public T data;
99
public Node<T> next;
1010

11+
public Node(){
12+
13+
}
14+
1115
public Node(T data){
1216
this.data=data;
1317
}

‎src/com/zejian/structures/LinkedList/singleLinked/SingleILinkedList.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,11 @@ public SingleILinkedList(Node<T> head) {
1414
this.head = head;
1515
}
1616

17+
18+
public SingleILinkedList() {
19+
20+
}
21+
1722
/**
1823
* 传入一个数组,转换成链表
1924
* @param array

‎src/com/zejian/structures/Stack/CheckExpression.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.zejian.structures.Stack;
2+
3+
/**
4+
* Created by zejian on 2016/11/27.
5+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
6+
* 表达式检测
7+
*/
8+
public class CheckExpression {
9+
10+
public static String isValid(String expstr)
11+
{
12+
//创建栈
13+
LinkedStack<String> stack = new LinkedStack<>();
14+
15+
int i=0;
16+
while(i<expstr.length())
17+
{
18+
char ch=expstr.charAt(i);
19+
i++;
20+
switch(ch)
21+
{
22+
case '(': stack.push(ch+"");//左括号直接入栈
23+
break;
24+
case ')': if (stack.isEmpty() || !stack.pop().equals("(")) //遇见右括号左括号直接出栈
25+
return "(";
26+
}
27+
}
28+
//最后检测是否为空,为空则检测通过
29+
if(stack.isEmpty())
30+
return "check pass!";
31+
else
32+
return "check exception!";
33+
}
34+
35+
public static void main(String args[])
36+
{
37+
String expstr="((5-3)*8-2)";
38+
System.out.println(expstr+" "+isValid(expstr));
39+
}
40+
}

‎src/com/zejian/structures/Stack/EmptyStackException.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package com.zejian.structures.Stack;
2+
3+
import java.io.Serializable;
4+
5+
/**
6+
* Created by zejian on 2016/11/27.
7+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
8+
* 自定义异常
9+
*/
10+
public class EmptyStackException extends RuntimeException implements Serializable{
11+
12+
13+
private static final long serialVersionUID = -8766038608920134747L;
14+
15+
16+
public EmptyStackException(){
17+
super();
18+
}
19+
20+
public EmptyStackException(String msg){
21+
super(msg);
22+
}
23+
}

‎src/com/zejian/structures/Stack/LinkedStack.java‎

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package com.zejian.structures.Stack;
2+
3+
import com.zejian.structures.LinkedList.singleLinked.Node;
4+
5+
import java.io.Serializable;
6+
7+
/**
8+
* Created by zejian on 2016/11/27.
9+
* Blog : http://blog.csdn.net/javazejian/article/details/53362993 [原文地址,请尊重原创]
10+
* 栈的链式实现
11+
*/
12+
public class LinkedStack<T> implements Stack<T> ,Serializable{
13+
14+
private static final long serialVersionUID = 1911829302658328353L;
15+
16+
private Node<T> top;
17+
18+
private int size;
19+
20+
public LinkedStack(){
21+
this.top=new Node<>();
22+
}
23+
24+
public int size(){
25+
return size;
26+
}
27+
28+
29+
@Override
30+
public boolean isEmpty() {
31+
return top==null || top.data==null;
32+
}
33+
34+
@Override
35+
public void push(T data) {
36+
if (data==null){
37+
throw new StackException("data can\'t be null");
38+
}
39+
if(this.top==null){
40+
this.top=new Node<>(data);
41+
}else if(this.top.data==null){
42+
this.top.data=data;
43+
}else {
44+
Node<T> p=new Node<>(data,this.top);
45+
top=p;//更新栈顶
46+
}
47+
size++;
48+
}
49+
50+
@Override
51+
public T peek() {
52+
if(isEmpty()){
53+
throw new EmptyStackException("Stack empty");
54+
}
55+
56+
return top.data;
57+
}
58+
59+
@Override
60+
public T pop() {
61+
if(isEmpty()){
62+
throw new EmptyStackException("Stack empty");
63+
}
64+
65+
T data=top.data;
66+
top=top.next;
67+
size--;
68+
return data;
69+
}
70+
71+
72+
public static void main(String[] args){
73+
LinkedStack<String> sl=new LinkedStack<>();
74+
sl.push("A");
75+
sl.push("B");
76+
sl.push("C");
77+
int length=sl.size();
78+
for (int i = 0; i < length; i++) {
79+
System.out.println("sl.pop->"+sl.pop());
80+
}
81+
}
82+
}

‎src/com/zejian/structures/Stack/LinkedStackBySingleLinkedList.java‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package com.zejian.structures.Stack;
2+
3+
import com.zejian.structures.LinkedList.singleLinked.SingleILinkedList;
4+
5+
import java.io.Serializable;
6+
7+
8+
/**
9+
* Created by zejian on 2016/11/27.
10+
* Blog : http://blog.csdn.net/javazejian/article/details/53362993 [原文地址,请尊重原创]
11+
* 链式栈的实现(利用单链表即可)
12+
*/
13+
public class LinkedStackBySingleLinkedList<T> implements Stack<T> ,Serializable {
14+
15+
private static final long serialVersionUID = 3409158027110650450L;
16+
17+
18+
private SingleILinkedList<T> linkedList;
19+
20+
public LinkedStackBySingleLinkedList(){
21+
linkedList=new SingleILinkedList<>();
22+
}
23+
24+
25+
@Override
26+
public boolean isEmpty() {
27+
return linkedList.isEmpty();
28+
}
29+
30+
/**
31+
* 栈顶插入(单链表尾部)
32+
* @param data
33+
*/
34+
@Override
35+
public void push(T data) {
36+
linkedList.add(data);
37+
}
38+
39+
/**
40+
* 获取元素,不删除
41+
* @return
42+
*/
43+
@Override
44+
public T peek() {
45+
if(isEmpty())
46+
throw new EmptyStackException("Stack empty");
47+
return linkedList.get(0);
48+
}
49+
50+
/**
51+
* 栈顶移除
52+
* @return
53+
*/
54+
@Override
55+
public T pop() {
56+
if(isEmpty())
57+
throw new EmptyStackException("Stack empty");
58+
return linkedList.remove(0);
59+
}
60+
}

‎src/com/zejian/structures/Stack/SeqStack.java‎

Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
package com.zejian.structures.Stack;
2+
3+
import java.io.Serializable;
4+
5+
/**
6+
* Created by zejian on 2016/11/27.
7+
* Blog : http://blog.csdn.net/javazejian/article/details/53362993 [原文地址,请尊重原创]
8+
* 顺序栈的实现
9+
*/
10+
public class SeqStack<T> implements Stack<T>,Serializable {
11+
12+
private static final long serialVersionUID = -5413303117698554397L;
13+
14+
/**
15+
* 栈顶指针,-1代表空栈
16+
*/
17+
private int top=-1;
18+
19+
/**
20+
* 容量大小默认为10
21+
*/
22+
private int capacity=10;
23+
24+
/**
25+
* 存放元素的数组
26+
*/
27+
private T[] array;
28+
29+
private int size;
30+
31+
public SeqStack(int capacity){
32+
array = (T[]) new Object[capacity];
33+
}
34+
35+
public SeqStack(){
36+
array= (T[]) new Object[this.capacity];
37+
}
38+
39+
public int size(){
40+
return size;
41+
}
42+
43+
44+
@Override
45+
public boolean isEmpty() {
46+
return this.top==-1;
47+
}
48+
49+
/**
50+
* 添加元素,从栈顶(数组尾部)插入
51+
* @param data
52+
*/
53+
@Override
54+
public void push(T data) {
55+
//判断容量是否充足
56+
if(array.length==size)
57+
ensureCapacity(size*2+1);//扩容
58+
59+
//从栈顶添加元素
60+
array[++top]=data;
61+
62+
size++;
63+
}
64+
65+
/**
66+
* 获取栈顶元素的值,不删除
67+
* @return
68+
*/
69+
@Override
70+
public T peek() {
71+
if(isEmpty())
72+
throw new EmptyStackException("Stack empty");
73+
return array[top];
74+
}
75+
76+
/**
77+
* 从栈顶(顺序表尾部)删除
78+
* @return
79+
*/
80+
@Override
81+
public T pop() {
82+
if(isEmpty())
83+
throw new EmptyStackException("Stack empty");
84+
size--;
85+
return array[top--];
86+
}
87+
88+
/**
89+
* 扩容的方法
90+
* @param capacity
91+
*/
92+
public void ensureCapacity(int capacity) {
93+
//如果需要拓展的容量比现在数组的容量还小,则无需扩容
94+
if (capacity<size)
95+
return;
96+
97+
T[] old = array;
98+
array = (T[]) new Object[capacity];
99+
//复制元素
100+
for (int i=0; i<size ; i++)
101+
array[i]=old[i];
102+
}
103+
104+
public static void main(String[] args){
105+
SeqStack<String> s=new SeqStack<>();
106+
s.push("A");
107+
s.push("B");
108+
s.push("C");
109+
System.out.println("size->"+s.size());
110+
int l=s.size();//size 在减少,必须先记录
111+
for (int i=0;i<l;i++){
112+
System.out.println("s.pop->"+s.pop());
113+
}
114+
115+
System.out.println("s.peek->"+s.peek());
116+
}
117+
}

‎src/com/zejian/structures/Stack/Stack.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package com.zejian.structures.Stack;
2+
3+
/**
4+
* Created by zejian on 2016/11/27.
5+
* Blog : http://blog.csdn.net/javazejian/article/details/53362993 [原文地址,请尊重原创]
6+
* 栈接口抽象数据类型
7+
*/
8+
public interface Stack<T> {
9+
10+
/**
11+
* 栈是否为空
12+
* @return
13+
*/
14+
boolean isEmpty();
15+
16+
/**
17+
* data元素入栈
18+
* @param data
19+
*/
20+
void push(T data);
21+
22+
/**
23+
* 返回栈顶元素,未出栈
24+
* @return
25+
*/
26+
T peek();
27+
28+
/**
29+
* 出栈,返回栈顶元素,同时从栈中移除该元素
30+
* @return
31+
*/
32+
T pop();
33+
34+
35+
}

0 commit comments

Comments
 (0)