データ構造-Java実装スタックの順序格納とチェーン記憶

10282 ワード

スタックの順序格納
配列で実現
//      :        :  0    ;length-1    
public class MySqStack {
	int[] data;//  
	int top;//     

	public MySqStack(int size) {
		data = new int[size];
		top = -1;
	}

	//   
	public boolean push(int element) {
		//     ,     
		if (top == data.length - 1) {
			// throw new RuntimeException("stack is empty");
			return false;
		} else {
			top++;
			data[top] = element;
			return true;
		}
	}

	//   
	public int pop() {
		//         
		if (top == -1) {
			throw new RuntimeException("stack is empty");
		} else {
			return data[top--];
		}
	}

	//      
	public int GetTop() {
		//         
		if (top == -1) {
			throw new RuntimeException("stack is empty");
		} else {
			return data[top];
		}
	}
スタックのチェーン記憶
シングルチェーンで実現します.
public class LinkStack {
	class Node {
		int data;
		Node next;
	}
	//      
	private Node header = new Node();

	//      :    :       
	public boolean push(int data) {
		Node node = new Node();
		node.data = data;
		node.next = header.next;
		header.next = node;
		return true;
	}
	//  :           
	public int pop() {
		if(header.next == null) {
			return -1;
		}
		else {
			int rtn = 0;
			rtn = header.next.data;
			header.next = header.next.next;
			return rtn;
		}
	}
	//     
	public int getTop() {
		if(header.next == null) {
			return -1;
		}
		else {
			return header.next.data;
		}
	}