数据结构--栈和队列的使用_ashfiqa的博客

目录

一、栈的理解和使用

1.1什么是栈

1.2栈的简单实现 

1.3栈中方法的介绍

1.4 关于栈的练习

二、队列的理解和使用 

2.1什么是队列

2.2对于简单队列的实现 

 2.3队列中方法的介绍

三、循环队列

---

一、栈的理解和使用

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;
    }

}