数据结构基础

数据结构与算法是我们大二将要学的，所以有些难度。

开篇小提问：（答案在结尾）

1、数据结构（Data Structure）概念：

    · 数据元素之间不是孤立存在，之间存在某种关系，数据元素之间的关系称为结构；

    · 是指相互之间存在一种或多种特定关系的数据元素集合

    · 换言之，数据结构是带结构的数据元素的集合

什么是栈？

官方定义：后进先出的线性表，要求只在表尾进行删除和插入的操作。

实质是线性表，所以根据线性表的两种存储形式有两种栈的存储结构

栈中不含任何数据时，叫做空栈，此时栈顶就是站底。

录入数据时，数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。

数据出栈时，从栈顶弹出，栈顶下移，整个栈的当前容量变小。

我个人理解栈就像一个汉堡，刚开始时候，只是两个面包片，带芝麻的朝上的的是栈顶，挨着表尾。不带芝麻的另一片面包是栈底，挨着表尾。

当想要加入生菜或者肉片（录入数据）就要打开上片面包（栈顶）

当想要拿走生菜或者肉片（导出数据）也要打开上片面包（栈顶）

加入/取走的食材越多（录入/导出数据越多） 面包的高度越厚/薄（当前容量越大/小）

一、栈的顺序存储结构

typedef struct
{
  ElemType *base;  //创建指向栈底的指针
  ElemType *top;   //创建指向栈顶的指针
  int stackSize;   //栈的当前可使用的最大容量
}sqStack;          //顺序栈

创建一个栈：

#define STACK_INIT_SIZE 100
initStack(sqStack*s)
{
  s->base = (ElemType *)malloc(
  STACK_INIT_SIZE * sizeof(ElemType) );
  if( !s->base )
     exit(0);
  s->top = s->base; //最开始时候，栈顶就是栈尾
  s->stackSize = STACK_INIT_SIZE;
}

入栈：

又称作压栈，每次在栈顶入栈，top指针就加一。

#define STACKINCREMENTS 10
Push(sqStack *a,ElemType e)
{
//如果栈满 追加空间
  if( s->top - s->base >= s->stackSize )
     {
      s->base = (ElemType *)realloc(s->base,(s->stackSize + STACKINCREMENT) * sizeof(ElemType));
if( !s->base )
      exit(0);
      s->top = s->base + s->stackSize;  //设置栈顶
      s->stackSize = s->stackSize + s->STACKINCREMENTS; //设置栈的最大容量 
     }
  *(s->top)=e;
  s->top++;
}

出栈：

Pop(sqStack *s, ElemType *e)
{
    if( s->top = s->base )  //判断栈空
       return;
    *e = *--(s->top);
}  //在栈顶取出数据，栈顶指针下移，当前容量减一

清空一个栈：

ClearStack(sqStack*S)
{
  s->top = s->base;
}

销毁一个栈：（释放该栈所占物理空间）

DstoryStack(sqStack *S)
{
  int i,len;
  len = s->stackSize;
  for( i=0;i< len; i++ )
   {
     free( s->base );
   }
   s->base = s->top = NULL;
   s->stackSize = 0;
}

计算栈的当前容量：（所含元素个数）

int StackLen(sqStack s)
{
  return (s.top - s.base)
  //中间隔了几个元素，就相当于指针的差值再除以每个单元所占的内存，指针可相减，不可相加
}

二、栈的链式存储结构

利用栈只在栈顶插入和删除的特性，将栈顶放在单链表表头，使栈顶指针和单链表合二为一。

·链栈不存在满的情况（除非内存空间无）

·链栈空时：top->null（头指针指向空）

创建一个栈（链表）：

public class LinkedStack<E> implements Stack<E>
    {
    private LinkedList<E> list;  //创建一个链表
 
    public LinkedStack(){	//构造函数
        list=new LinkedList();
    }

获取结点个数判断和非空：

  //获取结点个数
    public int getSize() 
    {
        return list.getSize();
    }
	//判空
    public boolean isEmpty() 
    {
        return list.isEmpty();
    }

入栈：

public void push(E e) 
    {
        list.addFirst(e); 	//调用list的头插函数
    }

出栈：

public E pop() 
    {
        return list.removeFirst(); 	//调用list的尾删函数
    }

获取栈顶元素：

public E peek() 
    {
        return list.getFirst(); //调用list的获取表头元素
    }

清空栈：

   public void clear() 
    {
        list.clear();
    }

迭代器：

@Override
    public Iterator<E> iterator() {
 
        return list.iterator();		//调用list的迭代方法
    }

 答案：

  2021.7.7 

发的第一篇文章，文章还会更改，很多东西还待改进，主要是为了自己学习和理解，有问题还请指出。