数据结构《栈和队列》

🕗 发布于 2024-11-17 07:31 数据结构 java 开发语言

文章目录

一、什么是栈？
- 1.1 栈的模拟实现
- 1.2 关于栈的例题
二、什么是队列？
- 2.2 队列的模拟实现
- 2.2 关于队列的例题
总结

提示：关于栈和队列的实现其实很简单，基本上是对之前的顺序表和链表的一种应用，代码部分也不难。主要的是对栈和队列的实际运用。

一、什么是栈？

可以理解为一个竖过来的数组、顺序表，同时这个数组只能将末尾的元素先推出来，再推出来前面的元素，也就是我们所说的，先进后出、后进先出。
在这里插入图片描述
栈的实例化

Stack<E> stack = new Stack<>();

1.1 栈的模拟实现

在这里插入图片描述

自定义的接口，规范自定义的类,便于模拟实现

public interface IStack {
    //放入元素
    int push(int a);
    //推出栈顶元素
    int pop();
    //查看栈顶元素
    int peek();
    //栈是否为空
    boolean isEmpty(int[] array);
    //栈中的元素个数
    int size();
    //栈中寻找某个元素距离栈顶的距离
    int search(int a);
}

push(int a) — 将元素放入栈中

public int push(int a) {
        isFull(array);
        array[useSide++] = a;
        return a;
    }

在这里插入图片描述

peek() — 查看栈顶元素

public int peek() {
        try {
            if(isEmpty(array)){
                throw new EmptyException("空数组读取异常");
            }
        }catch (EmptyException e){
            e.printStackTrace();
        }
        return array[useSide - 1];
    }

在这里插入图片描述

pop() — 出栈顶元素

public int pop() {
        int top = peek();
        useSide--;
        return top;
    }

在这里插入图片描述

isEmpty(int[] array) — 判断栈是否为空

public boolean isEmpty(int[] array) {
        return array.length == useSide;
    }

size() — 得到栈中的元素个数

public int size() {
        return useSide;
    }

search(int a) — 得到栈中某个元素距离栈顶的距离，栈顶元素位置按1来计算

public int search(int a) {
        int cur = useSide - 1;
        int len = 1;
        while (0 <= cur){
            if(a == array[cur]){
                return len;
            }else {
                cur--;
                len++;
            }
        }
        return -1;
    }

代码整合

public class MyStack implements IStack{
    private int[] array;

    public MyStack() {
        this.array = new int[10];
    }
    private int useSide;


    private void isFull(int[] check){
        if(isEmpty(check)){
            array = Arrays.copyOf(check,2*check.length);
        }
    }
    @Override
    public int push(int a) {
        isFull(array);
        array[useSide++] = a;
        return a;
    }

    @Override
    public int pop() {
        int top = peek();
        useSide--;
        return top;
    }

    @Override
    public int peek() {
        try {
            if(isEmpty(array)){
                throw new EmptyException("空数组读取异常");
            }
        }catch (EmptyException e){
            e.printStackTrace();
        }
        return array[useSide - 1];
    }

    @Override
    public boolean isEmpty(int[] array) {
        return array.length == useSide;
    }

    @Override
    public int size() {
        return useSide;
    }

    @Override
    public int search(int a) {
        int cur = useSide - 1;
        int len = 1;
        while (0 <= cur){
            if(a == array[cur]){
                return len;
            }else {
                cur--;
                len++;
            }
        }
        return -1;
    }
}

1.2 关于栈的例题

例题1 有效括号
在这里插入图片描述

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        if(s == null){
            return false;
        }
        for(int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            if(cur == '(' || cur == '{' || cur == '['){
                stack.push(cur);
            }else if(cur == ')' || cur == '}' || cur == ']'){
                if(stack.isEmpty()){
                    return false;
                }
                if(cur == ')'&&stack.peek() == '(' || 
                   cur == '}'&&stack.peek() == '{' || 
                   cur == ']'&&stack.peek() == '['){
                    stack.pop();
                }else{
                    return false;
                }
            }else{
                return false;
            }
        }
        if(stack.isEmpty()){
            return true;
        }
        return false;
    }
}

例题2 逆波兰表达式
在这里插入图片描述

public int evalRPN(String[] tokens) {
        
        Stack<String> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++){
            if(tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")){
                int m = Integer.parseInt(stack.pop());
                int n = Integer.parseInt(stack.pop());
                if(tokens[i].equals("+")){
                    stack.push(String.valueOf(m+n));
                }else if(tokens[i].equals("-")){
                    stack.push(String.valueOf(n-m));
                }else if(tokens[i].equals("*")){
                    stack.push(String.valueOf(m*n));
                }else{
                    stack.push(String.valueOf(n/m));
                }
            }else{
                stack.push(tokens[i]);
            }
        }
        return Integer.parseInt(stack.pop());
    }

例题3 最小栈
在这里插入图片描述

