Java 实现栈和队列

public class LinkStack<E> {

//链栈的节点

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; //栈顶元素

private int size; //当前栈大小

public LinkStack(){

top = null;

}

//当前栈大小

public int length(){

return size;

}

//判空

public boolean empty(){

return size==0;

}

//入栈：让 top 指向新创建的元素，新元素的 next 引用指向原来的栈顶元素

public boolean push(E e){

top = new Node(e,top);

size ++;

return true;

}

//查看栈顶元素但不删除

public Node<E> peek(){

if(empty()){

throw new RuntimeException("空栈异常！");

}else{

return top;

}

}

//出栈

public Node<E> pop(){

if(empty()){

throw new RuntimeException("空栈异常！");

}else{

Node<E> value = top; //得到栈顶元素

top = top.next; //让 top 引用指向原栈顶元素的下一个元素

value.next = null; //释放原栈顶元素的 next 引用

size --;

return value;

}

}

}

基于 LinkedList 实现的栈结构：

import java.util.LinkedList;

/**

* 基于 LinkedList 实现栈

* 在 LinkedList 实力中只选择部分基于栈实现的接口

*/

public class StackList<E> {

private LinkedList<E> ll = new LinkedList<E>();

//入栈

public void push(E e){

ll.addFirst(e);

}

//查看栈顶元素但不移除

public E peek(){

return ll.getFirst();

}

//出栈

public E pop(){

return ll.removeFirst();

}

//判空

public boolean empty(){

return ll.isEmpty();

}

//打印栈元素

public String toString(){

return ll.toString();

}

}

队列的顺序存储结构实现

public class Queue<E> {

private Object[] data=null;

private int maxSize; //队列容量

private int front; //队列头，允许删除

private int rear; //队列尾，允许插入

//构造函数

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("初始化大小不能小于 0：" + initialSize);

}

}

//判空

public boolean empty(){

return rear==front?true:false;

}

//插入

public boolean add(E e){

if(rear== maxSize){

throw new RuntimeException("队列已满，无法插入新的元素！");

}else{

data[rear++]=e;

return true;

}

}

//返回队首元素，但不删除

public E peek(){

if(empty()){

throw new RuntimeException("空队列异常！");

}else{

return (E) data[front];

}

}

//出队

public E poll(){

if(empty()){

throw new RuntimeException("空队列异常！");

}else{

E value = (E) data[front]; //保留队列的 front 端的元素的值

data[front++] = null; //释放队列的 front 端的元素

return value;

}

}

//队列长度

public int length(){

return rear-front;

}

}

**循环队列**的顺序存储结构实现

import java.util.Arrays;

public class LoopQueue<E> {

public Object[] data = null;

private int maxSize; // 队列容量

private int rear;// 队列尾，允许插入

private int front;// 队列头，允许删除

private int size=0; //队列当前长度

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("初始化大小不能小于 0：" + initialSize);

}

}

// 判空

public boolean empty() {

return size == 0;

**《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】**

}

// 插入

public boolean add(E e) {

if (size == maxSize) {

throw new RuntimeException("队列已满，无法插入新的元素！");

} else {

data[rear] = e;

rear = (rear + 1)%maxSize;

size ++;

return true;

}

}

// 返回队首元素，但不删除

public E peek() {

if (empty()) {

throw new RuntimeException("空队列异常！");

} else {

return (E) data[front];

}

}

// 出队

public E poll() {

if (empty()) {

throw new RuntimeException("空队列异常！");

} else {

E value = (E) data[front]; // 保留队列的 front 端的元素的值

data[front] = null; // 释放队列的 front 端的元素

front = (front+1)%maxSize; //队首指针加 1

size--;

return value;

}

}

// 队列长度

public int length() {

return size;

}

//清空循环队列

public void clear(){

Arrays.fill(data, null);

size = 0;

front = 0;

rear = 0;

}

}

队列的链式存储结构实现

public class LinkQueue<E> {

// 链栈的节点

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;// 队列头，允许删除

private Node rear;// 队列尾，允许插入

private int size; //队列当前长度

public LinkQueue() {

front = null;

rear = null;

}