阅读大话数据结构（3）

本文在阅读大话数据结构这本书的基础上，结合java语言的特点，来理解栈和队列，代码均为自己实现。

栈与队列

栈是限定仅在表尾进行插入和删除操作的线性表。（类似弹夹中的子弹）
队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表。（类似等待客服电话排队）

栈的抽象数据类型

栈本身也是一种线性表，除了删除和添加改名为pop(弹)和push(压)，抽象功能没有特别的地方。为了方便实现我们还是自定义栈的接口

，另外注意一点是java的sdk继承vector实现的stack，相关操作使用synchronized，具有安全性。

public interface IStack<E> {
	boolean isEmpty();
	boolean push(E e);
	E peek();
	E pop();
	int size();
	void clear();
}

栈的顺序存储结构(两栈共享空间)

import java.util.Arrays;
public class Mystack<E> implements IStack<E> {
	private Object[] elementData;
	private int size;
	private int top;
	public Mystack(){
		this(10);
	}
	public Mystack (int initcapactity){
		if(initcapactity > 0) {
			this.elementData = new Object[initcapactity];
			this.size = initcapactity;
			this.top = -1;
		}else{
			throw new RuntimeException("stack init capactity < 0");
		}
	}
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return top == -1;
	}
	@Override
	public boolean push(E e) {
		// TODO Auto-generated method stub
		if(top == size - 1){
			ensureCapacity();
		}
		elementData[++top]=e;
		return true;
	}
	private void ensureCapacity(){
		int oldcapacity = elementData.length;
		int newcapacity = oldcapacity + (oldcapacity >> 1);
		size = newcapacity;
		Arrays.copyOf(elementData, newcapacity);
	}
	@Override
	public E peek() {
		// TODO Auto-generated method stub
		if(top == -1){
			throw new RuntimeException("stack is empty");
		}
		E e=elementData(top);
		return e;
	}
	@Override
	public E pop() {
		// TODO Auto-generated method stub
		if(top == -1){
			throw new RuntimeException("stack is empty");
		}
		E e=elementData(top);
		elementData[top]=null;
		top--;
		return e;
	}
	@Override
	public int size() {
		// TODO Auto-generated method stub
		return top + 1;
	}
	@Override
	public void clear() {
		// TODO Auto-generated method stub
		for (int i = 0 ; i < elementData.length; i++) {
			elementData[i] = null;
		}
		top = -1;
	}
	@SuppressWarnings("unchecked")
	E elementData(int top){
		return (E) elementData[top];
	}
	@Override
	public String toString(){
		String str ="[";
		for (int i = 0 ; i <= top; i++) {
			str = str + elementData[i] + ",";
		}
		str = str + "]";
		return str;
	}
}

public class Teststack {
	public static void main(String[] args) {
		IStack<String> stack = new Mystack<String>();
		System.out.println("stack.size()"+stack.size());
		System.out.println(stack.isEmpty());
		stack.push("a");
		stack.push("b");
		stack.push("c");
		stack.push("d");
		System.out.println("stack.size() = "+stack.size());
		System.out.println(stack.toString());
		stack.pop();
		System.out.println(stack.peek());
		stack.clear();
		System.out.println(stack.size());
	}
}

public class Sharestack<E>{
	private Object[] elementData;
	private int size;
	private int top1;
	private int top2;
	public Sharestack(){
		this(20);
	}
	public Sharestack (int initcapactity){
		if(initcapactity > 0) {
			this.elementData = new Object[initcapactity];
			this.size = initcapactity;
			this.top1 = -1;
			this.top2 = size;
		}else{
			throw new RuntimeException("stack init capactity < 0");
		}
	}
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return top1 == -1 && top2 == size;
	}
	public boolean push(int i ,E e) {
		// TODO Auto-generated method stub
		if(top1 == size - 1 || top2 == 0){
			throw new RuntimeException("stack is full");
		}
		if(i == 1){
			elementData[++top1]=e;
		} else if (i == 2){
			elementData[--top2]=e;
		} else{
			throw new RuntimeException("i is 1 or 2");
		}
		return true;
	}
	public E peek(int i) {
		// TODO Auto-generated method stub
		E e;
		if(i == 1){
			if(top1 == -1){
				throw new RuntimeException("stack is empty");
			}
			e=elementData(top1);
		}else if(i == 2){
			if(top2 == size){
				throw new RuntimeException("stack is empty");
			}
			e=elementData(top2);
		}else{
			throw new RuntimeException("i is 1 or 2");
		}
		return e;
	}
	public E pop(int i) {
		// TODO Auto-generated method stub
		E e;
		if(i == 1){
			if(top1 == -1){
				throw new RuntimeException("stack is empty");
			}
			e=elementData(top1);
			elementData[top1]=null;
			top1--;
		}else if(i == 2){
			if(top2 == size){
				throw new RuntimeException("stack is empty");
			}
			e=elementData(top2);
			elementData[top2]=null;
			top2++;
		}else{
			throw new RuntimeException("i is 1 or 2");
		}
		return e;
	}
	public int size(int i) {
		// TODO Auto-generated method stub
		if(i == 1){
			return top1 + 1;
		}else if(i == 2){
			return size - top2;
		}else{
			throw new RuntimeException("i is 1 or 2");
		}		
	}
	public void clear() {
		// TODO Auto-generated method stub
		for (int i = 0 ; i < elementData.length; i++) {
			elementData[i] = null;
		}
		top1 = -1;
		top2 = size;
	}
	@SuppressWarnings("unchecked")
	E elementData(int top){
		return (E) elementData[top];
	}
	@Override
	public String toString(){
		String str ="stack 1:[";
		for (int i = 0 ; i <= top1; i++) {
			str = str + elementData[i] + ",";
		}
		str = str + "] stack 2:[";
		for (int i = size - 1 ; i >=top2; i--) {
			str = str + elementData[i] + ",";
		}
		str =str +"]";
		return str;
	}
}

