【算法】实现栈和队列
正文
栈(stack)
栈(stack)是一种后进先出(LIFO)的集合类型, 即后来添加的数据会先被删除
可以将其类比于下面文件的取放操作:新到的文件会被先取走,这使得每次取走的文件都是最新的。
栈可以用数组或者队列去实现
下面要实现的栈的API如下图所示:
用数组实现栈
下面我们通过数组实现一个指定了初始容量,但随着元素的增加能够动态地扩张容量的栈。注意: 因为数组指定大小后不可改变, 所以我们要定义自动扩大栈容量的操作
public class ArrayStack<Item> { // 栈元素的总数 private int N = 0; // 存放栈元素的数组 private Item [] items; public ArrayStack (int M) { items = (Item[]) new Object[M]; } /** * @description: 调整栈的大小 */ private void resize (int max) { Item [] temp = (Item [])new Object[max]; for (int i =0;i<items.length;i++) { temp[i] = items[i]; } items = temp; } /** * @description: 向栈顶插入元素 */ public void push (Item item) { // 当栈满了的时候, 将栈的数组大小扩大为原来两倍 if (N==items.length) resize(2*N); items[N++] = item; } /** * @description: 从栈顶删除元素,并将删除的元素返回 */ public Item pop () { // 当栈还是空的时候, 不删除并且返回空 if(isEmpty()) return null; // 保存将要被删除的元素 Item i = items[N-1]; // 将该元素删除 items[N-1] = null; // 栈的长度减1 N--; return i; } /** * @description: 判断栈是否为空