public Stack<Integer> stack;
    public Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()){
            minStack.push(val);
        }else{
            int m = minStack.peek();
            if(m >= val){
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
        if(stack.empty()){
            return;
        }
        int m = stack.pop();
        if(m == minStack.peek()){
            minStack.pop();
        }
    }
    
    public int top() {
        if(stack.empty()){
            return -1;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if(minStack.empty()){
            return -1;
        }
        return minStack.peek();
    }

例题4 栈的压入、弹出序列
在这里插入图片描述

public boolean IsPopOrder (int[] pushV, int[] popV) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for(int i = 0; i < pushV.length;i++){
            stack.push(pushV[i]);
            while(!stack.isEmpty() && stack.peek() == popV[j] && j < popV.length){
                stack.pop();
                j++;
            }
        }
        
        return stack.isEmpty();
    }

二、什么是队列？

可以理解为一个双向链表(一个一个节点在排队)，同时这个链表只能将队头的元素先推出来，再推出来后面的元素，也就是我们所说的，先进先出、后进后出。
在这里插入图片描述
队列的实例化

Deque<E> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<E> queue = new LinkedList<>();//双端队列的链式实现

2.2 队列的模拟实现

在这里插入图片描述

自定义的接口，规范自定义的类,便于模拟实现

public interface IQueue {
    //
    int offer(int a);
    int poll();
    int peek();
    boolean isEmpty();
}

isEmpty() — 判断是否为空队列

@Override
    public boolean isEmpty() {
        return useSide == 0;
    }

offer(int a) — 从队尾放入元素

public int offer(int a) {
        ListNode listNode = new ListNode(a);
        listNode.val = a;
        if(isEmpty()){
            head = listNode;
            last = listNode;
        }else {
            last.next = listNode;
            listNode.pre = last;
            last = listNode;
        }
        useSide++;
        return a;
    }

在这里插入图片描述

peek() — 查看队头元素

public int peek() {
        try {
            if(head == null){
                throw new EmptyException("空指针异常访问");
            }
        }catch (EmptyException e){
            e.printStackTrace();
        }
        return head.val;
    }

在这里插入图片描述

poll() — 推出队头的元素

public int poll() {
        int fisrt = peek();
        head = head.next;
        useSide --;
        return fisrt;
    }

在这里插入图片描述

代码整合

public class MyQueue implements IQueue{

    static class ListNode{
        int val;
        ListNode pre;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    private ListNode head;
    private ListNode last;
    private int useSide;


    @Override
    public int offer(int a) {
        ListNode listNode = new ListNode(a);
        listNode.val = a;
        if(isEmpty()){
            head = listNode;
            last = listNode;
        }else {
            last.next = listNode;
            listNode.pre = last;
            last = listNode;
        }
        useSide++;
        return a;
    }

    @Override
    public int poll() {
        int fisrt = peek();
        head = head.next;
        useSide --;
        return fisrt;
    }

    @Override
    public int peek() {
        try {
            if(head == null){
                throw new EmptyException("空指针异常访问");
            }
        }catch (EmptyException e){
            e.printStackTrace();
        }
        return head.val;
    }

    @Override
    public boolean isEmpty() {
        return useSide == 0;
    }

}

2.2 关于队列的例题

例题1 设计循环队列
在这里插入图片描述

class MyCircularQueue {
    public int[] array;
    int front;
    int rear;

    public MyCircularQueue(int k) {
        array = new int[k+1];
    }
    // 向循环队列插入一个元素。如果成功插入则返回真。
    public boolean enQueue(int value) {
        if(isFull()){
            return false;
        }
        array[rear] = value;
        rear = (rear+1) % array.length;
        return true;
    }
    //从循环队列中删除一个元素。如果成功删除则返回真。
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        front = (front+1) % array.length;
        return true;
    }
    //从队首获取元素。如果队列为空，返回 -1 。
    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return array[front];
    }
    //获取队尾元素。如果队列为空，返回 -1 。
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        if(rear == 0){
            return array[array.length - 1];
        }
        return array[rear-1];
    }
    //检查循环队列是否为空。
    public boolean isEmpty() {
        return rear == front;
    }
    //检查循环队列是否已满。
    public boolean isFull() {
        return (rear+1) % array.length == front;
    }
}

例题2 用队列实现栈
在这里插入图片描述

class MyStack {
    public Queue<Integer> queue1;
    public Queue<Integer> queue2;
    int size;
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(queue1.isEmpty() && queue2.isEmpty()){
            queue1.offer(x);
            size++;
        }else if(!queue1.isEmpty()){
            queue1.offer(x);
            size++;
        }else if(!queue2.isEmpty()){
            queue2.offer(x);
            size++;
        }
    }
    
    public int pop() {
        if(queue1.isEmpty() && queue2.isEmpty()){
            return -1;
        }
        if(queue1.isEmpty() && !queue2.isEmpty()){
            int cur = size - 1;
            while(cur != 0){
                queue1.offer(queue2.poll());
                cur--;
            }
            size--;
            return queue2.poll();
        }else if(!queue1.isEmpty() && queue2.isEmpty()){
            int cur = size - 1;
            while(cur != 0){
                queue2.offer(queue1.poll());
                cur--;
            }
            size--;
            return queue1.poll();
        }
        return -1;
    }
    
    public int top() {
        if(queue1.isEmpty() && queue2.isEmpty()){
            return -1;
        }
        if(queue1.isEmpty() && !queue2.isEmpty()){
            int cur = size - 1;
            while(cur != 0){
                queue1.offer(queue2.poll());
                cur--;
            }
            int m = queue2.peek();
            queue1.offer(queue2.poll());
            return m;
        }else if(!queue1.isEmpty() && queue2.isEmpty()){
            int cur = size - 1;
            while(cur != 0){
                queue2.offer(queue1.poll());
                cur--;
            }
            int m = queue1.peek();
            queue2.offer(queue1.poll());
            return m;
        }
        return -1;
    }
    
    public boolean empty() {
        return size == 0;
    }

}

