数据结构与算法之栈（基于数组）讲解

今天药忘吃喽~ 2024-04-18 15:15 145阅读 0赞

1，栈是一种后进先出（last in first out）LIFO

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MzA1MDI3_size_16_color_FFFFFF_t_70][]

2，基于自己实现的数组实现栈，下面是自己实现数组类

<table> 
 <tbody> 
  <tr> 
   <td> <pre><code>package com.dream21th.algorithmicdatastructure.stack;

/**
 * @Auther: hp
 * @Date: 2019/9/7 15:42
 * @Description:
 */
public class MyExtendArray&lt;E&gt; {

private E[] datas;

private int size;

/**
     * 创建有参构造函数，初始化数组容量
     * @param capacity
     */
    public MyExtendArray(int capacity){
        datas=(E[])new Object[capacity];
        size=0;
    }

/**
     * 构造无参函数，初始化数组容量
     */
    public MyExtendArray(){
        this(10);
    }

public int getSize(){
        return this.size;
    }

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

/**
     * 在指定索引位置加值
     * @param index
     * @param e
     */
    public void add(int index,E e){
        if(index&lt;0 || index&gt;this.size){
            throw new IllegalArgumentException("index must between 0 and size");
        }
        if(this.size==datas.length){
            resize(2*datas.length);
        }
        for(int position=size-1;position&gt;=index;position--){
            this.datas[position+1]=this.datas[position];
        }
        this.datas[index]=e;
        this.size++;
    }

private void resize(int newCapacity) {

E[] newDatas= (E[]) new Object[newCapacity];

for(int i=0;i&lt;this.datas.length;i++){
            newDatas[i]=this.datas[i];
        }
        this.datas=newDatas;
    }

/**
     * 在第一个位置加入元素
     * @param e
     */
    public void addFirst(E e){
        this.add(0,e);
    }

/**
     * 在最后一个位置添加元素
     * @param e
     */
    public void addLast(E e){
        this.add(size,e);
    }

public E get(int index){
        if(index&lt;0 || index&gt;=this.size){
            throw new IllegalArgumentException("index must between 0 and size");
        }
        return this.datas[index];
    }

public void set(int index,E e){
        if(index&lt;0 || index&gt;=this.size){
            throw new IllegalArgumentException("index must between 0 and size");
        }
        this.datas[index]=e;
    }

public boolean contain(E e){
        for(int i=0;i&lt;size;i++){
            if(this.datas[i].equals(e)){
                return true;
            }
        }
        return false;
    }

public int find(int e){
        for(int i=0;i&lt;size;i++){
            if(this.datas[i].equals(e)){
                return i;
            }
        }
        return -1;
    }

public E remove(int index){
        if(index&lt;0 || index&gt;=this.size){
            throw new IllegalArgumentException("index must between 0 and size");
        }
        E ret=this.datas[index];
        for(int i=index+1;i&lt;size;i++){
            this.datas[i-1]=this.datas[i];
        }
        size--;
        this.datas[size]=null;
        if(this.size==this.datas.length/2){
            resize(this.datas.length/2);
        }
        return ret;
    }

public E removeFirst(){
        return remove(0);
    }

public E removeLast(){
        return remove(size-1);
    }

public E getLast(){
       return  get(this.size-1);
    }

public E getFirst(){
        return get(0);
    }

public int getCapacity(){
        return this.datas.length;
    }
    @Override
    public String toString() {

StringBuilder builder=new StringBuilder();
        builder.append(String.format("Array: size = %d,capacity = %d \n",this.size,this.datas.length));
        builder.append("[");
        for(int i=0;i&lt;size;i++){
            builder.append(this.datas[i]);
            if(i!=size-1){
                builder.append(",");
            }
        }
        builder.append("]");
        return builder.toString();
    }
}
</code></pre> </td> 
  </tr> 
 </tbody> 
</table>

3，栈的实现

<table> 
 <tbody> 
  <tr> 
   <td> <pre><code>package com.dream21th.algorithmicdatastructure.stack;

/**
 * @Auther: hp
 * @Date: 2019/9/8 10:41
 * @Description:
 */
public interface Stack&lt;E&gt; {

int getSize();

boolean isEmpty();

void push(E e);

E pop();

E peek();
}
</code></pre> </td> 
  </tr> 
 </tbody> 
</table>

<table> 
 <tbody> 
  <tr> 
   <td> <pre><code>package com.dream21th.algorithmicdatastructure.stack;

/**
 * @Auther: hp
 * @Date: 2019/9/8 10:55
 * @Description:
 */
public class ArrayStack&lt;E&gt; implements Stack&lt;E&gt; {

private MyExtendArray&lt;E&gt; myExtendArray;

public ArrayStack(int capacity){
        myExtendArray=new MyExtendArray&lt;&gt;(capacity);
    }

public ArrayStack(){
        this(10);
    }
    @Override
    public int getSize() {
        return myExtendArray.getSize();
    }

@Override
    public boolean isEmpty() {
        return myExtendArray.isEmpty();
    }

@Override
    public void push(E e) {
        myExtendArray.addLast(e);
    }

@Override
    public E pop() {
        return myExtendArray.removeLast();
    }

@Override
    public E peek() {
        return myExtendArray.getLast();
    }

public int getCapacity(){
        return myExtendArray.getCapacity();
    }

@Override
    public String toString() {

StringBuilder builder=new StringBuilder();
        builder.append(String.format("Stack: size = %d, capacity = %d \n",getSize(),getCapacity()));
        builder.append("[");
        for(int i=0;i&lt;getSize();i++){
            builder.append(myExtendArray.get(i));
            if(i!=getSize()-1){
                builder.append(",");
            }
        }
        builder.append("] top");

return builder.toString();
    }
}
</code></pre> </td> 
  </tr> 
 </tbody> 
</table>

4，时间复杂度分析

由于都是在数据末尾进行操作，进栈和出栈的空间复杂度都是O(n)。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MzA1MDI3_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/fa67fcfc502740f495bc22ec2fd59800.png