public class Testsharestack {
	public static void main(String[] args) {
		Sharestack<String> stack = new Sharestack<String>();
		System.out.println("stack1.size() = "+stack.size(1));
		System.out.println("stack2.size() = "+stack.size(2));
		System.out.println(stack.isEmpty());
		stack.push(1,"a");
		stack.push(2,"b");
		stack.push(1,"c");
		stack.push(2,"d");
		System.out.println("stack1.size() = "+stack.size(1));
		System.out.println("stack2.size() = "+stack.size(2));
		System.out.println(stack.toString());
		stack.pop(1);
		System.out.println(stack.peek(1));
		System.out.println(stack.toString());
		stack.clear();
		System.out.println(stack.size(1));
		System.out.println(stack.size(2));
		stack.push(1,"a");
		System.out.println(stack.toString());
	}
}

栈的链式存储结构

public class Mystack<E> implements IStack<E>{
	private Node<E> top;
	private int size;
	
	public Mystack(){
		
	}
	
	private static class Node<E>{
		private E item;
		private Node<E> next;
		public Node(E item , Node<E> next){
			this.item = item;
			this.next = next;
		}
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}

	@Override
	public boolean push(E e) {
		// TODO Auto-generated method stub
		if(top == null){
			final Node<E> newNode = new Node<E>(e,null);
			top = newNode;
		}else{
			final Node<E> newNode = new Node<E>(e,top);
			top = newNode;
		}
		size++;
		return true;
	}

	@Override
	public E peek() {
		// TODO Auto-generated method stub
		return top.item;
	}

	@Override
	public E pop() {
		// TODO Auto-generated method stub
		Node<E> e = top;
		E item = e.item;
		e = null;
		top = top.next;
		return item;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}

	@Override
	public void clear() {
		// TODO Auto-generated method stub
		for(Node<E> x = top; x != null;) {
			Node<E> next = x.next;
			x.item = null;
			x.next = null;
			x = next;
		}
		top = null;
		size = 0;
	}
	@Override
	public String toString(){
		String str = "[";
		for(Node<E> x = top; x != null;) {
			Node<E> next = x.next;
			str = str + x.item + ",";
			x = next;
		}
		str = str + "]";
		return str;
	}
}

public class Teststack {
	public static void main(String[] args) {
		IStack<String> stack = new Mystack<String>();
		System.out.println("stack.size()"+stack.size());
		System.out.println(stack.isEmpty());
		stack.push("a");
		stack.push("b");
		stack.push("c");
		stack.push("d");
		System.out.println("stack.size() = "+stack.size());
		System.out.println(stack.toString());
		stack.pop();
		System.out.println(stack.peek());
		System.out.println(stack.toString());
		stack.clear();
		System.out.println(stack.size());
		stack.push("a");
		System.out.println(stack.peek());
		System.out.println(stack.toString());
	}
}

队列的抽象数据类型

队列本身也是一种线性表，不同的是插入只能是队尾，删除只能是队首，抽象功能同样没有特别的地方。

public interface IQueue<E> {
	boolean offer(E e);
	E poll();//the head of this queue, or {@code null} if this queue is empty
	boolean isEmpty();
	void clear();
	E element(); //NoSuchElementException if this queue is empty
	E peek();  //the head of this queue, or {@code null} if this queue is empty
    int size();
}

队列的顺序存储结构（循环队列）

循环队列指队列的首尾相接的顺序存储结构。

import java.util.NoSuchElementException;

public class MyQueue<E> implements IQueue<E> {
	private Object[] elementData;
	private int front;
	private int rear;
	private int length;
	
	public MyQueue(){
		this(10);
	}
	public MyQueue(int capacity){
		this.elementData = new Object[capacity];
		this.length = capacity;
		this.front = 0;
		this.rear = 0;
	}

