数据结构与算法——Java实现 21.栈

目录

一、概述

二、基于链表的栈的实现

接口

链表接口实现类

测试类

​编辑

三、基于数组的栈的实现

接口

数组接口实现类

测试类

---

妈妈，生日快乐，希望你健康快乐没有烦恼也不会有病痛

                                                                                —— 24.9.28

一、概述

计算机科学中，stack是一种线性的数据结构，只能在其一端添加数据和移除数据。习惯来说，这一端称之为栈顶，另一端不能操作数据的称之为栈底，就如同生活中的一摞书

二、基于链表的栈的实现

接口

public interface Stack<E> {/*向栈顶压入元素Params：value-待压入值Returns：压入成功返回true，否则返回false*/boolean push(E vale);/*从栈顶弹出元素Returns：栈非空返回栈顶元素，栈为空返回null*/E pop();/*返回栈顶元素，不弹出Returns：栈非空返回栈顶元素，栈为空返回null*/E peek();/*判断栈是否为空Returns：空返回true，非空返回false*/boolean isEmpty();/*判断栈是否为满Returns:满返回true，空返回false*/boolean isFull();
}

链表接口实现类

import java.util.Iterator;public class LinkedListStack<E> implements Stack<E>,Iterable<E> {// 容量private int capacity;// 元素个数private int size;// 头指针private Node<E> top = new Node<>(null,null);public LinkedListStack(int capacity) {this.capacity = capacity;}/*向栈顶压入元素Params：value-待压入值Returns：压入成功返回true，否则返回false*/@Overridepublic boolean push(E value) {if (isFull()){return false;}Node<E> node = new Node<>(value, top.next);top.next = node;size++;return true;}/*从栈顶弹出元素Returns：栈非空返回栈顶元素，栈为空返回null*/@Overridepublic E pop() {if (isEmpty()) {return null;}Node<E> next = top.next;top.next = top.next.next;size--;return next.value;}/*返回栈顶元素，不弹出Returns：栈非空返回栈顶元素，栈为空返回null*/@Overridepublic E peek() {if (isEmpty()) {return null;}Node<E> next = top.next;return next.value;}/*判断栈是否为空Returns：空返回true，非空返回false*/@Overridepublic boolean isEmpty() {return top.next == null;}/*判断栈是否为满Returns:满返回true，空返回false*/@Overridepublic boolean isFull() {boolean b = size == capacity;return b;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node<E> next = top.next;@Overridepublic boolean hasNext() {return next != null;}@Overridepublic E next() {E value = next.value;next = next.next;return value;}};}// 单项链表实现栈static class Node<E> {E value;Node<E> next;public Node(E value, Node<E> next) {this.value = value;this.next = next;}}
}

测试类

import org.junit.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;
public class TestLinkedListStack {@Testpublic void push() {LinkedListStack<Object> stack = new LinkedListStack<>(3);stack.push(1);stack.push(2);stack.push(3);assertFalse(stack.push(4));assertIterableEquals(List.of(3,2,1),stack);}@Testpublic void pop() {LinkedListStack<Object> stack = new LinkedListStack<>(3);stack.push(1);stack.push(2);stack.push(3);assertEquals(3,stack.pop());assertEquals(2,stack.pop());assertEquals(1,stack.pop());assertNull(stack.pop());System.out.println(stack.isEmpty());}
}

三、基于数组的栈的实现

接口

public interface Stack<E> {/*向栈顶压入元素Params：value-待压入值Returns：压入成功返回true，否则返回false*/boolean push(E vale);/*从栈顶弹出元素Returns：栈非空返回栈顶元素，栈为空返回null*/E pop();/*返回栈顶元素，不弹出Returns：栈非空返回栈顶元素，栈为空返回null*/E peek();/*判断栈是否为空Returns：空返回true，非空返回false*/boolean isEmpty();/*判断栈是否为满Returns:满返回true，空返回false*/boolean isFull();
}

数组接口实现类

import java.util.Iterator;public class ArrayStack<E> implements Stack<E>,Iterable<E> {private E[] array;// 栈顶指针private int top;@SuppressWarnings("all")public ArrayStack(int capacity) {this.array = (E[]) new Object[capacity];}/*向栈顶压入元素Params：value-待压入值Returns：压入成功返回true，否则返回false*/@Overridepublic boolean push(E value) {if(isFull()){return false;}array[top] = value;top++;return true;}/*从栈顶弹出元素Returns：栈非空返回栈顶元素，栈为空返回null*/@Overridepublic E pop() {if(isEmpty()){return null;}E e = array[top-1];top--;return e;}/*返回栈顶元素，不弹出Returns：栈非空返回栈顶元素，栈为空返回null*/@Overridepublic E peek() {if(isEmpty()){return null;}E e = array[top-1];return e;}/*判断栈是否为空Returns：空返回true，非空返回false*/@Overridepublic boolean isEmpty() {return top == 0;}/*判断栈是否为满Returns:满返回true，空返回false*/@Overridepublic boolean isFull() {return top == array.length;}@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int p = top;@Overridepublic boolean hasNext() {return p > 0;}@Overridepublic E next() {E e = array[p-1];p--;return e;}};}
}

测试类

import org.junit.Test;import java.util.List;import static org.junit.jupiter.api.Assertions.*;public class TestArrayStack {@Testpublic void push() {ArrayStack<Object> stack = new ArrayStack<>(3);stack.push(1);stack.push(2);stack.push(3);assertFalse(stack.push(4));assertIterableEquals(List.of(3,2,1),stack);}@Testpublic void pop() {ArrayStack<Object> stack = new ArrayStack<>(3);stack.push(1);stack.push(2);stack.push(3);assertEquals(3,stack.pop());assertEquals(2,stack.pop());assertEquals(1,stack.pop());assertNull(stack.pop());System.out.println(stack.isEmpty());}
}