目录
一、栈的理解和使用
1.1什么是栈
?栈是一种特殊的线性表只能允许在一段进行插入和删除操作，进行插入和删除操作的一端叫栈顶，另一端称为栈底。
?出栈和入栈就是将元素从栈顶拿出或者拿入。
1.2栈的简单实现?
public class MyStack01 {
int[] elem;
int usedSize;
public MyStack01(){
this.elem=new int[10];
this.usedSize=0;
}
public boolean isFull(){
if(this.elem.length==usedSize){
return true;
}
return false;
}
//添加
public void push(int val){
if(isFull()){
this.elem=Arrays.copyOf(elem,2*elem.length);
}
this.elem[this.usedSize]=val;
this.usedSize++;
}
public boolean isEmpty(){
return this.usedSize==0;
}
//出栈
public int pop(){
if(isEmpty()){
System.out.println("栈中没有元素");
return -1;
}
int val=this.elem[usedSize-1];
usedSize--;
return val;
}
//查找栈顶元素
public int peek(){
if(isEmpty()){
System.out.println("栈中没有元素");
return -1;
}
return this.elem[usedSize-1];
}
}1.3栈中方法的介绍
| 方法 | 介绍 |
| push（） | 压栈操作 |
| pop（） | 出栈操作 |
| peek（） | 查看栈顶元素 |
| empty（） | 栈是否为空 |
?
1.4?关于栈的练习
括号匹配问题：题目。
给定一个只包括?'('，')'，'{'，'}'，'['，']'?的字符串?s?，判断字符串是否有效。
public boolean isValid(String s) {
if(s.length()==0||s==null) return false;
Stack<Character> stack=new Stack<>();
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
if(ch=='('||ch=='{'||ch=='['){
stack.push(ch);
}else{
if(stack.empty()){
return false;
}
char ch01=stack.peek();
if((ch==')'&&ch01=='(')||(ch=='}'&&ch01=='{')||(ch==']'&&ch01=='[')){
stack.pop();
}else{
return false;
}
}
}
return stack.empty();
}二、队列的理解和使用?
2.1什么是队列
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 。入队列：进行插入操作的一端称为队尾。出队列：进行删除操作的一端称为队头。
2.2对于简单队列的实现?
public class MyQueue {
Node head;
Node last;
int usedSize;
//入队列
public void offer(int val) {
Node node=new Node(val);
if(head==null){
this.head=node;
this.last=node;
}else{
this.last.next=node;
this.last=node;
}
}
//出对头元素
public int poll() {
if(isEmpty()){
throw new RuntimeException("队列为空");
}
int val=this.head.data;
if(this.head.next==null){
this.head=null;
this.last=null;
}else{
this.head=this.head.next;
}
return val;
}
//得到对头元素
public int peek() {
if(isEmpty()){
throw new RuntimeException("队列为空");
}
return this.head.data;
}
public boolean isEmpty() {
return this.usedSize==0;
}
public int size() {
return this.usedSize;
}
}?2.3队列中方法的介绍
| 抛出异常 | 返回特殊值 | |
| 入队列 | add() | offer() |
| 出队列 | remove() | poll() |
| 查看队首元素 | element() | empty() |
?
三、循环队列
?循环队列是指用数组来实现队列（一般队列是用链表来实现的）。
我们通过head指向第一个和last指向最后一个的后面，两个指向来编写。
public class MyQueue01 {
int[] elem;
int usedSize;
int head;
int last;
public MyQueue01(int k) {
this.elem=new int[k+1];
}
//向循环队列插入一个元素。如果成功插入则返回真
public boolean enQueue(int value) {
if(isFull()) return false;
this.elem[this.last]=value;
this.last=(this.last+1)%this.elem.length;
return true;
}
//从循环队列中删除一个元素。如果成功删除则返回真。
public boolean deQueue() {
if(isEmpty()) return false;
this.head=(this.head+1)%this.elem.length;
return true;
}
//从队首获取元素。如果队列为空，返回 -1 。
public int Front() {
if(isEmpty()) return -1;
int val=this.elem[this.head];
return val;
}
//获取队尾元素。如果队列为空，返回 -1 。
public int Rear() {
if(isEmpty()) return -1;
if(this.last==0){
return this.elem[this.elem.length-1];
}
return this.elem[this.last-1];
}
//检查循环队列是否为空。
public boolean isEmpty() {
if(this.head==this.last){
return true;
}
return false;
}
//检查循环队列是否已满。
public boolean isFull() {
if((this.last+1)%elem.length==this.head){
return true;
}
return false;
}
}