当前位置: 代码迷 >> 综合 >> 数据结构—栈
  详细解决方案

数据结构—栈

热度:134   发布时间:2023-09-06 11:16:40.0

栈的定义
栈是限定仅在表尾进行插入和删除操作的线性表
我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)
不含任何数据元素的栈称为空栈
栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构
栈本身是一个线性表,其数据元素具有线性关系,只不过它是一种特殊的线性表而已
定义中说的是在线性表的表尾进行插入和删除操作,这里表尾是指栈顶,而不是栈底
栈的插入操作,叫作进栈,也称压栈、入栈
栈的删除操作,叫作出栈,也称弹栈
数据结构—栈
栈的主要功能

//特殊情况的线性表
public interface Stack<E> extends Iterable<E>{int getSize();  //获取栈元素个数boolean isEmpty();  //栈判空void push(E e);  //进栈E pop();  //出栈E peek();   //查看当前栈顶void clear();  //清空栈}

栈功能的具体实现(基于上篇线性表代码完成)<线性表链接>

package DS01.动态数组;import java.util.Iterator;public class ArrayStack<E> implements Stack<E> {private ArrayList<E> list;public ArrayStack(){list=new ArrayList<E>();}public ArrayStack(int a){list=new ArrayList<>(a);}@Overridepublic int getSize() {return list.getSize();}@Overridepublic boolean isEmpty() {return list.isEmpty();}@Overridepublic void push(E e) {list.addLast(e);}@Overridepublic E pop() {return list.removeLast();}@Overridepublic E peek() {return list.getLast();}@Overridepublic void clear() {list.clear();}@Overridepublic Iterator<E> iterator() {return list.iterator();}public String toString(){StringBuilder s=new StringBuilder();s.append(String.format("ArrayStack:%d/%d\n",getSize(),list.getCapacity()));s.append('[');if(isEmpty()){s.append(']');}else{for (int i = 0; i <getSize() ; i++) {s.append(list.get(i));if(i==getSize()-1){s.append(']');}else{s.append(',');}}}return s.toString();}
}
  相关解决方案