Recently, I have reviewed the data structure and implemented the stack by myself. A stack is a type of table that restricts insertion and deletion of only one position. The most basic operations are in and out of the stack, so it is also called the "first in and out" table.
First, let’s understand the concept of stack:
A stack is a linear table that limits insertion and deletion operations only in the table header. Sometimes it is also called LIFO (latest in first out table). To understand this concept, you must first understand the original meaning of "stack", so that you can grasp the essence.
"Stack" means a place where goods are stored or passengers can be extended to a warehouse or a transit station. Therefore, it is introduced into the computer field, which refers to the place where data is temporarily stored, so there is a saying that it enters the stack and exits the stack.
The implementation method is as follows: first define an interface, and then implement a linear stack and a chain stack 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> {/* Query empty*/Boolean isEmpty();/* Clear stack*/void clear();/* Bull stack*/T pop();/* Enter stack*/Boolean push(T data);/* length of stack*/int length();/* View the element at the top of the stack, but not remove it*/T peek();/* Return the position of the object in the stack*/int search(T data);}Linear stack: implemented in 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 stubreturn size == 0;}@Override public void clear() {// TODO Auto-generated method stubfor (int i = 0; i < t.length; i++) {t[i] = null;}size = 0;}@Override public T pop() {// TODO Auto-generated method stubif (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 stubif (size >= t.length) {resize();}t[size++] = data;return true;}@Override public int length() {// TODO Auto-generated method stubreturn size;}@Override public T peek() {// TODO Auto-generated method stubif (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 stubint 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 stubStringBuffer 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();}}Chain stack: implemented through 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 stubreturn size == 0;}@Override public void clear() {// TODO Auto-generated method stubtop = null;size = 0;}@Override public T pop() {// TODO Auto-generated method stubT 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 stubNode oldTop = top;top = new Node(data);top.prev = oldTop;size++;return true;}@Override public int length() {// TODO Auto-generated method stubreturn size;}@Override public T peek() {// TODO Auto-generated method stubT topValue = null;if (top != null) {topValue = top.data;}return topValue;}@Override public int search(T data) {// TODO Auto-generated method stubint 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 stubStringBuffer 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 stubthis.data = data;}}}Learning is still in progress and the code will continue to be updated in the future.
This is all the detailed explanation of the Java language implementation data structure stack code, I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!