数据结构--栈

2023-02-04

字数统计: 808字 | 阅读时长≈ 3分

栈：

定义：只能在同一端进行插入或删除操作的线性表（受限的线性表）
特点：后进先出（每次进栈的元素都作为新栈顶元素，每次出栈的元素只能是当前栈顶元素）
栈的实现：
- 数组
- 链表
数组实现的栈创建时容量固定，在不考虑后期扩容的情况下，容易栈溢出，链栈在内存足够的情况下，通常不会栈溢出

数组实现栈：

/**
 * 数组实现栈
 * @author zzr
 * @create 2023-09-22-20:09
 */
public class ArrayStack implements Iterable{
    private int[] stack;
    private int size;
    private int top;
    private int cap=10;

    public ArrayStack() {
        stack=new int[cap];
        size=0;
        top=-1;
    }

    public ArrayStack(int initCap) {
        if (initCap != 0) {
            this.cap = initCap;
        }
        stack=new int[cap];
        size=0;
        top=-1;
    }

    public boolean isEmpty(){
        return size==0;
    }

    public boolean isFull(){
        return size==cap;
    }

    //扩容
    public void grow(){
        if (size==cap){
            int newCap=cap<<1;
            int[] newArray=new int[newCap];//扩容两倍
            this.cap=newCap;
            System.arraycopy(stack,0,newArray,0,size);
            stack=newArray;
        }
    }

    public int getSize(){
        return size;
    }

    /**
     * 入栈
     * @param item
     * @return
     */
    public boolean push(int item){
        grow();
        stack[++top]=item;
        size++;
        return true;
    }
    
    /**
     * 出栈
     * @return
     */
    public Integer pop(){
        if (isEmpty()){
            return null;
        }
        Integer val=stack[top--];
        size--;
        return val;
    }
    /**
     * 查看栈顶元素
     * @return
     */
    public Integer peek(){
        if (isEmpty()){
            return null;
        }
        return stack[top];
    }

    /**
     * 迭代器遍历
     * @return
     */
    @Override
    public Iterator iterator() {
        return new Iterator() {
            int i=0;
            @Override
            public boolean hasNext() {
                return i<size;
            }

            @Override
            public Object next() {
                return stack[i++];
            }
        };
    }
}

链栈（带哨兵结点 [ 哨兵结点不存数据 ] 单链表实现，哨兵结点一边作栈顶）

public class LinkStackClass<E>{  
    //结点类
    static class LinkNode<E>{ 
        E data;//存放结点数据
        LinkNode<E> next;//指向下一节点指针

        /**
        初始化结点
        **/
        public LinkNode(){   
            next=null;  
        }
        public LinkNode(E d){  
            data=d;
            next=null;
        }
    }

    LinkNode<E> head;

    /**
    初始化链栈
    **/
    public LinkStackClass()	{  
        head=new LinkNode<E>();	//哨兵结点	
        head.next=null;			
    }

    //栈空
    public boolean empty(){  
        return head.next==null;  
    }

    //入栈
    public void push(E e){ 
        LinkNode<E> s=new LinkNode<E>(e);//封装成结点
        //将结点s插入到表头
        s.next=head.next;			
        head.next=s;
    }

    //出栈
    public E pop(){  
        if (empty()){
            throw new IllegalArgumentException("栈空");
        }
        E e=(E)head.next.data;	//取首结点值
        head.next=head.next.next;	//删除原首结点
        return e;
    }

    //查看栈顶元素
    public E peek(){  
        if (empty()){
            throw new IllegalArgumentException("栈空");
        }  
        E e=(E)head.next.data;	//取首结点值
        return e;
    }
    
}

Java 栈：

Stack（数组栈）

Iterator 接口
- Collection接口
  - List接口
    - Vetcor 类
      - Stack 类

常用方法：

（1）boolean empty()：判断栈是否为空。

（2）int size()：返回栈中元素个数。

（3）E push(E item)：把对象压入栈顶，即进栈操作。

（4）E pop()：移除栈顶对象，并作为此函数的值返回该对象，即出栈操作。

（5）E peek()：查看栈顶对象，但不从栈中移除它，即返回栈顶元素操作。

（6）int search(Object o)：返回元素o在栈中的位置，该位置从栈顶开始往下算，栈顶为1。

（7）boolean contains(Object o)：如果栈中包含指定的元素o，则返回true；否则返回false。

LinkedList（可做链栈）

常用方法：

（1）push(E e)：头部添加元素

（2）pop()：移除头部元素

（3）peek()：查看头部元素

本文作者： zzr
本文链接： http://zzruei.github.io/2023/021b97c4b0.html
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！