Java数据结构之栈和队列
栈
相关概念
- 栈是一种特殊的线性表
- 只允许在固定的一端进行插入和删除元素操作。
- 进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。
- 原则:后进先出LIFO(Last In First Out)
- 压栈:栈的插入操作,入数据在栈顶
- 出栈:栈的删除操作,出数据也在栈顶
栈的实现
- 一头进出
- 栈一般可以使用数组或链表实现,数组结构更优
class Stack{
int[] array;
int top;
}
//顺序表实现栈
Stack(){
this.array = new int[100];
this.top = top;
}
/**
* 压入一个数据,插入一个数据
* 压栈
* @param v
*/
public void push(int v){
this.array [this.top++] = v;
}
/**
* 弹栈,出栈
* 先进后出
* @return 栈顶元素
*/
public int pop() {
return this.array[--this.top];
}
/**
* 查看栈顶元素
* @return 栈顶元素
*/
public int peek() {
return this.array[this.top - 1];
}
/**
* 返回栈的元素个数
* @return 栈顶元素
*/
public int size() {
return this.top;
}
/**
* 判断栈空
* @return
*/
public boolean isEmpty() {
return this.top == 0;
}
队列
相关概念
- 队列只允许队尾插入数据,队头删除数据
- 队列具有先进先出FIFO(First In First One)原则
队列的实现
- 一头进另一头出
- 队列可利用数组或链表结构实现,链表结构更优
class Node{
int value;
int next;
}
Node head;
Node last;
Queue(){
this.head = this.last = null;
}
/**
* 将数据插到队尾
* @param v
*/
public void push(int v){
Node node= new Node();
node.val = v;
node.next = null;
if(this.head == null){
this.head = this.last = node;
} else {
this.last.next = this.last = node;
}
}
/**
* 将数据从队头删除
* @return v = this.head.val
*/
public int pop() {
int v = this.head.val;
this.head = this.head.next;
if (this.head == null) {
this.last = null;
}
return v;
}
/**
* 返回队首元素
* @return
*/
public int front() {
return this.head.val;
}
在这里简单介绍一下循环队列
- 循环队列其操作表现基于FIFO(先进先出)原则并且队尾被链接在队首之后形成一个循环,也被称作“环形缓冲器”
- 循环队列的好处在于我们可以利用这个队列之前用过的空间,在一个普通队列里,一旦一个队列满了就不能再插入下一个元素了,即使这个队列前面还有空间。但是使用循环队列,我们能使用这些空间取存储新的值
循环队列的实现
- 定义size
- front指向一个进队列的第一个元素,rear指向队尾元素的下一个可用空间
- 当size = 0,front和rear指向同一个地方,代表此时队列为null
- 当size != 0时,front和rear指向同一个地方,代表此时队列为full
- 当rear指向的下一个可用空间的下一个空间为队首元素
-如图,当队列仅剩下一个可用空间(图中rear所指处)的时候,就不再允许元素进队列,以此判空rear