数据结构——栈和队列

一、栈 (Stack)

        栈是一种后进先出(LIFO, Last In First Out)的线性数据结构，只允许在一端进行插入和删除操作，这一端被称为栈顶(top)，另一端称为栈底(bottom)。

1、基本操作

• isFull(判断栈满)：判断栈是否满

• isEmpty(判断栈空)：判断栈是否为空

• push(入栈)：将元素压入栈顶

• pop(出栈)：移除并返回栈顶元素

• peek(查看栈顶)：返回但不移除栈顶元素

• size(大小)：返回栈中元素数量

2、实现方式

• 数组实现：使用固定大小或动态扩容的数组

• 链表实现：使用单链表，头节点作为栈顶

3、应用场景

1. 函数调用栈：程序执行时保存函数调用关系

2. 表达式求值：处理括号匹配、后缀表达式

3. 撤销操作：如文本编辑器的撤销功能

4. 浏览器历史记录：前进后退功能

5. 递归实现：递归函数调用转换为迭代实现

6. 深度优先搜索（DFS）算法

二、队列 (Queue)

        队列是一种先进先出(FIFO, First In First Out)的线性数据结构，允许在一端(队尾/rear)插入元素，在另一端(队头/front)删除元素。

1、基本操作

• isFull(判断队满)：判断队列是否满

• isEmpty(判断队空)：判断队列是否为空

• add(入队)：在队尾添加元素

• remove(出队)：移除并返回队头元素

• front(查看队头)：返回但不移除队头元素

• size(大小)：返回队列中元素数量

2、实现方式

• 数组实现：使用循环数组解决空间浪费问题

• 链表实现：使用单链表，头节点作为队头，尾节点作为队尾

3、队列扩展

1. 双端队列(Deque)：两端都可以进行插入和删除操作

2. 优先队列(Priority Queue)：元素按优先级出队

3. 循环队列(Circular Queue)：利用数组实现的高效队列

4. 阻塞队列(Blocking Queue)：线程安全的队列实现

4、应用场景

1. 任务调度：CPU任务调度

2. 消息队列：系统间异步通信

3. 打印队列：打印机任务管理

4. 广度优先搜索（BFS）算法：图的广度优先搜索

5. 缓存系统：如Redis等内存数据库

6. 客服中心的来电处理

三、栈和队列的比较

四、代码示例（Java实现）

1、Java实现栈

public class Stack {

	private int[] arr=new int[5];
//	栈顶
	private int top=-1;
//	判断栈满
	public boolean isFull() {
		return top==arr.length-1;
	}
//	判断栈空
	public boolean isEmpty() {
		return top==-1;
	}
	
//	入栈
	public void push(int num) {
		if(isFull()) {
			System.out.println("栈满");
			return;
		}
		top++;
		arr[top]=num;
	}
	
//	出栈
	public int pop() {
		if(isEmpty()) {
			System.out.println("栈空");
			throw new RuntimeException("栈空");
		}
		int res=arr[top];
		top--;
		return res;
	}	
}

2、Java实现队列

public class Queue {

	private int[] arr=new int[5];
	private int front=-1;
	private int rear=-1;
	
//	队满
	public boolean isFull() {
		return rear==arr.length-1;
	}
//	队空
	public boolean isEmpty() {
		return rear==front;
	}
//	入队
	public void add(int value) {
		if(isFull()) {
			System.out.println("队满");
			return;
		}
		rear++;
		arr[rear]=value;
	}
//	出队
	public int remove() {
		if(isEmpty()) {
			System.out.println("队空");
			throw new RuntimeException("队空");
		}
		front++;
		return arr[front];
	}
}