Java学习----栈Stack

今日学习内容总结如下：

栈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() {
		//如果栈中没有数据则返回为null
		if(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 为基数

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

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

顺序栈和链式栈

//定义接口
interface Stack {
	// 栈是否为空
	boolean empty();
 
	// data元素入栈
	void push(T data);
 
	// 返回栈顶元素,未出栈
	T peek();
 
	// 出栈,返回栈顶元素,同时从栈中移除该元素
	T pop();
}

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

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

class SeqStack implements Stack, Serializable {
	// 栈顶指针，-1代表空栈
	private int top = -1;
	// 容量大小默认为10
	private int capacity = 10;
	// 存放元素的数组
	private T[] array;
	private int size;
 
	public SeqStack() {
		array = (T[]) new Object[capacity];
	}
 
	// 一般情况下应该方法名称为getSize，但是遵循一般的使用习惯，所以命名为size()
	public int size() {
		return size;
	}
 
	@Override
	public 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);
	}
 
}

Queue队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端front进行删除操作，而在表的后端rear进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作端称为队尾，进行删除操作端称为队头。

根据实现方式不同分为顺序队列和链式队列

顺序队列

采用数组实现

队列的基本操作为添加数据的入队操作enqueue和删除并获取数据的dequeue出队操作

public class ArrayQueue {
	private Object[] items; // 具体存储数据的数组
	private int head = 0;// 队头下标
	private int tail = 0; // 队尾下标
 
	public ArrayQueue() {
		this(10);
	}
 
	public ArrayQueue(int capacity) {
		items = new Object[capacity];
	}
 
	public boolean enqueue(Object item) { // 入队操作
		if (tail == items.length)
			return false; // 队伍已满，拒绝插入操作
		items[tail++] = item;
		return true;
	}
 
	public Object dequeue() { // 出队操作
		if (head == tail)
			return null; // 队列为空
		return items[head++];
	}
}

循环队列

基于数组的队列实现中，当tail=items.length时需要搬移大量的数据，就会导致入队操作的性能降低，可以使用循环队列解决。

典型算法题目：约瑟夫环

import java.util.Arrays;
 
public class CircleQueue {
	private Object[] items;
	private int head = 0, tail = 0;
 
	public CircleQueue() {
		this(10);
	}
 
	public CircleQueue(int capacity) {
		items = new Object[capacity];
	}
 
	public boolean enqueue(Object item) {
		// 如果尾指针和头指针重合则表示不能插入数据，因为头指针指向的位置上有数据
		if (tail % items.length  == head && items[head] != null) {
			return false;
		} // 拒绝插入数据
		tail = tail % items.length;
		items[tail++] = item;
		return true;
	}
 
	public Object dequeue() {
		if (head== tail && items[head] != null)
			return null;
		Object res = items[head];
		items[head] = null;
		head = (head + 1) % items.length;
		return res;
	}
 
	public static void main(String[] args) {
		CircleQueue cq = new CircleQueue();
		for (int i = 0; i < 12; i++) {
			cq.enqueue(i);
		}
		System.out.println(Arrays.toString(cq.items));
		System.out.println("ddd:" + cq.head);
		for (int i = 0; i < 4; i++)
			System.out.println(cq.dequeue());
		for (int i = 11; i < 20; i++) {
			cq.enqueue(i);
		}
		System.out.println(Arrays.toString(cq.items));
	}
}