数据结构C语言版:线性表之顺序栈

栈是一种特殊的线性表。 栈是一种数据结构,是只能在某一端插入和删除的特殊线性表。它按照后进先出的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶 (top),另一端为栈底(bottom);栈底固定,而栈顶浮动;栈中元素个数为零时称为空栈。插入一般称为进栈(PUSH),删除则称为退栈(POP)。 栈也称为后进先出表(LIFO--Last IN First Out表)。

顺序栈的类型描述如下: ADT sequence\_stack{ 数据集合 K: K={k(1), k(2), ...,k(n)}, n >=0, K中的地素是datatype类型; 数据关系 R: R={r} r={ | i=1, 2, ..., n-1} 操作集合: (1) void init(sequence\_stack *st);栈的初始化---置空栈 (2) int empty(sequence\_stack st);判断栈是否为空 (3) datatype read(sequence\_stack st);读栈顶节点值 (4) void push(sequence\_stack *st, datatype x);栈的插入操作 (5) void pop(sequence\_stack *st);栈的删除操作 (6) void display(sequence\_stack st);栈打印操作(假定类型为int) }ADT sequence\_stack;

下面用C代码实现: csequstack.h

#define MAXSIZE 100
typedef int datatype;
typedef struct
{
   datatype a[MAXSIZE];
  int top;
}sequence_stack;
void init(sequence_stack *st);
int empty(sequence_stack st);
datatype read(sequence_stack st);
void push(sequence_stack *st, datatype x);
void pop(sequence_stack *st);
void display(sequence_stack st);

csequstack.cpp

#include "stdafx.h"
#include < stdlib.h >
#include "csequstack.h"
void init(sequence_stack *st)
{
   st->top = 0;
}
int empty(sequence_stack st)
{
  return (st.top ? 0 : 1);
}
datatype read(sequence_stack st)
{
  if(empty(st))
 {
     printf("\nThe sequence stack is empty!"); exit(1);
    }
 else
  {
     return st.a[st.top-1];
    }
}
void push(sequence_stack *st, datatype x)
{
    if(st->top == MAXSIZE)
    {
     printf("\nThe sequence stack is full.");exit(1);
  }
 st->a[st->top] = x;
   ++st->top;
}
void pop(sequence_stack *st)
{
    if(0 == st->top)
  {
     printf("\nThe sequence is empty!");exit(1);
   }
 --st->top;
}
void display(sequence_stack st)
{
 if(0 == st.top)
   {
     printf("\nThe sequence is empty!");exit(1);
   }
 for(int i = 0; i < st.top; ++i)
   {
     printf("%d ", st.a[i]);
   }
}

main.cpp

  sequence_stack st;
   init(&st);
   push(&st, 5);
push(&st, 8);
display(st);