Java code to achieve the basic method of stack data structure induction
- 2020-04-01 04:06:33
- OfStack
Chain implementation:
Add and remove elements in a section of the stack, maintain a node to the top of the stack and a count variable to indicate the size of the stack:
Private LinearNode top; // points to the top of the stack
Private int count; // marks the size of the stack
Each time the stack and the stack in the linked list of the table head :(can also be the end of the table, the implementation is not the same)
Top - > Element 1 - > Element 2 - > Elements 3...
Implementation (with test main) :
LinkedStack
package Stack;
import Bag.LinearNode;
//To focus on the algorithm, print out the exception and exit the program without declaring the exception class
public class LinkedStack implements StackADT {
private LinearNode top; //Point to the top
private int count;//Mark the size of the stack
public static void main(String[] args){
LinkedStack stack = new LinkedStack();
System.out.println(" will 0 to 10 In turn the stack ");
for(int i = 0;i < 10;i++)
stack.push(i);
System.out.println(" Continuous execution 5 Secondary stack operation ");
for(int i = 0;i < 5;i++)
stack.pop();
System.out.println(" Is the stack empty? : " + stack.isEmpty());
System.out.println(" The stack size is: " + stack.size());
System.out.println(" The top element of the stack is: " + stack.top.getElement());
System.out.println(" The top element of the stack is: " + stack.peek());
}
public LinkedStack()
{
top = null;
count = 0;
}
public int size() {
return count;
}
public boolean isEmpty() {
return (size() == 0);
}
public void push(Object element) {
LinearNode node = new LinearNode(element);
node.setNext(top);
top = node;
count++;
}
public Object pop() {
if(isEmpty())
{
System.out.println("stack is empty!");
System.exit(1);
}
Object result = top.getElement();
top = top.getNext();
count--;
return result;
}
public Object peek() {
Object result = top.getElement();
return result;
}
}
Operation results:
Push the stack from 0 to 10
Perform 5 stack operations in a row
Is the stack empty? : false
The stack size is: 5
The top element of the stack is: 4
The top element of the stack is: 4
Array implementation:
The bottom of the stack is always the position where the array index is 0. The push-out stack starts with the last element of the array index:
private Object[] contents;
private int top;//Top marks the location of the next push, and also indicates the capacity of the stack, compared with the chain implementation of count!!
Implementation (with test main) :
ArrayStack
package Stack;
public class ArrayStack implements StackADT {
private Object[] contents;
private int top;//Top marks the location of the next push, and also indicates the capacity of the stack, compared with the chain implementation of count!!
private static int SIZE = 10;
public ArrayStack()
{
contents = new Object[SIZE];
top = 0;
}
public void expand(){//By applying for an auxiliary space, the capacity is doubled each time
Object[] larger = new Object[size()*2];
for(int index = 0;index < top;index++)
larger[index] = contents[index];
contents = larger;
}
public int size() {
return top;
}
public boolean isEmpty() {
return (size() == 0);
}
public void push(Object element) {
//if(isEmpty())
//expand();
if(top == contents.length)
expand();
contents[top] = element;
top++;
}
public Object pop() {
if(isEmpty())
{
System.out.println("stack is empty!");
System.exit(1);
}
Object result = contents[top-1];
contents[top-1] = null;//Out of the stack
top--;
return result;
}
public Object peek() {
Object result;
if(isEmpty())
result = null;
else
result = contents[top-1];
return result;
}
public static void main(String[] args) {
ArrayStack stack = new ArrayStack();
System.out.println(" will 0 to 24 Push the stack one by one, then continue 10 time Out of the stack");
for(int i = 0;i < 25;i++)
stack.push(i);
for(int i = 0;i < 10;i++)
stack.pop();
System.out.println(" The stack size is: " + stack.size());
System.out.println(" Is the stack empty? : " + stack.isEmpty());
System.out.println(" The top element of the stack is: " + stack.peek());
}
}
Operation results:
Push the stack from 0 to 24, then push it out 10 times in a row
The stack size is: 15
Is the stack empty? : false
The top element of the stack is: 14
Use the collection LinkedList to simulate the stack
methods
Java generics let LinkedList simulate a stack of various data types, including int, double, String, Object, and so on. Here are a few API interfaces:
Into the stack
void addFirst(E e); //Inserts the specified element at the beginning of the list
Gets the top element of the stack
E getFirst(); //Returns the first element of this list
Out of the stack
E removeFirst(); //Removes and returns the first element in this list
Sentenced to stack is empty
boolean isEmpty(); //Determine the stack is empty
The sample code
import java.util.LinkedList;
import java.util.NoSuchElementException;
public class SimulateStack {
private LinkedList<Integer> stack = new LinkedList<Integer>();
public boolean isEmpty() {
return this.stack.isEmpty();
}
public void push(int data) {
this.stack.addFirst(data);
}
public int pop() throws NoSuchElementException{
return this.stack.removeFirst();
}
public int getTop() throws NoSuchElementException{
return this.stack.getFirst();
}
public static void main(String args[]) {
SimulateStack s = new SimulateStack();
s.push(1);
s.push(2);
s.push(3);
while (! s.isEmpty()) {
int data = s.getTop();
System.out.println(data);
s.pop();
}
}
}