题目描述：
实现一个栈的数据结构，使其具有以下方法：压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。
//利用数组 class MyStack{ private ArrayList arr; private int stackSize; public MyStack() { stackSize=0; arr=new ArrayList (); } //判断是否为空 boolean isEmpty(){ return stackSize==0; } //返回栈的大小 int size(){ return stackSize; } //返回栈顶元素 T top(){ if(isEmpty()){ return null; } return arr.get(stackSize-1); } //弹栈 T pop(){ if(stackSize>0){ return arr.get(--stackSize); }else{ System.out.println("栈已经为空"); return null; } } //压栈 void push(T item){ arr.add(item); stackSize++; } } public class ConStack { public static void main(String[] args) { MyStack stack=new MyStack<>(); stack.push(1); System.out.println("栈顶元素为："+stack.top()); System.out.println("栈大小为："+stack.size()); stack.pop(); System.out.println("弹栈成功"); stack.pop(); } }
//链表法 class LNode2.如何实现队列{ T data; LNode next; } class myStack { private LNode pHead; public myStack(){ pHead =new LNode (); pHead.data=null; pHead.next=null; } //判断栈是否为空 boolean empty(){ return pHead==null; } //获取栈中的元素个数 int size(){ int size=0; LNode p=pHead.next; while (p!=null){ p=p.next; size++; } return size; } //入栈，把e放到栈顶 void push(T e){ LNode p=new LNode<>(); p.data=e; p.next=pHead.next; pHead.next=p; } //出栈,同时返回栈顶元素 T pop(){ LNode tmp=pHead.next; if(tmp!=null){ pHead.next=tmp.next; return tmp.data; } System.out.println("栈已经为空"); return null; } //获取栈顶元素 T top(){ if(pHead.next!=null){ return pHead.next.data; } System.out.println("栈已经为空"); return null; } } public class ListTest { public static void main(String[] args) { myStack stack=new myStack<>(); stack.push(1); System.out.println("栈顶元素为："+stack.pop()); System.out.println("栈大小为："+stack.size()); stack.pop(); System.out.println("弹栈成功"); stack.pop(); } }
题目描述：
实现一个队列的数据结构，使其具有入队列、出队列、查看队列首尾元素、查看队列大小等功能。
import java.util.ArrayList; class MyQueue{ private ArrayList arr=new ArrayList<>(); private int front;//队列头 private int rear;//队列尾 public MyQueue(){ front=0; rear=0; } //判断队列是否为空 public boolean isEmpty(){ return front==rear; } //返回队列的大小 public int size(){ return rear-front; } //返回队列首元素 public T getFront(){ if(isEmpty()){ return null; } return arr.get(front); } //返回队列尾元素 public T getRear(){ if(isEmpty()){ return null; } return arr.get(rear-1); } //删除队列头元素 public void deleteQueue(){ if(rear>front){ front++; }else { System.out.println("队列已经为空"); } } //把新元素加入队列尾 public void joinQueue(T item){ arr.add(item); rear++; } } public class ArrayQueue { public static void main(String[] args) { MyQueue queue =new MyQueue<>(); queue.joinQueue(1); queue.joinQueue(2); queue.joinQueue(3); System.out.println("队列头元素为："+queue.getFront()); System.out.println("队列尾元素为："+queue.getRear()); System.out.println("队列大小为："+queue.size()); } }
//利用链表实现队列 class LNode3.如何设计一个排序系统{ T data; LNode next; } class MyQueue { private LNode pHead; private LNode pEnd; //分配头结点 public MyQueue(){ pEnd=pHead=null; } //判断队列是否为空 boolean empty(){ if(pHead==null){ return true; }else { return false; } } //元素个数 int size(){ int size=0; LNode p=pHead; while (p!=null){ p=p.next; size++; } return size; } //添加列尾 void enQueue(T e){ LNode p=new LNode<>(); p.data=e; p.next=null; if(pHead==null){ pHead=pEnd=p; }else { pEnd.next=p; pEnd=p; } } //删除队列元素 void deQueue(){ if(pHead==null) System.out.println("出队列失败，队列已经为空"); pHead=pHead.next; if(pHead==null) pEnd=null; } //获取队列首位元素 T getFront(){ if(pHead==null){ System.out.println("获取队列首元素失败，队列已经为空"); return null; } return pHead.data; } //队列尾元素 T getBack(){ if(pEnd==null){ System.out.println("获取队列尾元素失败，队列已经为空"); return null; } return pEnd.data; } } public class QueueList { public static void main(String[] args) { MyQueue queue=new MyQueue<>(); queue.enQueue(1); queue.enQueue(2); System.out.println("队列头元素为："+queue.getFront()); System.out.println("队列尾元素为："+queue.getBack()); System.out.println("队列大小为："+queue.size()); } }
题目描述：
设计一个排队系统，能够让每个进入队的用户都能看到自己在队列中所处的位置和变化，队可能随时有人加入和退出；当有人退出影响到用户的位置排名时需要及时反馈到用户。
package queue;
import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
class User {
private int id;
private String name;
private int seq;
public User(int id, String name) {
this.id = id;
this.name = name;
this.seq = seq;
}
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getSeq() {
return seq;
}
public void setSeq(int seq) {
this.seq = seq;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()) {
return false;
}
User user = (User) o;
return id == user.id && seq == user.seq && Objects.equals(name, user.name);
}
@Override
public int hashCode() {
return Objects.hash(id, name, seq);
}
@Override
public String toString() {
return "User{" +
"id=" + id +
", name='" + name + ''' +
", seq=" + seq +
'}';
}
}
class MyQueue {
private Queue q = new LinkedList<>();
//进入队列尾部
public void enQueue(User u) {
u.setSeq(q.size() + 1);
q.add(u);
}
//对头 出队列
void deQueue() {
q.poll();
updataSep();
}
//队列中的人随机离开
void deQueue(User u) {
q.remove(u);
updataSep();
}
//出列后更新队列中每个人的序列
void updataSep() {
int i = 1;
for (User u : q) {
u.setSeq(i++);
}
}
//打印队列的信息
void printList() {
for (User u : q) {
System.out.println(q);
}
}
}
public class SoftSystem {
public static void main(String[] args) {
User u1=new User(1,"User1");
User u2=new User(2,"User2");
User u3=new User(3,"User3");
User u4=new User(4,"User4");
MyQueue queue=new MyQueue();
//存入队列
queue.enQueue(u1);
queue.enQueue(u2);
queue.enQueue(u3);
queue.enQueue(u4);
//删除队列头和队列u3
queue.printList();
queue.deQueue();
queue.deQueue(u3);
queue.printList();
}
}
4.如何实现LRU缓存方案
题目描述：
LRU是Least Recently Used 的缩写，它的意思是“最近最少使用”。LRU缓存就是使用这种原理实现，简单地说，就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉。常用于页面置换算法，是为虚拟页式存储管理中常用的算法。如何实现LRU缓存方案？
package queue;
import java.util.ArrayDeque;
import java.util.HashSet;
public class Test1 {
public static void main(String[] args) {
LRU lru = new LRU(3);
lru.accessPage(1);
lru.accessPage(2);
lru.accessPage(5);
lru.accessPage(1);
lru.accessPage(6);
lru.accessPage(7);
lru.printQueue();
}
}
class LRU {
private int cacheSize;
private ArrayDeque queue = new ArrayDeque<>();//双向链
private HashSet hashSet = new HashSet<>();//哈希表
public LRU(int cacheSize) {
this.cacheSize = cacheSize;
}
private boolean isQueueFull() {
return queue.size() == cacheSize;
}
private void enqueue(int pageNum) {
if (isQueueFull()) {
hashSet.remove(queue.getLast());
queue.pollLast();
}
queue.addFirst(pageNum);
}
public void accessPage(int pageNum) {
if (!hashSet.contains(pageNum)) {
enqueue(pageNum);
} else if (pageNum != queue.getFirst()) {
queue.remove(pageNum);
queue.addFirst(pageNum);
}
}
public void printQueue() {
while (!queue.isEmpty()) {
System.out.print(queue.pop() + "");
}
}
}
5.如何从数组中找出满足a+b=c+d的两个数对
题目描述：
给定一个数组，找出数组中是否有两个数对（a, b）和（c, d），使得a+b=c+d，其中a、b、c和d是不同的元素。如果有多个答案，打印任意一个即可。例如，给定数组：{3, 4, 7, 10, 20, 9, 8}，可以找到两个数对（3, 8）和（4, 7），使得3+8=4+7。
补充：拓扑排序是对一个有向图构造拓扑序列，解决工程是否能顺利进行的问题。构造时有 2 种结果：
此图全部顶点被输出：说明说明图中无「环」存在， 是 AOV 网
没有输出全部顶点：说明图中有「环」存在，不是 AOV 网
import java.util.HashMap;
public class ArrayElements {
boolean findPairs(int arr[]){
HashMap sumPair=new HashMap<>();
int n= arr.length;
for(int i=0;i
