This is part 2 of Java Data structures and Algorithms. From this part we will look at the design and implementation of the stack.

  • The abstract data type of the stack
  • Design and implementation of sequential stack
  • Design and implementation of chain stack
  • The application of the stack

The abstract data type of the stack

Stack is a simple data structure used to store data, similar to the list or sequential table (generally referred to as the linear table), the Stack and linear table is the biggest difference between the operation of the data access, we may think that the Stack (Stack) is a special kind of linear table, the insert and delete operation is allowed only in linear one end of the table, the general, The end of the allowed operation is called the Top of the stack, and the end of the non-operable is called the Bottom of the stack. At the same time, the operation of inserting elements is called Push, and the operation of deleting elements is called Pop. If there are no elements in the stack, it is called an empty stack. The structure of the stack is shown as follows:

From the diagram, we can see that the stack can only access the elements from the top of the stack, while the elements that enter first are the last ones out, and the top of the stack always points to the top element in the stack. Here we can give the formal definition of stack: A Stack (Stack) is a special ordered linear table. Only one end of the table (called the top of the Stack, top, always points to the top element) can be inserted and deleted. The last inserted element will be deleted first. Thus the stack is also called a linear list of Last In First Out (LIFO) or First In Last Out (FILO). Note that the Stack does not support the specified position to delete, insert, its interface Stack declaration is as follows:

3 */ 4 public interface Stack<T> {5 6 /** 7 public interface Stack<T> {5 6 * @return 9 */ 10 Boolean isEmpty(); 14 * @param data 15 */ 16 void push(T data); 20 * @return 21 */ 22 T peek(); 26 * @return 27 */ 28 T pop(); 26 * @return 27 */ 28 T pop(); 29}Copy the code

Design and implementation of sequential stack

Order stack, just as its name implies is to use the order table to implement the stack, order of the stack based on the order form, internal implementation of elements of access operation, of course, we can also use internal stack array implementation order, here we use the internal data group to implement a stack, as for the stack implementation, based on the sequence table as will be provided in source code. The Serializable interface can also be added to the Stack as follows:

3 */ 4 public class SeqStack<T> implements Stack<T>,Serializable {5 6 private static final Long serialVersionUID = -5413303117698554397L; Private int top= 1; private int top= 1; private int top= 1; 12 13 /** 14 * The default capacity is 10 15 */ 16 private int Capacity =10; 17 private T[] array; 17 private T[] array; 22 23 private int size; 24 25 public SeqStack(int capacity){ 26 array = (T[]) new Object[capacity]; 27 } 28 29 public SeqStack(){ 30 array= (T[]) new Object[this.capacity]; 31} 32 / /... Omit other code 33}Copy the code

The peek operation process of obtaining the value of the top element of the stack is shown below (only the value is obtained without deletion) :

This is the operation to get the top element of the stack, as follows:

6 public T peek() {7 if(isEmpty()) 8 new EmptyStackException(); 9 return array[top]; 10}Copy the code

The process of adding elements from the stack is as follows (update the top pointer to the stack) :

The above is the push operation, the code is as follows:

