数据结构——栈

1 栈

1.1 栈的定义

限定仅在表尾进行插入和删除操作的线性表，又称为后进先出(LAST IN FIRST OUT)线性表,简称LIFO；栈本质上是一个线性表

栈顶：允许进行插入删除操作的一端；栈顶实质上就是表尾

栈底：不允许进行插入删除操作的一端；

空栈：不含任何数据元素的栈；

1.2 栈的操作

进栈，又叫压栈，在栈中添加一个数据元素；

出栈，又叫弹栈，在栈中删除一个数据元素；

1.3 栈的抽象数据类型

ADT栈

Operation 

  StackEmpty(s)    //若栈为空，返回true
                   //若栈中有元素，返回false

  GetTop(s,e)      //若栈存在且非空，返回栈顶元素

  Push(s,e)        //在栈中压入一个元素

  Pop(s,e)         //从栈中弹出一个元素

  StackLength(s)   //获取栈中的元素个数

endADT

2 栈的顺序存储结构

栈的顺序存储结构简称为顺序栈，和线性表类似，用一维数组来存储栈；

2.1 栈的顺序存储结构

1 #define STACKSIZE 100
2 typedef int DataType;
3 typedef struct //结构体别名可有可无
4 {
5   DataType data[STACKSIZE];
6   int top;
7 }SeqStack;

2.2 栈的顺序存储结构的初始化操作

1 void InitStack(SeqStack *s)
2 {
3   s->top=-1;
4 }

2.3 将栈中所以元素删除

1 void ClearStack(SeqStack *s)
2 {
3   s->top=-1;
4 }

2.4 判断栈是否为空

1 bool StackEmpty(SeqStack *s)
2 {
3   return s->top==-1;
4 }

2.5 判断栈是否为满

1 bool StackFull(SeqStack *s)
2 {
3   return s->top=STACKSIZE-1;
4 }

2.6 压栈

1 Status push(SeqStack *s,DataType e)
2 {
3   if(StacFull(s))
4     return ERROR;
5   ++s->top;
6   s->data[s->top]=e;
7   return OK;
8 }

2.7 出栈

1 Status pop(SeqStack *s,DataType *e)
2 {
3   if(StackEmpty(s))
4     return ERROR;
5   *e=s->data[s->top--];
6   return OK;
7 }

2.8 获取栈顶元素

Status getTop(SeqStack *s,DataType *e)
{
   if(StackEmpty(s))
     return ERROR;
   *e=s->data[s->top];
   return OK;
}

2.9 获取栈中元素个数

1 int StackLength(SeqStack *s)
2 {
3   return s->top+1;
4 }

3 栈的链式存储结构

栈的链式存储结构简称链栈，是运算受限的单链表；

链栈通常我们将链表的头部作为栈顶,尾部作为栈底,将链表头部作为栈顶的一端,可以避免在实现数据"入栈"和"出栈"操作时做大量遍历链表的耗时操作。在实现数据"入栈"操作时，需要将数据从链表的头部插入；在实现数据"出栈"操作时，需要删除链表头部的首元节点；(即从链表的头部插入节点，从链表的头部删除节点)

3.1 栈的链式存储结构

 1 typedef int DataType;
 2 
 3 typedef struct StackNode
 4 {
 5   DataType data;
 6   struct StackNode next;
 7 }StackNode;
 8 
 9 typedef struct LinkStack
10 {
11   StackNode *top;
12   int count;
13 }LinkStack;

3.2 初始化操作

typedef int DataType;
 
typedef struct StackNode
{
  DataType data;
  struct StackNode next;
}StackNode;
 
typedef struct LinkStack
{
  StackNode *top;
  int count;
}LinkStack;

void InitStack(LinkStack *s)
{
  s->top=NULL;
  s->count=0；
}

void main()
{
  LinkStack ls;
  InitStack(&ls);
}

3.3 判断栈是否为空

typedef int DataType;
 
typedef struct StackNode
{
  DataType data;
  struct StackNode next;
}StackNode;
 
typedef struct LinkStack
{
  StackNode *top;
  int count;
}LinkStack;

void InitStack(LinkStack *s)
{
  s->top=NULL;
  s->count=0；
}

void StackEmpty(LinkStack *s)
{
  return s->count==0?true:false;
}

void main()
{
  LinkStack ls;
  InitStack(&ls);
  ...
  if(StackEmpty(&ls))
    printf("Stack is empty");
  else
    printf("Stack is not empty");
}

3.4 压栈

typedef int DataType;
 
typedef struct StackNode
{
  DataType data;
  struct StackNode next;
}StackNode;
 
typedef struct LinkStack
{
  StackNode *top;
  int count;
}LinkStack;

void InitStack(LinkStack *s)
{
  s->top=NULL;
  s->count=0；
}

Status push(LinkStack *s,DataType e)
{
  StackNode *n=(StackNode*)malloc(sizeof(StackNode));
  n->data=e;
  n->next=s->top;
  s->top=n;
  s->count++;
  return OK;
}

void main()
{
  LinkStack ls;
  InitStack(&ls);
  push(&ls,10);
}

3.5 删除栈中所有元素

typedef int DataType;
 
typedef struct StackNode
{
  DataType data;
  struct StackNode next;
}StackNode;
 
typedef struct LinkStack
{
  StackNode *top;
  int count;
}LinkStack;

void InitStack(LinkStack *s)
{
  s->top=NULL;
  s->count=0；
}

void ClearStack(LinkStack *s)
{
  StackNode *p=s->top;
  while(p)
  {
    StackNode *q=p;
    p=p->next;
    free(q);
  }
  s->count=0;
  s->top=NULL;
}

void main()
{
  LinkStack ls;
  InitStack(&ls);
  push(&ls,10);
  push(&ls,3);
  push(&ls,8);
  ClearStack(&ls);
}

3.6 获取栈顶元素

typedef int DataType;
 
typedef struct StackNode
{
  DataType data;
  struct StackNode next;
}StackNode;
 
typedef struct LinkStack
{
  StackNode *top;
  int count;
}LinkStack;

void InitStack(LinkStack *s)
{
  s->top=NULL;
  s->count=0；
}

Status getTop(LinkStack *s,DataType *e)
{
  if(StackEmpty(&sl))
    return ERROR;
  *e=s->top->data;
  return OK;
}

void main()
{
  LinkStack ls;
  InitStack(&ls);
  push(&ls,10);
  push(&ls,3);
  push(&ls,8);
  DataType r;
  getTop(&ls,&r);
}

3.7 出栈

Status pop(SeqStack s,DataType *e)
{
  if(StackEmpty(&s))
    return ERROR;
  *e=s->top->data;
  StackNode *p=s->top;
  s->top=p->next;
  free(p);
  s->count--;
  return OK;
}

3.8 获取栈中元素个数

int StackLength(SeqStack *s)
{
  return s->count;
}

数据结构——栈

推荐阅读