“This is my third day of the November Gwen Challenge.The final text challenge in 2021”

Abstract

After exploring dynamic arrays or linked lists in previous installments, subsequent stacks can be implemented again using the structure of linear tables. When we implemented the stack, we found that it was much easier to implement on the basis of linear tables.

The stack data structure is used in many scenarios, such as jumping between web pages.

The definition of the stack

A stack is a special kind of linear table that can only be operated on at one end. The main features of the stack are as follows:

  • The operation of adding elements to the stack is called pushing.
  • The operation of removing elements from the stack, called pop, can only remove elements at the top of the stack
  • The stack follows the principle of Last In First Out (LIFO)

Stack interface design

According to the characteristics of the stack, the related interface of the stack can be designed:

function paraphrase
int size(); Number of elements
boolean isEmpty(); Whether is empty
void push(E element); Into the stack
E pop(); Out of the stack
E top(); Gets the top of the stack element
void clear(); empty
  • E is a generic type

The internal implementation of the stack can be a dynamic array or a linked list.

Stack code implementation

Here we create a class using E as the template, and then we create a list array of the ArrayList type to hold the data

public class Stack<E> { private List<E> list = new ArrayList<>(); // Other code content.... }Copy the code

The number of elements can be obtained by accessing the size() of the list object:

int size() {
  return list.size();
}
Copy the code

We can also access the isEmpty() implementation of the list:

boolean isEmpty()  {
  return list.isEmpty();
}
Copy the code

Next, we implement the stack method. Since the stack puts the elements at the end of the array, we can use the add() method of the list directly:

void push(E element) {
  list.add(element);
}
Copy the code

To unstack is to remove the element at the top of the stack, which is the last element in the array, so remove the last element using the remove method of list. The size() of the list gets the number of arrays, so subtract 1 to get the last element in the array.

E pop() {
  return list.remove(list.size() -1);
}
Copy the code

Fetching the top element of the stack means fetching the last element of the array directly:

E top() {
  return list.get(list.size() -1);
}
Copy the code

The final way to clear is also to use the list clear() method directly:

void clear() {
  list.clear();
}
Copy the code

The whole implementation is completed, it is found that the stack is the package of the array, so it seems that the stack structure is also very simple, here to use a lot of methods to deal with the array, so the structure of the array is not very clear, you can see the dynamic array introduced in the future.