Java Implement stacks and queues

Stack ：LIFO（ Last in, first out ）

queue ：FIFO（ fifo ）

The sequential storage structure of stack is realized ：

/**
* Sequence stack based on array implementation
* @param <E>
*/
public class Stack<E> {
private Object[] data = null;
private int maxSize=0; // Stack capacity
private int top =-1; // Top pointer of stack
/**
* Constructors ： According to the given size Initialization stack
*/
Stack(){
this(10); // The default stack size is 10
}
Stack(int initialSize){
if(initialSize >=0){
this.maxSize = initialSize;
data = new Object[initialSize];
top = -1;
}else{
throw new RuntimeException(" Initialization size cannot be less than 0：" + initialSize);
}
}
// Sentenced to empty
public boolean empty(){
return top==-1 ? true : false;
}
// Into the stack , First element top=0;
public boolean push(E e){
if(top == maxSize -1){
throw new RuntimeException(" The stack is full , Can't stack element ！");
}else{
data[++top]=e;
return true;
}
}
// Look at the top of the stack, but don't remove
public E peek(){
if(top == -1){
throw new RuntimeException(" The stack is empty. ！");
}else{
return (E)data[top];
}
}
// Pop up top element
public E pop(){
if(top == -1){
throw new RuntimeException(" The stack is empty. ！");
}else{
return (E)data[top--];
}
}
// Returns the position of the object in the stack , With 1 Cardinal number
public int search(E e){
int i=top;
while(top != -1){
if(peek() != e){
top --;
}else{
break;
}
}
int result = top+1;
top = i;
return result;
}
}

The implementation of stack chain storage structure ：

public class LinkStack<E> {
// The node of the chain stack
private class Node<E>{
E e;
Node<E> next;
public Node(){}
public Node(E e, Node next){
this.e = e;
this.next = next;
}
}
private Node<E> top; // Top element of stack
private int size; // Current stack size
public LinkStack(){
top = null;
}
// Current stack size
public int length(){
return size;
}
// Sentenced to empty
public boolean empty(){
return size==0;
}
// Push ： Give Way top Point to the newly created element , New elements next The reference points to the original stack top element
public boolean push(E e){
top = new Node(e,top);
size ++;
return true;
}
// Look at the top of the stack, but don't delete it
public Node<E> peek(){
if(empty()){
throw new RuntimeException(" Empty stack exception ！");
}else{
return top;
}
}
// Out of the stack
public Node<E> pop(){
if(empty()){
throw new RuntimeException(" Empty stack exception ！");
}else{
Node<E> value = top; // Get the stack top element
top = top.next; // Give Way top The reference points to the next element at the top of the original stack
value.next = null; // Release the top element of the original stack next quote
size --;
return value;
}
}
}

be based on LinkedList Implemented stack structure ：

import java.util.LinkedList;
/**
* be based on LinkedList Implementation stack
* stay LinkedList In strength, only partial stack based interfaces are selected
*/
public class StackList<E> {
private LinkedList<E> ll = new LinkedList<E>();
// Push
public void push(E e){
ll.addFirst(e);
}
// Look at the top of the stack, but don't remove
public E peek(){
return ll.getFirst();
}
// Out of the stack
public E pop(){
return ll.removeFirst();
}
// Sentenced to empty
public boolean empty(){
return ll.isEmpty();
}
// Print stack elements
public String toString(){
return ll.toString();
}
}

  The sequential storage structure of queue is realized

public class Queue<E> {
private Object[] data=null;
private int maxSize; // Queue capacity
private int front; // Queue header , Allow deletion of
private int rear; // Queue tail , Allow to insert
// Constructors
public Queue(){
this(10);
}
public Queue(int initialSize){
if(initialSize >=0){
this.maxSize = initialSize;
data = new Object[initialSize];
front = rear =0;
}else{
throw new RuntimeException(" Initialization size cannot be less than 0：" + initialSize);
}
}
// Sentenced to empty
public boolean empty(){
return rear==front?true:false;
}
// Insert
public boolean add(E e){
if(rear== maxSize){
throw new RuntimeException(" The queue is full , Cannot insert new element ！");
}else{
data[rear++]=e;
return true;
}
}
// Go back to team leader , But don't delete
public E peek(){
if(empty()){
throw new RuntimeException(" Empty queue exception ！");
}else{
return (E) data[front];
}
}
// Out of the team
public E poll(){
if(empty()){
throw new RuntimeException(" Empty queue exception ！");
}else{
E value = (E) data[front]; // Keep the queue front The value of the element at the end
data[front++] = null; // Release the queue front Element of end
return value;
}
}
// The queue length
public int length(){
return rear-front;
}
}

