C与指针-第十七章-堆栈

发表于   |   分类于   |  

抽象数据类型(ADT)是C程序员不可或缺的工具，这类ADT有链表、堆栈、队列和树等，前面我们已经讨论过了链表，接下来我们来学习堆栈、队列和树。

所有的ADT都需要确定一件事情–如何获取内存来存储值，这里有三种方案：

1)静态数组
2）动态内存分配
3）动态链表存储

本章主要讲解堆栈的操作方式，并用上述三种方式分别来实现堆栈的操作。

栈的特点：后进先出(Last in First out –LIFO)
例如向仓库里堆放货品，后放进去的靠近门口，因此也会先拿出去

栈操作：

入栈(push):
将数据保存到栈顶的操作。进入栈操作前，先修改栈顶指针，使其向上移动一个元素位置，然后将数据保存到栈顶指针所指的位置。

出栈(pop)：
将栈顶数据弹出操作，通过修改栈顶指针，使其指向栈中的下一个元素。

堆栈实现：

1)静态数组操作：

这一节堆栈的操作以int类型进行入栈、出栈

stack.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#ifndef STACK_H
#define STACK_H

#include <stdio.h>
#include <stdlib.h>

/*入栈*/
void push(int value);

/*出栈*/
int pop(void);

/*返回栈顶指针*/
int top(void);

/*栈是否为空： TRUE-栈为空; FALSE--栈不为空*/
int is_empty(void);

/*栈是否已满，TRUE--栈满; FALSE--栈不满*/
int is_full(void);

#endif

stack.c

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include "stack.h"

#define STACK_SIZE    100  /*栈中元素数量的限制*/
static int stack[STACK_SIZE];
static int top_element = -1;


/*入栈*/
void push(int value)
{
  top_element += 1;
  stack[top_element] = value;
}

/*出栈*/
int pop(void)
{
  if(is_empty())
  {
    return -1;
  }
  int temp;
  temp = stack[top_element];
  top_element -= 1;
  return temp;
}

/*返回栈顶指针*/
int top(void)
{
  return stack[top_element];
}

/*栈是否为空： TRUE-栈为空; FALSE--栈不为空*/
int is_empty(void)
{
  return (top_element == -1);
}

/*栈是否已满，TRUE--栈满; FALSE--栈不满*/
int is_full(void)
{
  return top_element == STACK_SIZE -1;
}

int main(void)
{
  push(10);
  push(11);
  int temp = pop();
  printf("temp = %d\n",temp);
  return 0;
}

2）动态内存分配

stack.h

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
#ifndef STACK_H
#define STACK_H

#include <stdio.h>
#include <stdlib.h>

/*创建栈*/
void create_stack(size_t size);

/*创建栈*/
void destory_stack(void);

/*入栈*/
void push(int value);

/*出栈*/
int pop(void);

/*返回栈顶指针*/
int top(void);

/*栈是否为空： TRUE-栈为空; FALSE--栈不为空*/
int is_empty(void);

/*栈是否已满，TRUE--栈满; FALSE--栈不满*/
int is_full(void);

#endif

stack.c

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "stack.h"

static int    *stack;
static size_t stack_size;
static int    top_element = -1;

/*创建栈*/
void create_stack(size_t size)
{
   stack_size = size;
   stack = malloc(stack_size * sizeof(int));
   if (stack == NULL)
   {
      printf("create_stack fail\n");
      return;
   }
}

/*销毁栈*/
void destory_stack(void)
{
  if (stack_size >0)
  {
    stack_size = 0;
  }
  free(stack);
}


/*入栈*/
void push(int value)
{
  top_element += 1;
  stack[top_element] = value;
}

/*出栈*/
int pop(void)
{
  if(is_empty())
  {
    return -1;
  }
  int temp;
  temp = stack[top_element];
  top_element -= 1;
  return temp;
}

/*返回栈顶指针*/
int top(void)
{
  return stack[top_element];
}

/*栈是否为空： TRUE-栈为空; FALSE--栈不为空*/
int is_empty(void)
{
  return (top_element == -1);
}

