学到LinkedList，上课时老师提了一下代码实现栈和队列，面试可能会用上，就码了栈和队列两种实现方案。如有问题，希望指出。
一、栈
1.数组实现栈
/*
利用数组的方式实现一个栈
栈的特点: 存储数据 -- 先进后出(就像弹夹)
定义一个栈类:
成员变量:
1.存储数据的数组
2.栈容量
3.栈顶索引
成员方法:
1.压入数据方法
2.取出数据方法
*/
public class Stack {
private int[] data;
private int size;
private int stackTop = -1; //记录栈顶索引, 默认空, 索引-1
//构造方法
public Stack(int size) {
this.size = size;
this.data = new int[size];
}
public boolean push(int data) { //压栈方法
if (stackTop + 1 == size) {
System.out.println("栈已满");
return false;
}
this.data[++stackTop] = data; //栈顶默认值为-1,所以要先加后充当索引
return true;
}
public int pop() throws Exception { //出栈方法
if (stackTop == -1) {
throw new Exception("栈已空");
}
return data[stackTop--]; //返回数据后栈顶后移
}
}
class StackDemo {
public static void main(String[] args) throws Exception {
Stack s = new Stack(5);
//s.pop(); //报栈空
//压栈
for (int i = 1; i <= 5; i++) {
System.out.println(s.push(i));
}
//s.push(6); //报栈满
//出栈
for (int i = 0; i < 5; i++) {
System.out.println(s.pop());
}
}
}
2.LinkedList实现栈
import java.util.LinkedList;
/*
使用 LinkedList类 实现栈
LinkedList类: 底层是链表 特点: 查询慢, 增删快
特有功能:
public void addFirst(E e): 在该列表开头插入指定元素
public void addLast(E e): 将指定元素追加到此列表的末尾
public E getFirst(): 返回此列表中的第一个元素
public E getLast(): 返回此列表中的最后一个元素
public E removeFirst(): 从此列表中删除并返回第一个元素
public E removeLast(): 从此列表中删除并返回最后一个元素
*/
public class Stack {
private LinkedList<Integer> list = new LinkedList<>();
private int size; //栈的大小
//构造方法
public Stack(int size) {
this.size = size;
}
//压栈方法
public boolean push(int data) {
if (list.size() == size) {
System.out.println("栈已满");
return false;
}
list.addLast(data); //直接使用LinkedList的方法往后添加元素
return true;
}
//出栈方法
public int pop() throws Exception {
if (list.size() == 0) {
throw new Exception("栈已空");
}
return list.removeLast(); //删除并返回最后一个元素
}
}
class StackDemo {
public static void main(String[] args) throws Exception {
Stack s = new Stack(5);
//s.pop(); //报栈空
//压栈
for (int i = 1; i <= 5; i++) {
s.push(i);
}
//s.push(6); //报栈满
//出栈
for (int i = 0; i < 5; i++) {
System.out.println(s.pop());
}
//s.pop(); //报栈空
}
}
二、队列
1.数组实现队列
/*
数组实现队列
队列的特点: 存储数据 -- 先进先出(排队)
定义一个队列类:
成员变量:
1.存储数据的数组
2.队列容量
3.队列头部索引
4.队列尾部索引
成员方法:
1.加入数据方法
2.取出数据方法
*/
public class Queue {
private int[] data;
private int size;
private int queueLast = -1; //队列头索引
private int queueFirst = -1; //队列尾索引
//构造方法
public Queue(int size) {
this.size = size;
this.data = new int[size];
}
//入列
public boolean inQueue(int data) {
if (queueLast + 1 == size) {
System.out.println("队列已满");
return false;
}
this.data[++queueLast] = data;
return true;
}
//出列
public int outQueue() throws Exception {
if (queueFirst == queueLast) {
throw new Exception("队列已空");
}
return data[++queueFirst];
}
}
class QueueDemo {
public static void main(String[] args) throws Exception {
Queue q = new Queue(5);
//q.outQueue(); //报队列空
for (int i = 1; i <= 5; i++) {
q.inQueue(i);
}
//q.inQueue(6); //报队列满
for (int i = 0; i < 5; i++) {
System.out.println(q.outQueue());
}
//q.outQueue(); //报队列空
}
}
2.LinkedList实现队列
import java.util.LinkedList;
/*
LinkedList实现队列
*/
public class Queue {
private LinkedList<Integer> list = new LinkedList<>();
private int size;
//构造方法
public Queue(int size) {
this.size = size;
}
//入队列方法
public boolean inQueue(int data) {
if (list.size() == size) {
System.out.println("队列已满");
return false;
}
list.addLast(data); //从头添加元素
return true;
}
//出队列方法
public int outQueue() throws Exception {
if (list.size() == 0) {
throw new Exception("队列已空");
}
return list.removeFirst(); //从头删除元素并返回元素
}
}
class QueueDemo {
public static void main(String[] args) throws Exception {
Queue q = new Queue(5);
//q.outQueue(); //报队列空
for (int i = 1; i <= 5; i++) {
q.inQueue(i);
}
//q.inQueue(6); //报队列满
for (int i = 0; i < 5; i++) {
System.out.println(q.outQueue());
}
//q.outQueue(); //报队列空
}
}
网友评论