栈和队列都是特殊的线性表，它们的插入和删除操作都是事先规定好的。
第一节 栈
1 定义
栈（Stack）：只允许在一端进行插入和删除操作的线性表。
栈顶（Top）：允许进行插入和删除的那一端。
栈底（Bottom）：不允许进行插入和删除的那一端。
其操作的特性是后进先出（Last In First Out, LIFO）。
2 顺序栈
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时设一个指针（top）指示当前栈顶的位置。
public class MyArrayStack<T> {
private T[] data; // 存放元素的数组
private int top = -1; // 栈顶，初始值为-1
private int maxSize; // 栈容量
/**
* 初始化栈
* @param maxSize
*/
public MyArrayStack(int maxSize) {
this.maxSize = maxSize;
data = (T[]) new Object[this.maxSize];
}
/**
* 判栈空
* @return
*/
public boolean isEmpty() {
return top == -1;
}
/**
* 判栈满
* @return
*/
public boolean isFull() {
return top == this.maxSize - 1;
}
/**
* 入栈
* @param data
* @return
*/
public boolean push(T data) {
if (this.isFull()) {
throw new RuntimeException("栈满");
}
this.data[++this.top] = data;
return true;
}
/**
* 出栈
* @return
*/
public T pop() {
if (this.isEmpty()) {
throw new RuntimeException("栈空");
}
return this.data[this.top--];
}
/**
* 查看栈顶元素
* @return
*/
public T peek() {
if (this.isEmpty()) {
throw new RuntimeException("栈空");
}
return this.data[this.top];
}
}
3 链栈
采用链式存储的栈称为链栈。
链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。
通常采用单链表实现，并规定所有操作都是在单链表的表头进行的。
public class MyLinkedStack<T> {
private Node<T> head; // 栈头
private int length; // 栈长度
/**
* 初始化
*/
public MyLinkedStack() {
this.head = new Node<>();
this.length = 0;
}
/**
* 判栈空
* @return
*/
public boolean isEmpty() {
return this.head == null;
}
/**
* 获取栈长度
* @return
*/
public int size() {
return this.length;
}
/**
* 进栈
* @param data
* @return
*/
public boolean push(T data) {
Node<T> node = new Node<>(data);
boolean flag = false;
if (this.isEmpty()) {
this.head.next = node;
this.length++;
flag = true;
} else {
node.next = this.head.next;
this.head.next = node;
this.length++;
flag = true;
}
return flag;
}
/**
* 出栈
* @return
*/
public T pop() {
T data = null;
if (this.isEmpty()) {
throw new RuntimeException("栈空");
} else if (this.length == 1) {
data = (T) this.head.next.data;
this.head.next = null;
} else {
data = (T) this.head.next.data;
this.head.next = this.head.next.next;
}
return data;
}
/**
* 查看栈顶元素
* @return
*/
public T peek() {
T data = null;
if (this.isEmpty()) {
throw new RuntimeException("栈空");
} else {
data = (T) this.head.next.data;
}
return data;
}
public void print() {
if (this.isEmpty()) {
System.out.println("栈空");
} else {
Node<T> cur = this.head;
while (cur.next != null) {
cur = cur.next;
System.out.println(cur.data);
}
}
}
/**
* 栈元素
* @param <T>
*/
private class Node<T> {
private T data;
private Node next;
public Node() {
}
public Node(T data) {
this.data = data;
}
}
public static void main(String[] args) {
MyLinkedStack<String> list = new MyLinkedStack<>();
list.push("a");
list.push("b");
list.push("c");
list.print();
System.out.println("========");
System.out.println(list.pop());
System.out.println("=======");
list.print();
}
}
第二节 队列
1 定义
队列（Queue）也是一种操作受限的线性表，它只允许在表的一端进行插入，而在表的另一端进行删除。
向队列中插入元素称为入队；删除元素称为出队。其操作的特性是先进先出（First In First Out, FIFO）。
队头（Front)：允许删除的一端。
队尾（Rear）：允许插入的一端。
2 顺序存储的队列
队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针front和rear分别指示队列头元素和队尾元素的位置。将数组想象成一个环状的空间，可以充分利用数组的空间，称之为循环队列。
public class MyArrayQueue<T> {
private T[] arr; // 存放元素的数组
private int front; // 队头索引
private int rear; // 队尾索引
private int maxSize; // 队列容量
private int length; // 队长
/**
* 初始化队列
* @param maxSize
*/
public MyArrayQueue(int maxSize) {
this.maxSize = maxSize;
this.arr = (T[]) new Object[this.maxSize]; // 初始化数组
this.front = -1; // 初始化队头索引
this.rear = -1; // 初始化队尾索引
this.length = 0; // 初始化队长
}
/**
* 判队空
* @return
*/
public boolean isEmpty() {
return this.length == 0;
}
/**
* 判队满
* @return
*/
public boolean isFull() {
return this.length == this.maxSize;
}
/**
* 入队
* @param data
* @return
*/
public boolean enQueue(T data) {
if (this.isFull()) {
throw new RuntimeException("队满");
}
boolean flag = false;
if (isEmpty()) {
arr[this.rear + 1] = data;
this.rear = (this.rear + 1) % this.maxSize;
this.front = (this.front + 1) % this.maxSize;
this.length++;
flag = true;
} else {
arr[this.rear + 1] = data;
this.rear = (this.rear + 1) % this.maxSize;
this.length++;
flag = true;
}
return flag;
}
/**
* 出队
* @return
*/
public T deQueue() {
if (this.isEmpty()) {
throw new RuntimeException("队空");
}
T data = arr[this.front];
this.front = (this.front + 1) % this.maxSize;
this.length--;
return data;
}
public void print() {
if (this.isEmpty()) {
System.out.println("队空");
} else {
if (this.front < this.rear) {
for (int i = this.front; i <= this.rear; i++) {
System.out.println(arr[i]);
}
} else {
for (int i = this.front; i < this.maxSize; i++) {
System.out.println(arr[i]);
}
for (int i = 0; i <= this.rear; i++) {
System.out.println(arr[i]);
}
}
}
}
public static void main(String[] args) {
MyArrayQueue<String> queue = new MyArrayQueue<>(10);
queue.print();
queue.enQueue("a");
queue.enQueue("b");
queue.enQueue("c");
queue.enQueue("d");
System.out.println("===========");
queue.print();
System.out.println("===========");
System.out.println("出队："+queue.deQueue());
queue.print();
System.out.println("===========");
System.out.println("出队："+queue.deQueue());
queue.print();
}
}
京公网安备 11010502036488号