Written with StackEdit中文版.

顺序栈

简介

栈，是限定仅在表尾进行插入或删除的线性表，其表尾称为栈顶，表头称为栈底。栈具有后进先出的特点，即先入栈的元素后出栈。

栈有两种存储表示方法：

  • 顺序栈 — 即栈的顺序存储结构，是用一组地址连续的存储单元依次存放自栈底到栈顶的元素。
  • 链栈 — 即栈的链式表示，其实现方法与单链表类似，这里不实现。

声明与定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
typedef int SElemType;
typedef int Status;
#define STACK_INIT_SIZE 10  //存储空间初始分配量
#define STACKINCREMENT  10  //存储空间分配增量
#define OK 1
#define ERROR 0
#define OVERFLOW -1

typedef struct {
  SElemType* base;//在栈构造之前和销毁之后，base值为NULL
  SElemType* top; //栈顶指针
  int stacksize;//当前已分配的存储空间，以元素为单位
}Sqstack;

//构造一个空栈S
Status InitStack(Sqstack *S);
//若栈为空栈则返回1，否则返回0
Status StackEmpty(Sqstack S);
//若栈不空，则用e返回栈顶元素，并返回1，否则返回0
Status GetTop(Sqstack S, SElemType *e);
//将元素e插入到栈中作为栈顶元素
Status Push(Sqstack *S, SElemType e);
//若栈不空，则删除S的栈顶元素，并返回其值
Status Pop(Sqstack *S, SElemType *e);
//栈不空，则返回栈长
int StackLength(Sqstack S);
//逐一访问栈的元素直到栈空
Status StackTraverse(Sqstack S);

相关方法实现

InitStack

1
2
3
4
5
6
7
8
9
10
11
Status InitStack(Sqstack *S){
  S->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
  
  if (!S->base){
    printf("存储分配失败！\n");
    exit(OVERFLOW);
  }
  S->top = S->base;
  S->stacksize = STACK_INIT_SIZE;
  return OK;
}//InitStack

StackEmpty

1
2
3
Status StackEmpty(Sqstack S){
  return S.top == S.base;
}//StackEmpty

GetTop

1
2
3
4
5
6
7
8
Status GetTop(Sqstack S, SElemType *e){
  if (StackEmpty(S)){
    printf("栈空！\n");
    return ERROR;
  }
  *e = *(S.top);
  return OK;
}//GetTop

Push

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Status Push(Sqstack *S, SElemType e){
  if (S->top - S->base >= S->stacksize) {//栈满，追加存储空间
    int new_size = S->stacksize + STACKINCREMENT;//避免算术溢出
    SElemType* new_base = (SElemType*)realloc(S->base, new_size * sizeof(SElemType));
    if (!new_base){
      printf("追加存储分配失败！\n");
      exit(OVERFLOW);
    }
    S->base = new_base;
    S->top = S->base + S->stacksize - 1;
    S->stacksize += STACKINCREMENT;
  }
  *++(S->top) = e; //第一次入栈的时候，先给top指针++再赋值
				  //即base指针所指的地址是没有值的
                 //不然遍历栈的时候由于top==base的时候跳出循环
                //base指针的值就会丢失且top指针可能会指向一个空地址
  return OK;
}//Push

Pop

1
2
3
4
5
6
7
8
Status Pop(Sqstack *S, SElemType *e){
  if (StackEmpty(*S)){
    printf("栈空！\n");
    return ERROR;
  }
  *e = *S->top--;
  return OK;
}//Pop

StackLength

1
2
3
4
5
6
7
Status StackLength(Sqstack S){
  if (StackEmpty(S)){
    printf("栈空！\n");
    return ERROR;
  }
  return (int)(S.top - S.base);
}//StackLength

StackTraverse

1
2
3
4
5
6
7
8
9
10
Status StackTraverse(Sqstack S) {//逐一提取栈的元素直到栈空
  SElemType e;
  printf("遍历顺序栈: ");
  while (!StackEmpty(S)){
    Pop(&S,&e);
    printf("%d ", e);
  }
  printf("遍历结束\n");
  return OK;
}//StackTraverse

方法测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int main(void){
  SElemType e;
  int size = 0;

  Sqstack MyStack;
  InitStack(&MyStack);

  printf("输入初始栈长!\n");
  scanf_s("%d", &size);
  printf("输入%d个元素入栈!\n", size);
  for (int i = 0; i < size; i++){
    scanf_s("%d", &e);
    Push(&MyStack, e);
  }
  StackTraverse(MyStack);
  GetTop(MyStack, &e);
  printf("栈顶元素是%d\n", e);

  printf("再输入一个数入栈！\n");
  scanf_s("%d", &e);
  Push(&MyStack, e);
  printf("此时栈长为%d\n", StackLength(MyStack));
  StackTraverse(MyStack);

  return 0;
}