题目描述：
实现一个栈的数据结构，使其具有以下方法：压栈、d栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数。
//利用数组
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);
}
//d栈
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("d栈成功");
stack.pop();
}
} //链表法
class LNode{
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("d栈成功");
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 LNode{
T data;
LNode next;
}
class MyQueue{
private LNodepHead;
private LNode pEnd;
//分配头结点
public MyQueue(){
pEnd=pHead=null;
}
//判断队列是否为空
boolean empty(){
if(pHead==null){
return true;
}else {
return false;
}
}
//元素个数
int size(){
int size=0;
LNodep=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;
/*1、offer()和add()的区别
add()和offer()都是向队列中添加一个元素。但是如果想在一个满的队列中加入一个新元素，调用 add() 方法就会抛出一个 unchecked 异常，而调用 offer() 方法会返回 false。可以据此在程序中进行有效的判断！
2、peek()和element()的区别
peek()和element()都将在不移除的情况下返回队头，但是peek()方法在队列为空时返回null，调用element()方法会抛出NoSuchElementException异常。
3、poll()和remove()的区别
poll()和remove()都将移除并且返回对头，但是在poll()在队列为空时返回null，而remove()会抛出NoSuchElementException异常。
*/
/**
* @author 龙御修
*/
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();
}
}
题目描述：
LRU是Least Recently Used 的缩写，它的意思是“最近最少使用”。LRU缓存就是使用这种原理实现，简单地说，就是缓存一定量的数据，当超过设定的阈值时就把一些过期的数据删除掉。常用于页面置换算法，是为虚拟页式存储管理中常用的算法。如何实现LRU缓存方案？
package queue;
import java.util.ArrayDeque;
import java.util.HashSet;
/**
* @author tarena
*/
public class Test1 {
public static void main(String[] args) {
/*设置缓存大小*/
LRU lru = new LRU(3);
/*访问page*/
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;
}
/*把页号为PageNum的也缓存到队列中，同时也添加都Hash表中*/
private void enqueue(int pageNum) {
/*如果队列满了,需要删除队尾的缓存的页*/
if (isQueueFull()) {
hashSet.remove(queue.getLast());
queue.pollLast();
}
queue.addFirst(pageNum);
}
/*当访问某一个page的时候会调用这个函数，对于访问的page有两种情况：
* 1.如果page在缓存队列中，直接把这个结点移动到队首
* 2.如果page不在缓存队列中，把这个page缓存到队首*/
public void accessPage(int pageNum) {
/*page不在缓存队列中，把它缓存到队首*/
if (!hashSet.contains(pageNum)) {
enqueue(pageNum);
/*page已经在缓存队列中了,移动到队首*/
} else if (pageNum != queue.getFirst()) {
queue.remove(pageNum);
queue.addFirst(pageNum);
}
}
public void printQueue() {
while (!queue.isEmpty()) {
System.out.print(queue.pop() + "");
}
}
} 题目描述：
给定一个数组，找出数组中是否有两个数对（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;
/**
* @author 龙御修
* @create 2022-05-01 16:23
*/
public class ArrayElements {
boolean findPairs(int arr[]){
/*键为数对和和，值为数对*/
HashMap sumPair=new HashMap<>();
int n= arr.length;
/*遍历数组中所有可能的数对*/
for(int i=0;i 欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）