第四章：栈

# 第四章：栈

# 概念

栈是只允许在一端进行插入或删除操作的线性表
重要术语：栈顶、栈底、空栈
特点：后进先出（LIFO）

# 顺序栈

缺点：栈的大小不可改变

# 定义

#define MaxSize 10

/* 结点的结构体 */
typedef struct
{
  int data[MaxSize]; // 静态数组存放栈中元素
  int top;  // 栈顶指针，从0开始数，空栈时为-1
} SqStack;

1
2
3
4
5
6
7
8

# 初始化

/* 初始化操作 */
void InitStack(SqStack *S)
{
  S->top = -1;
}

1
2
3
4
5

# 是否为空

/* 是否为空 */
bool StackEmpty(SqStack *S)
{
  return S->top == -1;
}

1
2
3
4
5

# 进栈

/* 进栈 */
bool Push(SqStack *S, int x)
{
  if(S->top == MaxSize-1) // 栈满溢出
    return false;
  S->data[++S->top] = x;
  return true;
}

1
2
3
4
5
6
7
8

# 出栈

/* 出栈 */
bool Pop(SqStack *S, int *x)
{
  if(S->top == -1)  // 空栈
    return false;
  *x = S->data[S->top--];
  return true;
}

1
2
3
4
5
6
7
8

# 读取栈顶

/* 读取栈顶 */
bool GetTop(SqStack *S, int *x)
{
  if(S->top == -1)
    return false;
  *x = S->data[S->top];
  return true;
}

1
2
3
4
5
6
7
8

# 打印

/* 打印 */
void TravelStack(SqStack *S)
{
  int j = S->top;
  printf("打印：\n");
  while (j >= 0)
  {
    printf("%d --- %d\n", j, S->data[j]);
    j--;
  }
}

1
2
3
4
5
6
7
8
9
10
11

# 共享栈

#define MaxSize 10
typedef struct {
    ElemType data[MaxSize];
    int top0;
    int top1;
}
// 初始化栈
void InitStack(ShStach *S)
{
    S->top1 = -1;
    S->top2 = MaxSize;
}

1
2
3
4
5
6
7
8
9
10
11
12

栈满的条件：top0 +1 = top1;

# 链栈（不带头结点）

# 定义

struct Linknode
{
  int data;
  struct Linknode *next;
};
typedef struct Linknode *LiStack;

1
2
3
4
5
6

# 初始化

/* 初始化操作 */
void InitStack(LiStack *S)
{
  *S = NULL;
}

1
2
3
4
5

# 是否为空

/* 是否为空 */
bool StackEmpty(LiStack S)
{
  return S == NULL;
}

1
2
3
4
5

# 进栈

/* 进栈 */
bool Push(LiStack *S, int x)
{
  Linknode *p = (Linknode *)malloc(sizeof(Linknode));
  p->data = x;
  p->next = (*S);
  (*S) = p;
  return true;
}

1
2
3
4
5
6
7
8
9

# 出栈

/* 出栈 */
bool Pop(LiStack *S, int *x)
{
  if(*S == NULL)  // 空栈
    return false;
  Linknode *p = (*S);
  (*S) = (*S)->next;
  (*x) = p->data;
  free(p);
  return true;
}

1
2
3
4
5
6
7
8
9
10
11

# 读取栈顶

/* 读取栈顶 */
bool GetTop(LiStack *S, int *x)
{
  if((*S) == NULL)  // 空栈
    return false;
  *x = (*S)->data;
  return true;
}

1
2
3
4
5
6
7
8

# 打印

/* 打印 */
void TravelStack(LiStack S)
{
  Linknode *p = S;
  printf("打印：\n");
  while (p != NULL)
  {
    printf("%d\n", p->data);
    p = p->next;
  }
}

1
2
3
4
5
6
7
8
9
10
11

#

#数据结构 #考研

上次更新: 2020/11/05, 15:11:00

← 第三章：线性表第五章：队列→