Stack
栈是...
定义IStack接口
package _09_Linear.Stack;
public interface IStack<T> {
/**
* 元素入栈
* @param e
*/
void push(T e);
/**
* 弹出栈顶(栈中无此元素)
* @return
*/
T pop();
/**
* 是否空栈
* @return
*/
boolean empty();
/**
* 栈内元素个数
* @return
*/
int getSize();
/**
* 查看栈顶的元素 <br>不弹出
* @return
*/
public T peek();
}
Stack 实现接口
继承DoubleLinkList 泛型版
package _09_Linear.Stack;
import _09_Linear.list.DoubleLinkList;
import _09_Linear.list.ListNode;
import java.util.EmptyStackException;
public class MyStack<T> extends DoubleLinkList<T> implements IStack<T> {
@Override
public void push(T e) {
add(e);
}
@Override
public T pop() {
if (size <= 0) throw new EmptyStackException();
ListNode<T> the = super.last.getPre();//last 的前一个
T res = the.getData();
the.getPre().setNext(last);//目标元素的前一个 指向最后
last.setPre(the.getPre());//最后一个元素指向目标元素的前一个
the.setPre(null);
the.setNext(null);
size--;
return res;
}
@Override
public boolean empty() {
return size == 0;
}
@Override
public int getSize() {
return size;
}
@Override
public T peek() {
return last.getPre().getData();
}
}
ListNode
package _09_Linear.list;
/*节点*/
public class ListNode<T> {
T data;//数据
ListNode<T> next;//指向下一个节点的指针
ListNode<T> pre;
public ListNode(T data) {//初始化构造器
this.data = data;
}
public ListNode<T> getPre() {
return pre;
}
public T getData() {
return data;
}
public void setNext(ListNode<T> next) {
this.next = next;
}
public void setPre(ListNode<T> pre) {
this.pre = pre;
}
}
DoubleLinkList
package _09_Linear.list;
public class DoubleLinkList<T> implements MyList<T> {
protected ListNode<T> first = new ListNode(null);//head
protected ListNode<T> last = new ListNode(null);//tail
protected int size;
public DoubleLinkList() {//初始化两个 亚元
first.next = last;
last.pre = first;
}
/**
* 加到 node:last 之前
* 维护四条线
*
* @param element
*/
@Override
public void add(T element) {
ListNode<T> newNode = new ListNode(element);
last.pre.next = newNode;//倒数第二个指向新的
newNode.next = last;//新的尾巴 指向 最后一个
newNode.pre = last.pre;//新的头指向 上次最后一个的前面一个
last.pre = newNode;//最后一个的头 指向新的
size++;
}
@Override
public void delete(T element) {
ListNode<T> p = first.next;
while (p != last) {//终止于 亚元
if (p.data.equals(element)) {//当前p 匹配到了
size--;
p.pre.next = p.next;
p.next.pre = p.pre;
p.next = null;//便于被GC扫描 清除
p.pre = null;
}
p = p.next;//滑动指向下一个节点
}
}
@Override
public void delete(int index) {
if (index < 0 || index >= size) {
return;//索引超出 [0,size)
}
int i = 0;
ListNode<T> p = first.next;
while (p != last) {
if (i == index) {
size--;
p.pre.next = p.next;
p.next.pre = p.pre;
p.next = null;//便于被GC扫描 清除
p.pre = null;
break;
}
i++;
p = p.next;
}
}
@Override
public void update(int index, T newElement) {
if (index < 0 || index >= size) {
return;//索引超出 [0,size)
}
int i = 0;
ListNode<T> p = first.next;
while (p != last) {
if (i == index) {
p.data = newElement;
break;
}
i++;
p = p.next;
}
}
@Override
public boolean contains(T target) {
ListNode<T> p = first.next;
while (p != last) {
if (p.data.equals(target)) {
return true;
}
p = p.next;
}
return false;
}
@Override
public T at(int index) {
if (index < 0 && index >= size) {
return null;
}
int i = 0;
ListNode<T> p = first.next;
while (p != last) {
if (i == index) {
return (T) p.data;
}
p = p.next;
i++;
}
return null;
}
@Override
public int indexOf(T element) {
ListNode<T> p = first.next;
int i = 0;
while (p != last) {
if (p.data.equals(element)) {
return i;
}
p = p.next;
i++;
}
return -1;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
ListNode<T> p = first.next;
while (p != last) {
sb.append(p.data).append(p.next != last ? "," : "");
p = p.next;
}
sb.append("]");//这么写的原因是 如果为空 就[] 不然写到while 里面 while不判定就gg
return "DoubleLinkList{" +
"elements=" + sb.toString() +
"size=" + size +
'}';
}
ListNode<T> now = first;
@Override
public boolean hasNext() {
return now.next != last;
}
@Override
public T next() {
ListNode<T> next = now.next;
now = now.next;
return (T) next.data;
}
}
测试Stack
package _09_Linear.Stack;
import org.junit.Before;
import org.junit.Test;
import java.util.EmptyStackException;
public class MyStackTest {
MyStack<String> stack = new MyStack<>();
@Before
public void init() {
stack.push("a");
stack.push("b");
stack.push("c");
stack.push("d");
}
@Test
public void pop() {
try {
System.out.println(stack.pop());
System.out.println(stack.empty());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println("当前empty状态:" + stack.empty());
System.out.println("当前size状态:" + stack.getSize());
System.out.println("当前栈顶元素:" + stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());//溢出
} catch (EmptyStackException e) {
System.out.println("栈溢出了");
System.out.println(stack.empty());
}
}
}
本文作者:Author: 寒光博客
文章标题:[java] 栈的实现 Stack
本文地址:https://dxoca.cn/java/301.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/java/301.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。