	@Override
	public boolean offer(E e) {
		// TODO Auto-generated method stub
		if (front == (rear + 1) % length) {
			throw new RuntimeException("queue is full");
		}
		elementData[rear] =e;
		rear = (rear + 1) % length;
		return true;
	}

	@Override
	public E poll() {
		// TODO Auto-generated method stub
		if (front == rear){
			return null;
		}
		E e = elementData(front);
		elementData[front] =null;
		front = (front + 1) % length;
		return e;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return front == rear;
	}

	@Override
	public void clear() {
		// TODO Auto-generated method stub
		for(int i = 0 ; i < elementData.length; i++){
			elementData[i] = null;
		}
		front = rear = 0;
	}

	@Override
	public E element() {
		// TODO Auto-generated method stub
		if (front == rear){
			throw new NoSuchElementException("queue is empty"); 
		}
		E e = elementData(front);
		return e;
	}

	@Override
	public E peek() {
		// TODO Auto-generated method stub
		if (front == rear){
			return null;
		}
		E e = elementData(front);
		return e;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return (length + rear - front) % length;
	}
	
	@SuppressWarnings("unchecked")
	E elementData(int i){
		return (E) elementData[i];
	}
	@Override
	public String toString(){
		String str ="[";
		for(int i = front ; i != rear; i = (i + 1) % length){
			str = str + elementData[i] + ",";
		}
		str = str + "]";
		return str;
	}

}

public class Testqueue {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		IQueue<String> queue = new MyQueue<String>(6);
		System.out.println(queue.isEmpty());
		queue.offer("a");
		queue.offer("b");
		queue.offer("c");
		queue.offer("d");
		queue.offer("e");
		System.out.println(queue.toString());
		System.out.println(queue.size());
		queue.poll();
		System.out.println(queue.peek());
		queue.poll();
		System.out.println(queue.peek());
		System.out.println(queue.size());
		System.out.println(queue.toString());
		queue.offer("a");
		System.out.println(queue.peek());
		System.out.println(queue.toString());
		queue.offer("b");
		System.out.println(queue.toString());
		queue.clear();
		System.out.println(queue.toString());
		System.out.println(queue.isEmpty());
	}

}

队列的链式存储结构

import java.util.NoSuchElementException;
public class MyQueue<E> implements IQueue<E> {
	
	private Node<E> front;
	private Node<E> rear;
	private final Node<E> node;
	private int size;
	
	public MyQueue(){
		node = new Node<E>(null,null);
		this.front = node;
		this.rear = node;
	}
	
	private static class Node<E>{
		private E item;
		private Node<E> next;
		public Node(E item , Node<E> next){
			this.item = item;
			this.next = next;
		}
	}

	@Override
	public boolean offer(E e) {
		// TODO Auto-generated method stub
		final Node<E> newNode = new Node<E>(e, null);
		rear.next = newNode;
		rear = newNode;
		size++;
		return true;
	}

	@Override
	public E poll() {
		// TODO Auto-generated method stub
		if(front.next == null){
			return null;
		}
		Node<E> e = front.next;
		front.next = e.next;
		size--;
		return e.item;
	}

	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}

	@Override
	public void clear() {
		// TODO Auto-generated method stub
		for(Node<E> x = front; x != null;){
			Node<E> next = x.next;
			x.item =null;
			x.next = null;
			x = next;
		}
		front = rear = node;
		size =0;
		
	}

	@Override
	public E element() {
		// TODO Auto-generated method stub
		if(front.next == null){
			throw new NoSuchElementException("queue is empty"); 
		}
		Node<E> e =front.next;
		return e.item;
	}

	@Override
	public E peek() {
		// TODO Auto-generated method stub
		if(front.next == null){
			return null;
		}
		Node<E> e =front.next;
		return e.item;
	}

	@Override
	public int size() {
		// TODO Auto-generated method stub
		return size;
	}
	@Override
	public String toString(){
		String str = "[";
		for(Node<E> x = front.next; x !=null;) {
			Node<E> next = x.next;
			if(x.item != null){
				str = str + x.item +",";
			}
			x = next;
		}
		str = str + "]";
		return str;
	}

}

public class Testqueue {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		IQueue<String> queue = new MyQueue<String>();
		System.out.println(queue.isEmpty());
		queue.offer("a");
		queue.offer("b");
		queue.offer("c");
		queue.offer("d");
		queue.offer("e");
		System.out.println(queue.toString());
		System.out.println(queue.size());
		queue.poll();
		System.out.println(queue.peek());
		queue.poll();
		System.out.println(queue.peek());
		System.out.println(queue.size());
		System.out.println(queue.toString());
		queue.offer("a");
		System.out.println(queue.peek());
		System.out.println(queue.toString());
		queue.offer("b");
		System.out.println(queue.toString());
		queue.clear();
		queue.offer("a");
		queue.offer("b");
		queue.offer("c");
		queue.offer("d");
		queue.offer("e");
		queue.clear();
		System.out.println(queue.toString());
		System.out.println(queue.isEmpty());
	}

}