数据结构和算法(2)---- Stack 的原理和实现

Stack 的定义和结构

栈(Stack)是仅限于在表尾进行插入和删除的线性表
我们把允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)，不含任何元素的栈称为空栈，栈也被称为先进后出(Last In First Out)的线性表，简称LIFO结构
栈的机构如下图所示：

栈的插入操作，称为进栈，也称为压栈，入栈。类似于子弹压入弹夹
栈的弹出操作，称为出栈，有的也叫做弹栈。类型于子弹从弹夹中弹出

Stack 的抽象数据类型

ADT Stack(队列)
Data:
    同线性表, 元素具有相同的类型，相邻的元素具有前驱和后继关系
Operation:
    InitStack(S*)
    DestroySatck(S*)
    isEmpty(S*)
    Peek(Q*)// 获取栈顶的元素值，但是不弹出栈
    Pop(Q*, *e)
    Push(Q*, e)
    StackSize(Q)
endADT
1
2
3
4
5
6
7
8
9
10
11
12

静态数组实现Stack

• 建立一个 MAX_SIZE 的数组, 用于存放 Stack 中的元素
• 建立int类型 stack->top 代表栈顶，当弹出元素时，取出stack->top位置的值，同时stack->top--指向下一个元素
• 当压入元素时，stack->top++代表的index 存入新压入元素，并且stack->top指向新元素的位置
  

参考实现代码：

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
}Stack;

static void initStack(Stack* stack) {
    stack->top = -1;
}

static int isEmpty(Stack* stack) {
    return (stack->top == -1);
}

static int isFull(Stack* stack) {
    return (stack->top == MAX_SIZE -1);
}

static void push(Stack* stack, int value) {
    if(isFull(stack)) {
        fprintf(stderr, "stack is full. \n");
        return;
    }
    stack->top++;
    stack->data[stack->top] = value;
    //printf("stack top is %d.\n", stack->top);
}

static int pop(Stack* stack) {
    if(isEmpty(stack)) {
        printf("stack is empty. \n");
        return -1;
    }
    int item = stack->data[stack->top];
    stack->top--;
    return item;
}


static int peek(Stack* stack) {
    if(isEmpty(stack)) {
        fprintf(stderr, "stack is empty. \n");
        return -1;
    }
    return stack->data[stack->top];
}

static int modifyTop(Stack* stack, int value) {
    if(isEmpty(stack)) {
        fprintf(stderr, "stack is empty. \n");
    }
    stack->data[stack->top]= value;
}

static int stackSize(Stack* stack) {
    return stack->top+1;
}

int testbasicStackStaticArray(int agrc, char *argv[]) {
    {
        Stack teststack;
        initStack(&teststack);
        push(&teststack,100);
        push(&teststack,110);
        push(&teststack,120);

        printf("stack size is %d.\n",stackSize(&teststack));

        int value = pop(&teststack);
        printf("stack pop value is %d. size:%d\n",value,stackSize(&teststack));

        value =pop(&teststack);
        printf("stack pop value is %d. size:%d\n",value,stackSize(&teststack));

        value = pop(&teststack);
        printf("stack pop value is %d. size:%d\n",value,stackSize(&teststack));

        printf("stack pop value is %d.\n",pop(&teststack));

    }

    {
        Stack teststack;
        initStack(&teststack);
        push(&teststack,100);
        printf("stack size:%d peek value:%d \n", stackSize(&teststack), peek(&teststack));
        int value = pop(&teststack);
        printf("stack size:%d peek value:%d \n", stackSize(&teststack), peek(&teststack));
    }
}
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

单链表实现Stack

• 建立一个单链表，包含指向栈顶的指针Stack->top
• 当压入元素时，就是单链表的头部插入操作，先给新元素分配空间，然后将新元素的 next 指向 当前的Stack->top，最后更新Stack->top的值
• 当弹出元素时，就是单链表的头部删除操作，首先释放当前Stack->top节点，然后将Stack->top更新到之前元素的下一个位置
  
  参考代码实现如下：

struct node {
    int data;
    struct node *next;
};
typedef struct {
    struct node* top;
} Stack;

static int empty(Stack* stack) {
    return(stack->top == NULL);
}

static void initStack(Stack* stack){
    stack->top = NULL;
}

static  void push(Stack* stack, int item) {
    struct node *pnode;
    pnode = (struct node *)malloc(sizeof(struct node));
    if(pnode == NULL) {
        printf("malloc node failed!.\n");
        exit(1);
    }
    pnode->data = item;
    pnode->next = stack->top;
    stack->top = pnode;
}

static  int pop(Stack* stack) {
    int item;
    struct node *pnode;
    if(empty(stack)) {
        printf("stack is empty.\n");
        exit(1);
    } else {
        item = stack->top->data;
        pnode = stack->top;
        stack->top = stack->top->next;
        free(pnode);
    }
    return item;
}

static int stackSize(Stack* stack) {
    int count = 0;
    struct node *pnode = stack->top;
    if(empty(stack)) {
        return 0;
    } else {
        do {
            pnode = pnode->next;
            count++;
        }while(pnode != NULL);
    }
    return count;
}

int testbasicStackImplsingleLinkedList(int argc, char *argv[]) {
    {
        Stack teststack;
        initStack(&teststack);
        push(&teststack, 110);
        push(&teststack, 111);
        push(&teststack, 113);
        push(&teststack, 223);
        push(&teststack, 678);

        int stacksize = stackSize(&teststack);
        printf("stack size is %d.\n", stacksize);

        printf("stack pop value is %d.\n",pop(&teststack));
        printf("stack pop value is %d.\n",pop(&teststack));
        printf("stack pop value is %d.\n",pop(&teststack));

        // check failed
        printf("stack pop value is %d.\n",pop(&teststack));

        stacksize = stackSize(&teststack);
        printf("stack size is %d.\n", stacksize);

    }

    return 1;
}
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