本次我们介绍基础算法中的栈和队列,我们会从下面几个角度来介绍:
- 栈和队列简述
- 模拟栈
- 模拟队列
栈和队列简述
首先我们要简单了解一下栈和队列:
- 栈:数据元素先进后出
- 队列:数据元素先进先出
我们分别给出展示图:
模拟栈
我们下面给出用数组模拟栈的写法:
public class Stack {
// 固定长度
final int N = 1000010;
// 栈(栈元素从下标1开始)
int[] stk = new int[N];
// 栈指针(永远指在栈顶)
int t = 0;
public static void main(String[] args) {
// 测试代码
}
/**
* 推入操作
* @param x
*/
public void push(int x){
stk[++t] = x;
}
/**
* 弹出操作
*/
public void pop(){
t--;
}
/**
* 判断是否为空
*/
public boolean isEmpty(){
if (t > 0){
return false;
}else {
return true;
}
}
/**
* 返回栈顶元素
* @return
*/
public int stkTop(){
return stk[t];
}
}
模拟队列
我们下面给出用数组模拟队列的写法:
public class Queue {
// 定义一个队列大小
final int N = 100010;
// 定义队列
int[] queue = new int[N];
// 定义队头和队尾
int head = 1;
int tail = 0;
public static void main(String[] args) {
// 测试代码
}
/**
* 添加操作
* @param x
*/
public void add(int x){
queue[++tail] = x;
}
/**
* 弹出操作
*/
public void pop(){
if (head <= tail){
// 说明有值,可以删除
head++;
}else {
// 说明无值,无法删除
System.out.println("无法删除");
}
}
/**
* 得到队头元素
* @return
*/
public int getHead(){
return queue[head];
}
/**
* 得到队尾元素
*/
public int getTail(){
return queue[tail];
}
/**
* 是否为空
*/
public boolean isEmpty(){
if (head <= tail){
return false;
}else {
return true;
}
}
/**
* 队列长度
*/
public int getLong(){
return tail-head+1;
}
}
结束语
好的,关于数据结构篇的栈和队列就介绍到这里,希望能为你带来帮助~
附加
《表达式求值》问题由于涉及数,哈希等内容在后续会在该文章补充~