1 /** 2 * add element, insert 3 * from the top of stack (end of array) when the capacity is insufficient, 4 * @param data 5 */ 6 @override 7 public void push(T data) {8 // Check whether the capacity is sufficient 9 if(array.length==size) 10 ensureCapacity(size*2+1); Array [++top]=data; array[++top]=data; 14}Copy the code

The stack pops the top element as follows (delete and get the value) :

The above is the stack removal operation, the code is as follows:

6 public T pop() {7 if(isEmpty()) 8 new EmptyStackException(); 9 size--; 10 return array[top--]; 11}Copy the code

We can also use MyArrayList as a base to implement the sequential stack. This is also relatively simple, and we will provide the code later, so we won’t be verbose here. The following is the overall implementation code of the sequential stack:

1 import java.io.Serializable; 2 import java.util.EmptyStackException; 4 public class SeqStack<T> implements Stack<T>,Serializable {8 9 private static final Long serialVersionUID = -5413303117698554397L; Private int top= 1; private int top= 1; private int top= 1; 15 16 /** 17 * The default capacity is 10 18 */ 19 private int Capacity =10; Private T[] array; private T[] array; 25 26 private int size; 27 28 public SeqStack(int capacity){ 29 array = (T[]) new Object[capacity]; 30 } 31 32 public SeqStack(){ 33 array= (T[]) new Object[this.capacity]; 34 } 35 36 public int size(){ 37 return size; 38 } 39 40 41 @Override 42 public boolean isEmpty() { 43 return this.top==-1; 51 public void push(T data) {51 public void push(T data) {51 public void push(T data) {51 public void push(T data) {51 public void push(T data) {51 public void push(T data) {51 public void push(T data) {51 public void push(T data) {51 public void push(T data) {51 public void push(T data) {51 public void push(T data) {51 public void push(T data) if(array.length==size) 54 ensureCapacity(size*2+1); Array [++top]=data; 58 59 size++; 62 public T peek() {68 if(isEmpty()) 69 new EmptyStackException(); 70 return array[top]; 78 public T pop() {79 if(isEmpty()) 80 new EmptyStackException(); 81 size--; 82 return array[top--]; 88 * @param capacity 88 */ 89 public void ensureCapacity(int capacity) {90 91 if (capacity<size) 92 return; 93 94 T[] old = array; 95 array = (T[]) new Object[capacity]; For (int I =0; i<size ; i++) 98 array[i]=old[i]; 99 } 100 101 public static void main(String[] args){ 102 SeqStack<String> s=new SeqStack<>(); 103 s.push("A"); 104 s.push("B"); 105 s.push("C"); 106 System.out.println("size->"+s.size()); 107 int l=s.size(); For (int I =0; i<l; i++){ 109 System.out.println("s.pop->"+s.pop()); 110 } 111 112 System.out.println("s.peek->"+s.peek()); 114 113}}Copy the code

Design and implementation of chain stack

After understanding sequential Stack, we then look at Linked Stack. The so-called Linked Stack refers to the Stack with chained storage structure. Since we operate at the top of the Stack, we use a single Linked list (without the leading node) as the basis, and directly implement the main operations such as Stack addition, acquisition and deletion. Its operation process is shown as follows:

As can be seen from the figure, both insertion and deletion directly operate on the top of the list, that is, the top element of the stack, so we only need to use a single list without the leading node. The code implementation is as follows, relatively simple, but more analysis:

1 import com.zejian.structures.LinkedList.singleLinked.Node; 2 3 import java.io.Serializable; 4 public class LinkedStack<T> implements Stack<T>,Serializable{9 10 private static final Long serialVersionUID = 1911829302658328353L; 11 12 private Node<T> top; 13 14 private int size; 15 16 public LinkedStack(){ 17 this.top=new Node<>(); 18 } 19 20 public int size(){ 21 return size; 22 } 23 24 25 @Override 26 public boolean isEmpty() { 27 return top==null || top.data==null; 28 } 29 30 @Override 31 public void push(T data) { 32 if (data==null){ 33 throw new StackException("data can\'t be null"); 34} 35 if(this.top==null){// Call pop() top may be null 36 this.top=new Node<>(data); 37 }else if(this.top.data==null){ 38 this.top.data=data; 39 }else { 40 Node<T> p=new Node<>(data,this.top); 41 top=p; // update stack top 42} 43 size++; 44 } 45 46 @Override 47 public T peek() { 48 if(isEmpty()){ 49 throw new EmptyStackException("Stack empty"); 50 } 51 52 return top.data; 53 } 54 55 @Override 56 public T pop() { 57 if(isEmpty()){ 58 throw new EmptyStackException("Stack empty"); 59 } 60 61 T data=top.data; 62 top=top.next; 63 size--; 64 return data; Public static void main(String[] args){68 LinkedStack<String> sl=new LinkedStack<>(); 69 sl.push("A"); 70 sl.push("B"); 71 sl.push("C"); 72 int length=sl.size(); 73 for (int i = 0; i < length; i++) { 74 System.out.println("sl.pop->"+sl.pop()); 75} 76} 77}Copy the code