day-2-3-4

栈Stack

栈的实现可以有数组实现的顺序栈和链表结构的链式栈

数组实现的栈结构

如果需要一个支持动态扩容的顺序栈，则底层还需要以来一个支持动态扩容的数组，将原来的数据搬移到新数组中。也可以使用顺序栈支持动态扩容。

public class ArrayStack {private Object[] items;  //栈中存放的数据private int size;  // 栈中存放数据的个数public ArrayStack() {this(10);}public ArrayStack(int capacity) {items=new Object[capacity];}//数据压栈--将数据存储在栈顶public boolean push(Object item) {//如果栈已经满了则不允许再添加数据if(size==items.length)return false;items[size++]=item;return true;}//数据弹栈--将数据栈栈顶的数据获取出来，同时删除栈顶数据public Object pop() {//如果栈中没有数据则返回为nullif(size==0)return null;return items[--size];}
}

java预定义的栈实现

public class Stack extends Vector

实现方式为自定义实现的可变长数组，线程安全

• E push(E item) 把项压入堆栈顶部

• synchronized E pop() 移除堆栈顶部的对象，并作为此函数的值返回该对象
• synchronized E peek() 查看堆栈顶部的对象，但不从堆栈中移除它
• boolean empty() 测试堆栈是否为空
• synchronized int search(Object o) 返回对象在堆栈中的位置，以 1 为基数

public class Test1 {public static void main(String[] args) {Stack<Integer> stack = new Stack<>();for(int i=1;i<=5;i++)stack.push(i);Integer kk=stack.pop();System.out.println(kk+"::"+stack.size());int pos=stack.search(Integer.valueOf(4));System.out.println("4位于栈中的索引号为"+pos);//1，获取的位置从栈顶开始计算，序号从1开始Integer kk2=stack.peek();System.out.println(kk2+"::"+stack.size());while(!stack.empty())System.out.println(stack.pop());System.out.println(stack.size());}
}

总结自定义栈–在线考试题–放水题

栈是一种用于存储数据的简单数据结构，栈与线性表的最大区别是数据的存取的操作，可以这样认为栈Stack是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶Top，不可操作的一端称为栈底Bottom，同时把插入元素的操作称为入栈Push，删除元素的操作称wd 为出栈Pop。若栈中没有任何元素，则称为空栈

顺序栈和链式栈

public class Test2 {public static void main(String[] args) {Stack<Integer> s = new SeqStack<Integer>();System.out.println("是否为空" + s.empty());for (int i = 0; i < 5; i++)s.push(i);System.out.println("栈顶数据为" + s.peek());while (!s.empty())System.out.println(s.pop());}
}
//定义接口
interface Stack<T> {// 栈是否为空boolean empty();// data元素入栈void push(T data);// 返回栈顶元素,未出栈T peek();// 出栈,返回栈顶元素,同时从栈中移除该元素T pop();
}

如果不考虑编程成本，下一步应该定义抽象类，在抽象类中添加公共方法

顺序栈，顾名思义就是采用顺序表实现的的栈，顺序栈的内部以顺序表为基础，实现对元素的存取操作，当然还可以采用内部数组实现顺序栈，这里使用内部数据组来实现栈，至于以顺序表作为基础的栈实现

class SeqStack<T> implements Stack<T>, Serializable {// 栈顶指针，-1代表空栈private int top = -1;// 容量大小默认为10private int capacity = 10;// 存放元素的数组private T[] array;private int size;public SeqStack() {array = (T[]) new Object[capacity];}// 一般情况下应该方法名称为getSize，但是遵循一般的使用习惯，所以命名为size()public int size() {return size;}@Overridepublic boolean empty() {return this.top == -1;}// 添加元素,从栈顶(数组尾部)插入public void push(T data) {// 判断容量是否充足if (size == array.length)ensureCapacity(size * 2 + 1);// 扩容// 从栈顶添加元素array[++top] = data;size++;}private synchronized void ensureCapacity(int len) {Object[] res = new Object[len];System.arraycopy(array, 0, res, 0, this.size);this.array = (T[]) res;}// 获取栈顶元素的值,不删除public T peek() {if (empty())throw new EmptyStackException();return array[top];}// 从栈顶(顺序表尾部)删除public T pop() {if (empty())throw new EmptyStackException();size--;return array[top--];}}class EmptyStackException extends RuntimeException {private static final long serialVersionUID = -4870633979582008865L;public EmptyStackException() {super("栈中没有数据");}public EmptyStackException(String message, Throwable cause, boolean enableSuppression, boolean writableStackTrace) {super(message, cause, enableSuppression, writableStackTrace);}public EmptyStackException(String message, Throwable cause) {super(message, cause);}public EmptyStackException(String message) {super(message);}public EmptyStackException(Throwable cause) {super(cause);}}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！