栈和队列（Java）
一.栈（Stack）
1.定义
栈是限定仅在表尾进行插入或删除操作的线性表
一般的表尾称为栈顶 表头称为栈底
栈具有“后进先出”的特点
2.对栈的模拟
栈主要具有以下功能：
-
push(Object item)：将元素item压入栈顶。
-
pop()：弹出栈顶元素，并将其从栈中删除。
-
peek()：返回栈顶元素，但不删除它。
-
isEmpty()：判断栈是否为空，返回布尔值。具体模拟代码我们可以用一个顺序表来实现如下
而在Java 编程应用idea中我们在使用时无需再进行模拟实现，可直接通过栈的实例化 然后直接进行调用栈的不同方法
实例化一个存储字符串类型的栈
则可直接stack.pop（）....进行调用方法
3.括号匹配问题
链接如下：
20. 有效的括号 - 力扣（LeetCode）
该题目就需要我们对于栈的功能的熟练掌握
需我们考虑三种括号不匹配情况从而考虑入栈和出栈的适配问题
以下是代码：
二.队列（Queue）
1.定义
与栈相反，队列是一种先进先出的线性表
插入一端成为队尾，删除一端称为队头
2.对队列的模拟
队列具有以下功能：
- 1. offer(E e)：添加元素到队列
2.poll()：移除并返回队列头部的元素 - 3. peek()：获取队列头部的元素，但不移除
4.isEmpty()：检查队列是否为空
以下队列的模拟我是借助链表来进行模拟实现
Java中idea也具有Queue队列 但队列是作为一个抽象类 所以
在实例化对象时需要向上转型
则可进行调用队列的方法：queue.offer();....
3.循环队列
循环队列是队列的一大重点
与队列不同的就是需要考虑队尾与对头的衔接
1.注意队空与队满的判断条件
队空的条件：q.front==q.rear;
队满的条件：(q.rear+1)%MaxSize==q.front;
2.代码详解
三.栈对队列的模拟以及队列对栈的模拟
1.队列对栈的模拟
225. 用队列实现栈 - 力扣（LeetCode）
class MyStack {
Queue<Integer>queue1 ;//申请第一个队列
Queue<Integer>queue2 ;//申请第二个队列
public MyStack() {
queue1=new LinkedList<>();
queue2=new LinkedList<>();
}
public void push(int x) {//在模拟栈入队时 找两个队列中非空的队列
if(!queue1.isEmpty()){
queue1.offer(x);
}
else if(!queue2.isEmpty()){
queue2.offer(x);
}
else{
queue1.offer(x);
}
}
public int pop() {//出队列时将非空队列中size-1个元素入另一个队列中，留下的即为模拟栈该出栈的元素
if(empty()){
return -1;
}
if(!queue1.isEmpty()){
int size=queue1.size();
for(int i=0;i<size-1;i++){
queue2.offer(queue1.poll());
}
return queue1.poll();
}
else{
int size=queue2.size();
for(int i=0;i<size-1;i++){
queue1.offer(queue2.poll());
}
return queue2.poll();
}
}
public int top() {
if(empty()){
return -1;
}
if(!queue1.isEmpty()){
int val=0;
int size=queue1.size();
for(int i=0;i<size;i++){
val=queue1.poll();
queue2.offer(val);
}
return val;
}
else{
int val=0;
int size=queue2.size();
for(int i=0;i<size;i++){
val=queue2.poll();
queue1.offer(val);
}
return val;
}
}
public boolean empty() {
return queue1.isEmpty()&&queue2.isEmpty();
}
}
2.栈对队列的模拟
232. 用栈实现队列 - 力扣（LeetCode）
注意结合栈的特性以两个栈来结合使队列的先进后出成功进行
class MyQueue {
public Stack <Integer> stack1;
public Stack <Integer> stack2;
public MyQueue() {
stack1=new Stack<>();
stack2=new Stack<>();
}
public void push(int x) {
if(empty()){
stack1.push(x);
}
if(stack1.isEmpty()){
stack2.push(x);
}
else{
stack1.push(x);
}
}
public int pop() {
if(empty()){
return -1;
}
if(!stack2.isEmpty()){
return stack2.pop();
}
else{
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
}
public int peek() {
if(empty()){
return -1;
}
if(stack1.isEmpty()){
int sz=stack2.size();
int num=0;
for(int i=0;i<sz;i++){
num=stack2.pop();
stack1.push(num);
}
return stack1.peek();
}
else{
int sz=stack1.size();
int num=0;
for(int i=0;i<sz;i++){
num=stack1.pop();
stack2.push(num);
}
return stack2.peek();
}
}
public boolean empty() {
return stack1.isEmpty()&&stack2.isEmpty();
}
}
