栈和队列都是动态集合,且在其上进行DELETE操作所移除的元素是预先设定的。在栈中,被删除的是最近插入的元素:栈实现的是一种后进先出(last-in,first-out,LIFO) 策略。在队列中,被删去的总是在队列中存在时间最长的那个元素:队列实现的是一种先进先出(first-in,first-out,FIFO) 策略。
栈
可以用一个数组A[1…n]来实现一个最多可容纳n个元素的栈。同时,需要有一个top属性,指向数组最新插入的元素,即栈顶元素。栈中包含的元素为S[1…top],其中S[1]是栈底元素。栈的示意图如下:
基于java数组简单实现的栈,代码如下:
/**
* 数据结构-栈
*/
public class MyStack {
/**
* 栈顶指针
*/
private int top;
/**
* 保存栈中数据的数组,默认初始容量为10
*/
private int[] data;
public MyStack() {
this.data = new int[10];
}
public MyStack(int cap) {
this.data = new int[cap];
}
/**
* 判断栈是否为空
*
* @return 是否为空
*/
public boolean isEmpty() {
return this.top == 0;
}
/**
* 入栈操作
*
* @param num 入栈的元素
*/
public void push(int num) {
// 保存数据的数组已满,需要扩容
if (this.top == this.data.length - 1) {
throw new Error("stack is full!");
}
this.top++;
this.data[this.top] = num;
}
/**
* 弹出栈顶元素
*
* @return 栈顶元素
*/
public int pop() {
if (isEmpty()) {
throw new Error("stack is under flow!");
}
this.top--;
return this.data[this.top + 1];
}
}
队列
队列有队头(head)和队尾(tail)。head属性指向队头元素,tail属性指向下一个新元素将要插入的位置。基于数组实现的队列,示意图如下:
基于java数组简单实现的队列,代码如下:
/**
* 数据结构-队列
*/
public class MyQueue {
/**
* 队头,指向队列的第一个元素
*/
private int head = 0;
/**
* 队尾,指向下一个新元素将要插入的位置
*/
private int tail = 0;
/**
* 队列中的元素个数
*/
private int size = 0;
/**
* 数据
*/
private final int[] data;
public MyQueue() {
this.data = new int[10];
}
public MyQueue(int cap) {
data = new int[cap];
}
public boolean isEmpty() {
return size == 0;
}
/**
* 入队操作
*
* @param num 将要入队的元素
*/
public void enQueue(int num) {
if (size == data.length) {
throw new Error("queue is full!");
}
data[tail] = num;
size++;
if (tail == data.length - 1) {
tail = 0;
} else {
tail++;
}
}
/**
* 出队操作
*
* @return 队头元素
*/
public int deQueue() {
if (size == 0) {
throw new Error("queue is empty!");
}
int x = data[head];
size--;
if (head == data.length - 1) {
head = 0;
} else {
head++;
}
return x;
}
}