Circular queue The implementation of the sequential storage structure of

import java.util.Arrays;
public class LoopQueue<E> {
public Object[] data = null;
private int maxSize; // Queue capacity
private int rear;// Queue tail , Allow to insert
private int front;// Queue header , Allow deletion of
private int size=0; // Current queue length
public LoopQueue() {
this(10);
}
public LoopQueue(int initialSize) {
if (initialSize >= 0) {
this.maxSize = initialSize;
data = new Object[initialSize];
front = rear = 0;
} else {
throw new RuntimeException(" Initialization size cannot be less than 0：" + initialSize);
}
}
// Sentenced to empty
public boolean empty() {
return size == 0;
}
// Insert
public boolean add(E e) {
if (size == maxSize) {
throw new RuntimeException(" The queue is full , Cannot insert new element ！");
} else {
data[rear] = e;
rear = (rear + 1)%maxSize;
size ++;
return true;
}
}
// Go back to team leader , But don't delete
public E peek() {
if (empty()) {
throw new RuntimeException(" Empty queue exception ！");
} else {
return (E) data[front];
}
}
// Out of the team
public E poll() {
if (empty()) {
throw new RuntimeException(" Empty queue exception ！");
} else {
E value = (E) data[front]; // Keep the queue front The value of the element at the end
data[front] = null; // Release the queue front Element of end
front = (front+1)%maxSize; // Head of the team plus 1
size--;
return value;
}
}
// The queue length
public int length() {
return size;
}
// Empty the circular queue
public void clear(){
Arrays.fill(data, null);
size = 0;
front = 0;
rear = 0;
}
}

The chain storage structure of queue is realized

public class LinkQueue<E> {
// The node of the chain stack
private class Node<E> {
E e;
Node<E> next;
public Node() {
}
public Node(E e, Node next) {
this.e = e;
this.next = next;
}
}
private Node front;// Queue header , Allow deletion of
private Node rear;// Queue tail , Allow to insert
private int size; // Current queue length
public LinkQueue() {
front = null;
rear = null;
}
// Sentenced to empty
public boolean empty(){
return size==0;
}
// Insert
public boolean add(E e){
if(empty()){ // If the queue is empty
front = new Node(e,null);// Only one node ,front、rear All point to this node
rear = front;
}else{
Node<E> newNode = new Node<E>(e, null);
rear.next = newNode; // Let the tail node next Point to the new node
rear = newNode; // Take the new node as the new tail node
}
size ++;
return true;
}
// Go back to team leader , But don't delete
public Node<E> peek(){
if(empty()){
throw new RuntimeException(" Empty queue exception ！");
}else{
return front;
}
}
// Out of the team
public Node<E> poll(){
if(empty()){
throw new RuntimeException(" Empty queue exception ！");
}else{
Node<E> value = front; // Get the queue header element
front = front.next;// Give Way front The reference points to the next element of the original queue header element
value.next = null; // Release the original queue header element next quote
size --;
return value;
}
}
// The queue length
public int length(){
return size;
}
}

be based on LinkedList Implement queue structure

/**
* Use java.util.Queue Interface , The bottom layer is connected to a LinkedList（ deque ） example .
*/
import java.util.LinkedList;
import java.util.Queue;
public class QueueList<E> {
private Queue<E> queue = new LinkedList<E>();
// Inserts the specified element into this queue （ If it is immediately feasible and does not violate the capacity limit ）, Return on success true,
// If there is currently no space available , Throw out IllegalStateException.
public boolean add(E e){
return queue.add(e);
}
// obtain , But do not remove the header of this queue .
public E element(){
return queue.element();
}
// Inserts the specified element into this queue （ If it is immediately feasible and does not violate the capacity limit ）, When using a capacity limited queue ,
// This method is usually better than add(E), The latter may not be able to insert elements , Just throw an exception .
public boolean offer(E e){
return queue.offer(e);
}
// Get but do not remove the header of this queue ; If this queue is empty , Then return to null
public E peek(){
return queue.peek();
}
// Get and remove the header of this queue , If this queue is empty , Then return to null
public E poll(){
return queue.poll();
}
// Get and remove the header of this queue
public E remove(){
return queue.remove();
}
// Sentenced to empty
public boolean empty() {
return queue.isEmpty();
}
}