数据结构之数组实现栈

喜欢ヅ旅行 2022-02-23 13:16 210阅读 0赞

## 栈 ##

**描述**  
栈，先进后出（Last In First Out） ,它是一种只能在表尾进行插入和删除的特殊线性表。由于栈是一个表，所以数组和链表都可以实现一个栈，数组是一种静态栈，链表是一种动态栈，如果分配空间太大的话，数组栈太浪费内存空间，  
栈的特性是只能从一端取出元素，也只能从一端存元素，进行操作的这一端就是栈顶，那么在栈中我们主要做的操作就是入栈和压栈。  
**应用**  
栈在生活中用到的也是挺多的，就像是文本文档中的撤销操作，按下快捷键（ctrl+Z）就是实现了撤销操作，这就是栈中实现的入栈和出栈操作。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]**操作**  
栈的操作一般有入栈出栈和取出栈顶元素等操作。  
我们先创建一个接口方法Stack

public interface Stack<E> {
    
        int getSize();
        boolean isEmpty();
        void push(E e);
        E pop();
        E peek();
    }

然后进行实现，在我得上一篇博客中写到数组的底层实现，这个栈的实现就是用的数组，大家想了解的可以去上篇博客看一下

public class ArrayStack<E> implements Stack<E> {
    
        private Array<E> array;
    
        public ArrayStack(int capacity){
            array = new Array<>(capacity);
        }
    
        public ArrayStack(){
            array = new Array<>();
        }
    
        @Override
        public int getSize(){
            return array.getSize();
        }
    
        @Override
        public boolean isEmpty(){
            return array.isEmpty();
        }
    
        public int getCapacity(){
            return array.getCapacity();
        }
    
        @Override
        public void push(E e){
            array.addLast(e);
        }
    
        @Override
        public E pop(){
            return array.removeLast();
        }
    
        @Override
        public E peek(){
            return array.getLast();
        }
    
        @Override
        public String toString(){
            StringBuilder res = new StringBuilder();
            res.append("Stack: ");
            res.append('[');
            for(int i = 0 ; i < array.getSize() ; i ++){
                res.append(array.get(i));
                if(i != array.getSize() - 1)
                    res.append(", ");
            }
            res.append("] top");
            return res.toString();
        }
    }

**案例**  
在这里给大家推荐一个刷题的网站就是leetcode(力扣)，当然现在也出了中文版，英文不好的可以在中文版上看一下，在这里不做过多解释。  
我们在LeetCode上找一道关于栈的题目有效的括号如下：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。				
    	有效字符串需满足：		
    	左括号必须用相同类型的右括号闭合。
    	左括号必须以正确的顺序闭合。		
    	注意空字符串可被认为是有效字符串。

我们根据入栈和出栈进行字符串的匹配。  
代码如下：

class Solution {
    
        public boolean isValid(String s) {
    
            Stack<Character> stack = new Stack<>();
            for(int i = 0 ; i < s.length() ; i ++){
                char c = s.charAt(i);
                if(c == '(' || c == '[' || c == '{')
                    stack.push(c);
                else{
                    if(stack.isEmpty())
                        return false;
    
                    char topChar = stack.pop();
                    if(c == ')' && topChar != '(')
                        return false;
                    if(c == ']' && topChar != '[')
                        return false;
                    if(c == '}' && topChar != '{')
                        return false;
                }
            }
            return stack.isEmpty();
        }
    
        public static void main(String[] args) {
    
            System.out.println((new Solution()).isValid("({})[]"));
            System.out.println((new Solution()).isValid("([)]"));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]: /images/20220223/dab880ebc12545ffbf822199e7839aae.png