Java language implementation data structure stack code detail

Recently, I reviewed the data structure and implemented the stack myself. A stack is a table that restricts insertions and deletions to only one place. The most basic operations are push and push, so it is also called "in last out" table.

First, understand the concept of the lower stack:

A stack is a linear table that qualifies inserts and deletes only at the table head. Sometimes called LIFO (last in, first out). To understand this concept, we must first understand the original meaning of "stack", so that we can grasp the essence.

"Stack", the storage of goods or accommodation for passengers, can be extended to warehouse, transfer station, so introduced into the computer field, is the temporary storage of index data, so there is a stack, out of the stack.

The implementation method is as follows: first, an interface is defined, and then the linear stack and chain stack are implemented through this interface. The code is relatively simple, as follows:

package com.peter.java.dsa.interfaces;
/**
 *  Stack operation definition 
 * 
 * @author Peter Pan
 */
public interface Stack<T> {
	/*  Sentenced to empty  */
	Boolean isEmpty();
	/*  Empty stack  */
	void clear();
	/*  Play the stack  */
	T pop();
	/*  Into the stack  */
	Boolean push(T data);
	/*  The length of the stack  */
	int length();
	/*  Look at the element at the top of the stack, but do not remove it  */
	T peek();
	/*  Returns the location of the object in the stack  */
	int search(T data);
}

Linear stack: Implemented as an array.

package com.peter.java.dsa.common;
import com.peter.java.dsa.interfaces.Stack;
/**
 *  Linear stack 
 * 
 * @author Peter Pan
 */
public class LinearStack<T> implements Stack<T> {
	@SuppressWarnings("unchecked")
	 private T[] t = (T[]) new Object[16];
	private int size = 0;
	@Override
	 public Boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}
	@Override
	 public void clear() {
		// TODO Auto-generated method stub
		for (int i = 0; i < t.length; i++) {
			t[i] = null;
		}
		size = 0;
	}
	@Override
	 public T pop() {
		// TODO Auto-generated method stub
		if (size == 0) {
			return null;
		}
		T tmp = t[size - 1];
		t[size - 1] = null;
		size--;
		return tmp;
	}
	@Override
	 public Boolean push(T data) {
		// TODO Auto-generated method stub
		if (size >= t.length) {
			resize();
		}
		t[size++] = data;
		return true;
	}
	@Override
	 public int length() {
		// TODO Auto-generated method stub
		return size;
	}
	@Override
	 public T peek() {
		// TODO Auto-generated method stub
		if (size == 0) {
			return null;
		} else {
			return t[size - 1];
		}
	}
	/* return index of data, return -1 if no data */
	@Override
	 public int search(T data) {
		// TODO Auto-generated method stub
		int index = -1;
		for (int i = 0; i < t.length; i++) {
			if (t[i].equals(data)) {
				index = i;
				break;
			}
		}
		return index;
	}
	@SuppressWarnings("unchecked")
	 private void resize() {
		T[] tmp = (T[]) new Object[t.length * 2];
		for (int i = 0; i < t.length; i++) {
			tmp[i] = t[i];
			t[i] = null;
		}
		t = tmp;
		tmp = null;
	}
	/* from the left to the right is from the top to the bottom of the stack */
	@Override
	 public String toString() {
		// TODO Auto-generated method stub
		StringBuffer buffer = new StringBuffer();
		buffer.append("Linear Stack Content:[");
		for (int i = t.length - 1; i > -1; i--) {
			buffer.append(t[i].toString() + ",");
		}
		buffer.append("]");
		buffer.replace(buffer.lastIndexOf(","), buffer.lastIndexOf(",") + 1, "");
		return buffer.toString();
	}
}

Chained stack: Implemented by a single linked list.

package com.peter.java.dsa.common;
import com.peter.java.dsa.interfaces.Stack;
public class LinkedStack<T> implements Stack<T> {
	private Node top;
	private int size;
	@Override
	 public Boolean isEmpty() {
		// TODO Auto-generated method stub
		return size == 0;
	}
	@Override
	 public void clear() {
		// TODO Auto-generated method stub
		top = null;
		size = 0;
	}
	@Override
	 public T pop() {
		// TODO Auto-generated method stub
		T topValue = null;
		if (top != null) {
			topValue = top.data;
			Node oldTop = top;
			top = top.prev;
			oldTop.prev = null;
			size--;
		}
		return topValue;
	}
	@Override
	 public Boolean push(T data) {
		// TODO Auto-generated method stub
		Node oldTop = top;
		top = new Node(data);
		top.prev = oldTop;
		size++;
		return true;
	}
	@Override
	 public int length() {
		// TODO Auto-generated method stub
		return size;
	}
	@Override
	 public T peek() {
		// TODO Auto-generated method stub
		T topValue = null;
		if (top != null) {
			topValue = top.data;
		}
		return topValue;
	}
	@Override
	 public int search(T data) {
		// TODO Auto-generated method stub
		int index = -1;
		Node tmp = top;
		for (int i = size - 1; i > -1; i--) {
			if (tmp.data.equals(data)) {
				index = i;
				break;
			} else {
				tmp = tmp.prev;
			}
		}
		tmp = null;
		return index;
	}
	@Override
	 public String toString() {
		// TODO Auto-generated method stub
		StringBuffer buffer = new StringBuffer();
		buffer.append("Linked Stack Content:[");
		Node tmp = top;
		for (int i = 0; i < size - 1; i++) {
			buffer.append(tmp.toString() + ",");
			tmp = tmp.prev;
		}
		tmp = null;
		buffer.append("]");
		buffer.replace(buffer.lastIndexOf(","), buffer.lastIndexOf(",") + 1, "");
		return super.toString();
	}
	private class Node {
		T data;
		Node prev;
		public Node(T data) {
			// TODO Auto-generated constructor stub
			this.data = data;
		}
	}
}

Learning is ongoing and we will continue to update the code in the future.

This is the Java language implementation of the data structure stack code detailed content, I hope to help you. Interested friends can continue to refer to other related topics in this site, if there is any deficiency, welcome to comment out. Thank you for your support!