首页 > 其他分享 >栈(Stack)和队列(Queue)

栈(Stack)和队列(Queue)

时间:2022-08-24 01:12:40浏览次数:57  
标签:qu1 return 队列 public Queue int isEmpty Stack

一  栈(Stack):一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一 端称为栈顶,另一端称为栈底。栈中的数据元素遵守先进后出。    

压栈:栈的插入操作也叫入栈,进栈,压栈。 出栈:栈的删除操作也叫出栈。
  方法:
stack.push();  压栈 stack.pop();  查看栈顶元素并删除 stack.peek(); 查看栈顶元素不删除 stack.empty  栈是否为空
    二  队列(Queue):只允许在一端进行插入数据,另一端进行删除数据操作的特殊线性表,队列中的元素遵循先进先出。    
入队列:队尾插入; 出队列:队头删除;
方法: 常用:
Queue.offer(); 压栈 Queue.poll();  查看栈顶元素并删除 Queue.peek();  查看栈顶元素不删除
 
抛异常: Queue.add();  压栈 Queue.remove();  查看栈顶元素并删除 Queue.element();   查看栈顶元素不删除  
  三  双端队列(Deque):两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元 素可以从队头出队和入队,也可以从队尾出队和入队。  
方法:  常用:                                            抛异常: 入队列:队首:  offerFirst();                         addFirst();                    队尾:offerLast();                        addLast();      
出队列: 队首:   pollFirst();                         removeFirst();                队尾: pollLast();                         removeLast();  
获取元素: 队首:   peekFirst();                    getFirst();                      队尾:peekLast();                     getLast(); 
         

 

 

试题

1    括号匹配问题



class Solution {
    public boolean isValid(String s) {
         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()){
                    System.out.println("右括号多");
                    return false;
                }
                    char top=stack.peek();
                    if (top=='('&&ch==')'||top=='['&&ch==']'||top=='{'&&ch=='}'){
                        stack.pop();
                    }else {
                        System.out.println("左右括号不匹配");
                        return false;
                    }
            }
        }
        if (!stack.empty()){
            System.out.println("左括号多");
            return false;
        }
        return true;
    }
} 


 

 2 循环队列


class MyCircularQueue {
public int[] elem;
public int front; //队头下标
public int rear; //队尾下标

public MyCircularQueue(int k) {
this.elem=new int[k+1];
}

public boolean enQueue(int value) {
if (isFull()) return false;
this.elem [rear]=value;
rear=(rear+1)% elem.length;
return true;
}

public boolean deQueue() {
if (isEmpty()) return false;
front=(front+1)% elem.length;
return true;
}
//队首获取元素
public int Front() {
if (isEmpty())return -1;
return elem[front];
}
//队尾获取元素
public int Rear() {
if (isEmpty())
return -1;
int index = -1;
if (rear==0){
index= elem.length-1;
}else {
index= rear-1;
}
return elem[index];

}

public boolean isEmpty() {
return front==rear;
}

public boolean isFull() {
if ((rear+1)%elem.length==front){
return true;
}
return false;
}

 

 3 队列实现栈

public class MinStack {
    public Queue<Integer> qu1;
    public Queue<Integer> qu2;
    public MinStack() {
       qu1=new LinkedList<>();
       qu2=new LinkedList<>();
    }

    public void push(int x) {
        if (qu1.isEmpty()){
            qu1.offer(x);
        }else if (qu2.isEmpty()){
            qu2.offer(x);
        }
        qu1.offer(x);
    }

    public int pop() {
        if (empty())return -1;
        if (!qu1.isEmpty()){
            int size=qu1.size()-1;
            for (int i = 0; i < size; i++) {
                int val =qu1.poll();
                qu2.offer(val);
            }
            return qu1.poll();
        }
        if (!qu2.isEmpty()){
            int size=qu2.size()-1;
            for (int i = 0; i < size; i++) {

                int val=qu2.poll();
                qu1.offer(val);
            }
            return qu2.poll();
        }
        return -1;
    }

    public int top() {
        if (empty())return -1;
        int val=-1;

        if (!qu1.isEmpty()){
            int size= qu1.size();
            for (int i = 0; i<size; i++) {
                 val =qu1.poll();
                 qu2.offer(val);
            }
            return val;
        }

        if (!qu2.isEmpty()){
            int size= qu2.size();
            for (int i = 0; i < size; i++) {
               val=qu2.poll();
               qu1.offer(val);
            }
            return val;
        }
        return -1;
    }

    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }


}

 

 

 4  栈实现队列

class MyQueue {
    public Stack<Integer>stack1;
    public Stack<Integer>stack2;

    public MyQueue() {
        stack1 =new Stack<>();
        stack2 =new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (empty())return -1;
        while (stack2.isEmpty()){
            if (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if (empty())return-1 ;
        while (stack2.isEmpty()){
            if (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() &&stack2.empty();
    }

 

 

 

 

标签:qu1,return,队列,public,Queue,int,isEmpty,Stack
From: https://www.cnblogs.com/lbwboke/p/16618398.html

相关文章

  • 2022-8-23 剑指offer-优先队列(堆)-每日一题-太难不写了
    剑指OfferII061.和最小的k个数对难度中等44收藏分享切换为英文接收动态反馈给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。定义......
  • 队列结构
     什么是队列?队列(Queue),它是一种运算受限的线性表,先进先出(FIFOFirstInFirstOut)队列是一种受限的线性结构受限之处在于它只允许在表的前端(front)进行删除操......
  • 622. 设计循环队列
    622.设计循环队列设计你的循环队列实现。循环队列是一种线性数据结构,其操作表现基于FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓......
  • C#之List、Queue、Stack使用EnsureCapacity方法预设数组大小
    简介 List、Queue和Stack集合中的EnsureCapacity方法预设数组大小。为什么以及何时使用EnsureCapacity方法这里我们将首先了解为什么需要使用这种方法以及何时使......
  • C#-队列 Queue/栈 Stack
    队列先进先出,相当于排队买车票//队列Queue<string>queueList=newQueue<string>();//入队queueList.Enqueue("张三");queueList.Enqueue("李四");queueList.En......
  • After Effects 教程,如何在 After Effects 中更改渲染队列中的设置?
    欢迎观看AfterEffects中文版教程,小编带大家学习AdobeAfterEffects的基本工具和使用技巧,了解如何在AE中使用渲染队列更改设置。使用「渲染队列」创建「渲染」时,可能......
  • qt实现父界面中多子界面间的切换---stackWidget
    qt实现父界面中多子界面间的切换---stackWidget1.创建新项目2.项目命名3.起类名起类名之前的步骤可直接next即可。4.打开ui5.拖入控件6.添加新页该步可跳过,当......
  • After Effects 教程,如何在 After Effects 中使用渲染队列?
    欢迎观看AfterEffects教程,小编带大家学习ae视频软件的基本工具和使用技巧,了解如何在AE中使用渲染队列。在「时间轴」中单击,激活「时间轴」面板。按下空格键,查看项目,......
  • 2022-8-22 剑指offer-优先队列-每日一题-二叉树-搜索/递归
    剑指OfferII060.出现频率最高的k个数字难度中等36收藏分享切换为英文接收动态反馈给定一个整数数组 nums 和一个整数 k ,请返回其中出现频率前 k 高的元......
  • VMware虚拟机迁移到openstack平台
    1.检查内核是否支持virtio驱动grep-ivirtio/boot/config-$(uname-r)2.如果内核没有virtio驱动需要指定virtio驱动cp/boot/initramfs-$(uname-r).img/boot/initr......