Stack (Stack) Is a thread table that only inserts or deletes at the end of the table . So the end of the table has a special meaning for the stack , Stack Top (top), The corresponding header end is called the bottom of the stack (bottom).

Stack is a kind of LIFO (last in first out) Linear table of , abbreviation LIFO.

<> Abstract data type definition of stack
package com.codestd.study.stack; /** * Stack ADT */ public interface Stack<E> { /**
* View top of stack elements , View elements only , Don't take it out of the stack . */ E peek(); /** * Add elements to the stack . */ void push(E e); /** *
Take out the top element of the stack */ E pop(); /** * Empty stack */ void clear(); /** * Number of elements in the stack , If the stack is empty , Then return 0 */ int
size(); /** * Judge whether the stack is empty */ boolean isEmpty(); /** * Determine whether the stack is full */ boolean isFull(); }
<> The representation and implementation of stack

As mentioned before , There are two ways for computers to store data , One is sequential storage , One is non sequential storage . The stack corresponds to two storage modes, and there are two implementation modes : One is array , One is one-way linked list .

<> Array implementation of stack

Array implementation stack does not need to record the bottom of the stack , Just record the top pointer . When entering the stack, the top pointer moves backward , When the stack is out, the top pointer moves forward . Using array implementation is relatively simple , It's also easier to achieve .

package com.codestd.study.stack; import java.util.NoSuchElementException; /**
* Array implementation stack */ public class ArrayStack<E> implements Stack<E> { private final int
maxSize; private final E[] elementData; private int top = -1; @SuppressWarnings(
"unchecked") public ArrayStack(int maxSize) { this.maxSize = maxSize; this.
elementData= (E[]) new Object[this.maxSize]; } @Override public E peek() { if (
this.isEmpty()) { throw new NoSuchElementException(" Stack empty "); } return this.
elementData[this.top]; } @Override public void push(E e) { if (this.isFull()) {
throw new RuntimeException(" Stack full "); } this.top++; this.elementData[this.top] = e;
} @Override public E pop() { if (this.isEmpty()) { throw new
NoSuchElementException(" Stack empty "); } E el = this.elementData[this.top]; this.
elementData[this.top] = null; this.top--; return el; } @Override public void
clear() { for (int i = 0; i < this.top + 1; i++) { this.elementData[i] = null; }
this.top = -1; } @Override public int size() { return this.top + 1; } @Override
public boolean isEmpty() { return this.size() == 0; } @Override public boolean
isFull() { return (this.top + 1) == this.maxSize; } }
<> Chain list implementation of stack

It's a little more complicated to use linked list . Here we use a one-way linked list .

Different from the previous one-way list , Here we are no longer using next Point to next node , It's about using prev Point to previous node . Then the pointer top
Always point to the latest node . If the stack top data is taken out , The pointer points to the prev.

Now we use the code to implement .
package com.codestd.study.stack; import java.util.NoSuchElementException; /**
* Linked list implementation stack */ public class LinkedStack<E> implements Stack<E>{ private Node<E> top;
private int size; private int maxSize = Integer.MAX_VALUE; public LinkedStack()
{ } public LinkedStack(int maxSize) { this.maxSize = maxSize; } @Override public
Epeek() { if (this.isEmpty()) { throw new NoSuchElementException(" There are no elements in the stack "); }
return this.top.item; } @Override public void push(E e) { if (this.isFull()) {
throw new RuntimeException(" Stack full "); } if (this.top == null) { this.top = new Node<
>(e); } else { Node<E> node = new Node<>(e); node.prev = this.top; this.top =
node; } this.size++; } @Override public E pop() { if (this.isEmpty()) { throw
new NoSuchElementException(" There are no elements in the stack "); } Node<E> node = this.top; this.top = node
.prev; node.prev = null; this.size--; return node.item; } @Override public void
clear() { Node<E> node = this.top; while (node != null) { Node<E> prev = node.
prev; node.prev = null; node = prev; } this.top = null; this.size = 0; }
@Override public int size() { return this.size; } @Override public boolean
isEmpty() { return this.size == 0; } @Override public boolean isFull() { return
this.size == this.maxSize; } private static class Node<E> { E item; Node<E> prev
; public Node(E item) { this.item = item; } } }

Technology
©2019-2020 Toolsou All rights reserved,
java Four functional interfaces ( a key , simple )os Simple use of module HashMap Explain in detail html Writing about cherry trees , Writing about cherry trees It's unexpected Python Cherry tree (turtle The gorgeous style of Library ) computer network --- Basic concepts of computer network ( agreement , system ) Some East 14 Pay change 16 salary , Sincerity or routine ? Browser kernel ( understand )