[Java]基本数据结构实现

原文链接

下压栈

C语言实现

Java实现

package cn.ywrby.data.structure;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import java.util.Iterator;


//定义下压栈，动态调整数组的大小
public class ResizingArrayStack<Item> implements Iterable<Item> {
	
	private Item[] data = (Item[]) new Object[1];    //栈
	private int N = 0;  //栈内元素数量
	
	//判断栈是否为空
	public boolean isEmpty() {  
		return N == 0;
	}
	
	//返回栈内元素数量
	public int size() {
		return N;
	}
	
	
	//调整栈的大小
	public void resize(int max) {
		Item[] temp = (Item[]) new Object[max];
		for (int i = 0; i < N; i++) {
			temp[i] = data[i];
		}
		data = temp;
	}
	
	
	//压栈
	public void push(Item item) {
		if (N == data.length) {
			resize(2 * data.length);
		}
		data[N++] = item;
	}
	
	
	//出栈
	public Item pop() {
		Item item = data[--N];
		data[N] = null;
		if (N > 0 && N <= data.length / 4) {
			resize(data.length / 2);
		}
		return item;
	}
	
	//迭代器的实现
	@Override
	public Iterator<Item> iterator() {
		// TODO 自动生成的方法存根 
		//返回一个迭代器
		return new ReverseArrayIterator();
	}
	//定义迭代器类
	private class ReverseArrayIterator implements Iterator<Item> {
		private int i = N;
		//判断是否有下一个
		@Override
		public boolean hasNext() {
			// TODO 自动生成的方法存根
			return i > 0;
		}
		//返回下一个元素
		@Override
		public Item next() {
			// TODO 自动生成的方法存根
			return data[--i];
		}
		
		public void remove() {

		}
	}

	public static void main(String[] args) {
		ResizingArrayStack<Double> array=new ResizingArrayStack<Double>();
		for (int i=0;i<10;i++) {
			double num=StdRandom.uniform();
			StdOut.println(num);
			array.push(num);
		}   
		StdOut.println("-------------------------------");
		Iterator iterator=array.iterator();
		while(iterator.hasNext()) {
			StdOut.println(iterator.next());
		}
		// TODO 自动生成的方法存根

	}

}

链表

C语言实现

Java实现

package cn.ywrby.data.structure;

import java.util.Iterator;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;


//定义下压堆栈（链表）
public class Stack<Item> implements Iterable<Item> {
	//首节点
	private Node first;
	//元素数量
	private int N;
	//定义节点类
	private class Node{
		Item item;
		Node next;
	}
	public boolean isEmpty() {
		return N==0;
	}
	public int size() {
		return N;
	}
	public void push(Item data) {
		Node oldFirst=first;
		first=new Node();
		first.item=data;
		first.next=oldFirst;
		N++;
	}
	public Item pop() {
		Node oldFirst=first;
		first=first.next;
		N--;
		return oldFirst.item;
	}
	@Override
	public Iterator<Item> iterator() {
		// TODO 自动生成的方法存根
		return new StackIterator();
	}
	private class StackIterator implements Iterator<Item>{
		private Node current=first;
		
		@Override
		public boolean hasNext() {
			// TODO 自动生成的方法存根
			return current!=null;
		}

		@Override
		public Item next() {
			Item data=current.item;
			current=current.next;
			// TODO 自动生成的方法存根
			return data;
		}
		public void remove() {}
		
	}
	
	public static void main(String[] args) {
		Stack<Double> stack=new Stack<Double>();
		for(int i=0;i<10;i++) {
			double num=StdRandom.uniform();
			StdOut.println(num);
			stack.push(num);
		}
		System.out.println("-----------------------------");
		Iterator iterator=stack.iterator();
		while(iterator.hasNext()) {
			StdOut.println(iterator.next());
		}
		
		// TODO 自动生成的方法存根

	}

	

}

队列

C语言实现

Java实现

package cn.ywrby.data.structure;

import java.util.Iterator;

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;


public class Queue<Item> implements Iterable<Item> {
	private Node first;
	private Node last;
	private int N;

	private class Node {
		Item item;
		Node next;
	}

	public boolean isEmpty() {
		return N == 0;
	}

	public int size() {
		return N;
	}

	public void enqueue(Item data) {
		// 向表尾插入元素
		Node oldLast = last;
		last = new Node();
		last.item = data;
		last.next = null;
		if (isEmpty()) {
			first = last;
		} else {
			oldLast.next = last;
		}
		N++;
	}

	public Item dequeue() {
		// 从表头删除元素
		Node oldFirst = first;
		first = oldFirst.next;
		if (isEmpty()) {
			last = null;
		}
		N--;
		return oldFirst.item;
	}

	@Override
	public Iterator<Item> iterator() {
		// TODO 自动生成的方法存根
		return new QueueIterator();
	}
	private class QueueIterator implements Iterator<Item>{
		private Node current=first;
		
		@Override
		public boolean hasNext() {
			// TODO 自动生成的方法存根
			return current!=null;
		}

		@Override
		public Item next() {
			Item data=current.item;
			current=current.next;
			// TODO 自动生成的方法存根
			return data;
		}
		public void remove() {}
		
	}
	public static void main(String[] args) {
		Queue<Double> queue=new Queue<Double>();
		for(int i=0;i<10;i++) {
			double num=StdRandom.uniform();
			StdOut.println(num);
			queue.enqueue(num);
		}
		System.out.println("-----------------------------");
		Iterator iterator=queue.iterator();
		while(iterator.hasNext()) {
			StdOut.println(iterator.next());
		}
		// TODO 自动生成的方法存根

	}

}

背包

package cn.ywrby.data.structure;

import java.util.Iterator;

//Bag数据结构跟Stack基本完全一致，区别仅在于Bag不具有pop函数
//也就是加入背包的元素不可以再流出
public class Bag<Item> implements Iterable<Item> {
	// 首节点
	private Node first;
	// 元素数量
	private int N;

	// 定义节点类
	private class Node {
		Item item;
		Node next;
	}
	public boolean isEmpty() {
		return N==0;
	}
	public int size() {
		return N;
	}
	public void push(Item data) {
		Node oldFirst=first;
		first=new Node();
		first.item=data;
		first.next=oldFirst;
		N++;
	}
	@Override
	public Iterator<Item> iterator() {
		// TODO 自动生成的方法存根
		return new BagIterator();
	}
	private class BagIterator implements Iterator<Item>{
		private Node current=first;
		
		@Override
		public boolean hasNext() {
			// TODO 自动生成的方法存根
			return current!=null;
		}

		@Override
		public Item next() {
			Item data=current.item;
			current=current.next;
			// TODO 自动生成的方法存根
			return data;
		}
		public void remove() {}
		
	}
	public static void main(String[] args) {
		// TODO 自动生成的方法存根

	}

}