例题3 用栈实现队列
在这里插入图片描述

Stack<Integer> stack1;
    Stack<Integer> stack2;
    int size = 0;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    //将元素 x 推到队列的末尾
    public void push(int x) {
        stack1.push(x);
        size++;
    }
    //从队列的开头移除并返回元素
    public int pop() {
        if(empty()){
            return -1;
        }
        if(!stack2.isEmpty()){
            size--;
            return stack2.pop();
        }else if(stack2.isEmpty() && !stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            size--;
            return stack2.pop();
        }
        return -1;
    }
    //返回队列开头的元素
    public int peek() {
        if(empty()){
            return -1;
        }
        if(!stack2.isEmpty()){
            return stack2.peek();
        }else if(stack2.isEmpty() && !stack1.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.peek();
        }
        return -1;
    }
    //如果队列为空，返回 true ；否则，返回 false
    public boolean empty() {
        return size == 0;
    }

总结

本篇文章介绍了有关数据结构中的栈和队列的相关内容，以及它们的简单实现，和简单使用，如果有什么不正确的或者不严谨的地方，还望指正，谢谢大家！

原文地址：https://blog.csdn.net/weixin_74772041/article/details/143759690

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：使用dataGrip连接spark
下一篇：【数据库】组合索引生效规则及索引失效

Windows电脑本地部署llamafile并接入Qwen大语言模型远程AI对话实战
Windows电脑本地部署llamafile并接入Qwen大语言模型远程AI对话实战
阅读更多2024-11-23
解决vm虚拟机中ctrl键粘滞问题（一直处于按下状态）
虚拟机中点击鼠标左键没有问题，单独按下键盘也没有问题，但是如果按下键盘的同时在按下鼠标左键就会卡住。而且100%稳定复现。发现问题原因：vm版本的问题，我的版本是17.5.0，升级成17.5.2 bu
阅读更多2024-11-23
第十章 JavaScript的应用
10.1.1 JavaScript简介1 简单性JavaScript 设计之初就考虑到了非专业程序员的使用，因此它的语法相对简单，容易上手。2 动态性JavaScript 是一种解释型语言，代码可以在
阅读更多2024-11-23
非root用户安装CUDA
4.下载完成后执行.run文件，需要添加两个参数，一个是--override，用于跳过某些检查或限制；另一个是--toolkitpath，它表示安装路径，必须是自己目录下面的路径，如果是根目录就会安装
阅读更多2024-11-23
Python操作neo4j库py2neo使用之py2neo 删除及事务相关操作（三）
【代码】## Python操作neo4j库py2neo使用之py2neo 删除及事务相关操作（三）
阅读更多2024-11-23
【通俗理解】Jensen不等式与变分分布q(z)在积分计算中的应用
Jensen不等式 #变分分布 #积分计算 #期望 #凸函数 #优化问题 #下界估计 #机器学习。
阅读更多2024-11-23
「Mac玩转仓颉内测版27」基础篇7 - 字符串类型详解
本篇将介绍 Cangjie 中的字符串类型，包括字符串的定义、字面量形式、插值表达、常用操作及应用场景，帮助开发者熟练掌握字符串的使用。
阅读更多2024-11-23
数据科学与SQL：组距分组分析 | 区间分布问题
绝对值分布分析也可以理解为组距分组分析。对于某个指标而言，一个记录对应的指标值的绝对值，肯定落在所有指标值的绝对值的最小值和最大值构成的区间内，根据一定的算法，在把这个区间划分为等距离的几个小区间，，
阅读更多2024-11-23
c++编译报C1004错误的原因及解决办法
可能是你的代码文件最后没有正确的结束符，或者是缺少了一些必要的头文件或语句。默认磁盘驱动器没有足够的空间用于临时文件，需要大约两倍于源文件的空间。编译器到达了源文件尾但未解析构造。计算结果为假的 #i
阅读更多2024-11-23
mysql 去重补全取出重复变量函数和存储过程
mysql 去重补全取出重复变量函数和存储过程
阅读更多2024-11-23

数据结构《栈和队列》

文章目录

一、什么是栈？

1.1 栈的模拟实现

1.2 关于栈的例题

二、什么是队列？

2.2 队列的模拟实现

2.2 关于队列的例题

总结

相关文章