java数据结构- - - -栈
2021-05-18 09:30
标签：maxsize [] des this 数组 inter gen while for 栈：是一种容器，类似于桶一样，栈是一种特殊的线性表，不同于一般线性表的是，一般线性表可以在表内任意位置添加和删除元素， 而栈只可以在尾端进行，栈尾一般称之为栈顶，另一端称之为栈底，特点是：后进先出/先进后出。 而一般常见使用的有 顺序栈 和 链栈；顺序栈类似于数组一样，而链栈就是用链表实现的，链栈的结点特点需要有指针域和数值域。 这里首先放上顺序栈常见功能的实现： 然后再加上链栈常用功能的实现，首先链栈需要先添加一个Node类，属性用来存放指针域和数值域，所以先看Node类的定义 然后我们再来看链栈具体功能的实现 上述代码都是实现了接口，所以把接口的定义放上去 java数据结构- - - -栈 标签：maxsize [] des this 数组 inter gen while for 原文地址：https://www.cnblogs.com/yaoruozi/p/9744791.html 1 package com.demo.stackone;
2
3 /**
4 Author:yao
5 Date:2018年9月20日
6 Description:面试被问到栈的实现于是回来再在这里温习一下啊
7
8 首先：介绍一下栈，栈是一种特殊的线性表，不同于一般线性表的是，一般线性表可以在表内任意位置添加和删除元素，
9 而栈只可以在尾端进行，栈尾一般称之为栈顶，另一端称之为栈底，特点是：后进先出/先进后出
10
11 stack的接口相关实现类
12 *
13 */
14 public class StackDemo implements IStack {
15 private Object[] stackElem;//定义元素对象数组
16 private int top;//在栈为非空的情况下，top始终指向栈顶元素的下一个存储位置；当栈为空时，top值为0；
17
18 public StackDemo(int MaxSize) {
19 top = 0;
20 stackElem = new Object[MaxSize];
21 }
22
23 @Override
24 //清空栈
25 public void clear() {
26 top = 0;
27 }
28
29 @Override
30 //判断栈是否为空
31 public boolean isEmpty() {
32 return top == 0;
33
34 }
35
36 @Override
37 //栈内元素个数
38 public int length() {
39 return top;
40
41 }
42
43 @Override
44 //获取栈顶元素
45 public Object peek() {
46 if (!isEmpty()) {
47 return stackElem[top - 1];
48 } else {
49 return null;
50 }
51
52 }
53
54 //入栈操作
55 @Override
56 public void push(Object o) throws Exception {
57 if (top == stackElem.length) {
58 throw new Exception("栈已满");
59 } else {
60 stackElem[top++] = o;
61 }
62 }
63
64 //出栈操作
65 @Override
66 public Object pop() {
67 if (isEmpty()) {
68 return null;
69 } else {
70 return stackElem[--top];
71 }
72
73 }
74
75 //输出栈内所有元素（栈顶--->栈底）
76 public void printAllElement() {
77 for (int i = top - 1; i >= 0; i--) {
78 System.out.print(stackElem[i].toString() + " ");
79 }
80 }
81
82 }
1 package com.demo.linkstack;
2
3 /**
4 Author:yao
5 Date:2018年10月5日
6 Description:链表需要定义Node类，定义三大属性，(数据域，后指针)
7 *
8 */
9 public class Node {
10 private Object data;
11 private Node next;
12
13 public Node() { //初始化一个空结点
14 super();
15 // TODO Auto-generated constructor stub
16 }
17
18 public Node(Object data) { //构造一个数据域指针为指定值，指针域为空的结点
19 super();
20 this.data = data;
21 }
22
23 public Node(Object data, Node next) { //带有数据域和指针的结点
24 super();
25 this.data = data;
26 this.next = next;
27 }
28
29 public Object getData() {
30 return data;
31 }
32
33 public void setData(Object data) {
34 this.data = data;
35 }
36
37 public Node getNext() {
38 return next;
39 }
40
41 public void setNext(Node next) {
42 this.next = next;
43 }
44
45 @Override
46 public String toString() {
47 return "Node [data=" + data + ", next=" + next + "]";
48 }
49
50 }
package com.demo.linkstack;
/**
Author:yao
Date:2018年10月5日
Description:链栈的实现原理
*
*/
public class LinkedStack implements LinkStack {
private Node top; //栈顶元素的引用
//将栈置空
@Override
public void clear() {
top = null;
}
//判断栈是否为空
@Override
public boolean isEmpty() {
return top == null;
}
//获得栈的长度
@Override
public int length() {
Node p = top;
int length = 0;
while (p != null) {
p = p.getNext();
++length;
}
return length;
}
//获取栈顶元素并且返回
@Override
public Object peek() {
if (!isEmpty()) {
return top;
} else {
return null;
}
}
//入栈
@Override
public void push(Object o) throws Exception {
Node node = new Node(o);
node.setNext(top);
top = node;
}
//出栈
@Override
public Object pop() {
if (isEmpty()) {
return null;
} else {
Node p = top; //指向要被删除的结点
top = top.getNext();//修改顶部指针，原来顶部的下一个节点现在为新的栈顶
return p.getData(); //返回新的栈顶元素数值
}
}
//输出链栈中的所有元素
public void printAll() {
Node p = top;
while (p != null) {
System.out.print(p.getData().toString() + " ");
p = p.getNext();
}
}
}
public interface LinkStack {
public void clear();//清空栈
public boolean isEmpty();//判断栈是否为空
public int length();//返回栈中元素的个数
public Object peek();//取栈顶元素并且返回其值，如果栈是空，就返回null
public void push(Object o) throws Exception;//入栈
public Object pop();//出栈
}