Stack
-
Stack concept
Stack, also known as stack, is a linear table with limited operation. The limitation is that only insert and delete operations are allowed at one end of the table. This end is called the top of the stack, and the other end is called the bottom of the stack. Inserting new elements into a stack is also called pushing, pushing or pressing. It is to put new elements on top of the stack to make it a new stack top element. Deleting elements from a stack is also called pushing out or pushing back. It is to delete the stack top elements and make the adjacent elements become new stack top elements. -
Graphical interpretation
-
java implementation stack structure
package com.ds.lesson02;
import java.util.ArrayList;
import java.util.List;
/**
* Stack features: first in first out
*
* Variables required for stack:
* top: Top of stack
* size: Number of elements in the stack
* length: Total stack capacity
* list Collections: as stack containers
*
* How to implement the stack:
* Push (t t t)
* Out of stack: T pop()
* Take a look: boolean peek()
* Number of elements in the stack: int size()
*
* @author Administrator
*
*/
public class MyStack<T> {
private int top; // Top of stack, indicating the subscript of the top of stack element
private int size; // Number of elements in the stack
private int length; //Total stack capacity
private List<T> listStack = new ArrayList<T>(); //As stack container
/**
* Nonparametric construction method
*/
public MyStack() {
this.top = -1;
this.size = 0;
this.length = 10;
}
/**
* Including parameter structure: set the total stack capacity
* @param length Total stack capacity
*/
public MyStack(int length) {
super();
this.top = -1;
this.size = 0;
this.length = length;
if(length <= 0){
this.length = 10;
}
}
/**
* Stack entry method
* @param t Stack data
* @return boolean
*/
public boolean push(T t){
//Judgement stack
if(size == length){
return false;
}
else{
top++;
listStack.add(t);
size++;
return true;
}
}
/**
* Stack out method
* @return T Top element of stack
*/
public T pop(){
//Judge stack space
if(size == 0){
return null;
}
else{
T t = listStack.get(top);
top--;
size--;
return t;
}
}
/**
* View top of stack elements
* @return boolean
*/
public boolean peek(){
//Judge whether the stack is empty
if(size == 0){
return false;
}
else{
T t = listStack.get(top);
System.out.println(t);
return true;
}
}
/**
* View the number of elements in the stack
* @return int Number of elements in the stack
*/
public int size(){
return size;
}
public static void main(String[] args) {
MyStack<Integer> myStack = new MyStack<>();
//Enter stack
System.out.println("=============Enter stack===============");
myStack.push(1);
myStack.push(2);
myStack.push(3);
System.out.println("Stack elements:" + myStack.size());
//Take a look at the top of the stack
System.out.print("Top of stack:");
myStack.peek();
//Stack out
System.out.println("=============Stack out===============");
System.out.println("Stack:" + myStack.pop());
System.out.println("Stack elements:" + myStack.size());
//Take a look at the top of the stack
System.out.print("Top of stack:");
myStack.peek();
}
}
- Operation result
queue
- Queue concept
Queue is a kind of special linear table. The special thing is that it only allows deletion at the front end of the table, and insertion at the rear end of the table. Like stack, queue is a kind of linear table with limited operation. The end of the insertion operation is called the end of the queue, and the end of the deletion operation is called the head of the queue - Graphical interpretation
- java implementation of queue structure
package com.ds.lesson02;
import java.util.ArrayList;
import java.util.List;
/**
* Queue characteristics: first in, first out
*
* Variables required for the queue:
* front: Head of the team
* rear: End of team
* size: Number of elements in the queue
* length: Total queue capacity
* list: Most queue containers
*
* How to implement the queue:
* Team entry: boolean add(T t)
* Team leaving: T offer()
* View team leader: boolean peek()
* Number of team elements: int size()
*
* @author Administrator
*
* @param <T>
*/
public class MyQueue<T> {
private int front;
private int rear;
private int length;
private int size;
private List<T> queue = new ArrayList<>();
/**
* Non parametric structure
*/
public MyQueue() {
this.front = 0;
this.rear = -1;
this.size = 0;
this.length = 10;
}
/**
* Team entry method
* @param t Team elements
* @return boolean
*/
public boolean add(T t){
//Judgement team
if(size == length){
return false;
}
else{
rear++; //End of team subscript plus 1
queue.add(rear, t); //Join the team to the end
size++; //Number of elements in the team plus 1
return true;
}
}
/**
*Team exit method
* @return t Queue element
*/
public T offer(){
//Judge team empty
if(size == 0){
return null;
}
else{
T t = queue.get(front); // Get team leader element
// At the same time of the first and second marks, the team is empty after leaving the team, and the team variable returns to the initial state
if(front == rear){
front = 0;
rear = -1;
size = 0;
return t;
}
front++;
size--;
return t;
}
}
/**
* View team leader elements
* @return boolean
*/
public boolean peek(){
//Judge team empty
if(size == 0){
return false;
}
else{
T t = queue.get(front);
System.out.println(t);
return true;
}
}
/**
* Get the number of team elements
* @return int
*/
public int size(){
return size;
}
public static void main(String[] args) {
MyQueue<String> myQueue = new MyQueue<>();
//Join the team
System.out.println("==============Join the team==============");
myQueue.add("a");
myQueue.add("b");
myQueue.add("c");
System.out.println("Number of team elements:" + myQueue.size());
System.out.print("Team leader:");
myQueue.peek();
System.out.println("==============Team out==============");
System.out.println("Outgoing element:" + myQueue.offer());
System.out.println("Number of team elements:" + myQueue.size());
System.out.print("Team leader:");
myQueue.peek();
}
}
- Operation result