/*栈是否已满，TRUE--栈满; FALSE--栈不满*/
int is_full(void)
{
  return top_element == stack_size -1;
}

int main(void)
{
  create_stack(100); /*创建堆栈*/
  push(10); /*入栈*/
  push(11);
  int temp = pop(); /*出栈*/
  printf("temp = %d\n",temp);
  destory_stack(); /*销毁栈*/
  return 0;
}

3）数据链表操作：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#define MAX_LEN 100
typedef struct
{
    char *top; //栈顶
    char *base;//栈底
    int stacksize;//栈大小
}stack;


/*栈的初始化*/
void init_stack(stack *s)
{
    s->base = (char *)malloc(MAX_LEN * sizeof(char));
    if (NULL == s)
    {
      return;
    }
    s->top = s->base;
    s->stacksize = MAX_LEN;
}

/*栈的销毁*/
void destory(stack *s)
{
    if (NULL == s->base)
    {
        return;
    }
    free(s->base);
    s->top = s->base = NULL;
    s->stacksize = 0;
}

/*清空栈*/
void clear(stack *s)
{
    if (NULL == s->base)
    {
        return;
    }
    s->top = s->base;
}

/*入栈*/
void push(stack *s,char elem)
{
  //s是否已满，若栈满，重新分配空间
  if ((s->top-s->base)>STACK_INIT_SIZE)
  {
    s->base = (char*)realloc(s->base,(STACKINCRENMENT+STACK_INIT_SIZE)*sizeof(char));
    if (NULL == s->base)
    {
      return;
    }
    //将栈顶指针指向栈顶
    s->top = s->base+s->stacksize;
    s->stacksize += MAX_LEN;
  }
  //将元素e，写入栈顶，注意这里可能有错。
   *(s->top)=elem;
   s->top++;
}

/*出栈*/
char pop(stack *s)
{
   //保存栈顶元素
    char topelement;
    //如果栈顶指针指向与栈底指针指向同一内存单元时，表示栈为空或者栈不存在

    if (s->top == s->base)
    {
      return;
    }
   //栈顶元素= 栈的top - 1；
   topelement = *(s->top - 1);
    return topelement;
}

示例：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LEN 100

typedef struct
{
  char  *top;
  char  *tail;
  int    stacksize;
}stack;

void init_stack(stack *s)
{
  s->tail = (char *)malloc(MAX_LEN*sizeof(char));
  if (NULL == s)
  {
    return;
  }
  s->top = s->tail;
  s->stacksize = MAX_LEN;
}

void destory_stack(stack *s)
{
  if (NULL == s->tail)
  {
    return;
  }
  free(s->tail);
  s->top = s->tail = NULL;
  s->stacksize = 0;
}

void clear_stack(stack *s)
{
  if (NULL == s->tail)
  {
    return;
  }
  s->top = s->tail;
}

void push(stack *s,char elem)
{
  //if stack is full,need malloc new space
  if ((s->top - s->tail) > MAX_LEN)
  {
    s->tail = (char *)malloc(MAX_LEN *sizeof(char));
    if (NULL == s->tail)
    {
      return;
    }
    s->top = s->tail + s->stacksize;
    s->stacksize += MAX_LEN;
  }

  *(s->top) = elem;
  s->top++;
}

char pop(stack *s)
{
  char topelem;
  if (s->top == s->tail)
  {
    exit(-1);
  }

  topelem = *(s->top - 1);
  s->top--;

  return topelem;
}

int main(void)
{
  stack s;
  int i;
  char *elem = "abcd";

  //INI STACK
  init_stack(&s);
  printf("进栈顺序\r\n");

  //循环打印elem的值

  while(*elem != '\0')
  {
    push(&s,*elem);
    printf("%3c\r\n",*elem);
    elem++;
  }

  //出栈
  printf("出栈顺序\r\n");
  while((s.top != NULL) && (s.tail != NULL))
  {
    printf("%3c\r\n",pop(&s));
  }

  clear_stack(&s);
  return 0;
}

Tianger Ge wechat
如果您喜欢这篇文章，欢迎扫一扫我的微信公众号！