八、栈

---

 

---

1.定义

一种可以实现”先进后出”的存储结构

栈类似于箱子

栈和堆是一种存储数据的方式

静态变量和局部变量是以压栈和出栈的方式来分配内存

而动态变量是以堆排序的方式来分配内存的

2.分类

静态栈

动态栈

3.算法

出栈

压栈

结构体定义

1. typedef struct Node

2. {

3. int data;

4. struct Node * pNext;

5. }NODE, * PNODE;

6. typedef struct Stack

7. {

8. PNODE pTop;

9. PNODE pBottom;

10. }STACK, * PSTACK;

init方法

1. void init(PSTACK pS)

2. {

3. pS->pTop = (PNODE)malloc(sizeof(NODE));

4. if (NULL == pS->pTop)

5. {

6. printf(“动态内存分配失败!n”);

7. exit(-1);

8. }

9. else

10. {

11. pS->pBottom = pS->pTop;

12. pS->pTop->pNext = NULL;

13. }

14. }

push方法

1. void push(PSTACK pS, int val)

2. {

3. PNODE pNew = (PNODE)malloc(sizeof(NODE));

4. pNew->data = val;

5. pNew->pNext = pS->pTop;

6. pS->pTop = pNew;

7. return;

8. }

push方法的示例图

首先pNew->pNext = pS->pTop;

pNext获得了pTop指针变量存放的地址，直接指向头结点

然后pS->pTop = pNew;用来存放pNew的地址

traverse方法

1. void traverse(PSTACK pS)

2. {

3. PNODE p = pS->pTop;

4. while (p != pS->pBottom)

5. {

6. printf(“%d “, p->data);

7. p = p->pNext;

8. }

9. printf(“n”);

10. return;

11. }

最终结果演示

empty方法

1. bool empty(PSTACK pS)

2. {

3. if (pS->pTop == pS->pBottom)

4. {

5. return true;

6. }

7. else

8. return false;

9. }

pop方法

1. //把pS所指向的栈出栈一次，并把出栈的元素存入pVal指向的变量中，如果出栈失败，则返回false

2. bool pop(PSTACK pS, int * pVal)

3. {

4. if (empty(pS))//pS本身存放的就是S的地址

5. {

6. return false;

7. }

8. PNODE p = pS->pTop;

9. *pVal = p->data;

10. pS->pTop = pS->pTop->pNext;

11. free(p);

12. p = NULL;

13. return true;

14. }

clear方法

1. void clear(PSTACK pS)

2. {

3. if (empty(pS))

4. {

5. return;

6. }

7. PNODE p = pS->pTop;

8. PNODE q = NULL;

9. while (p != pS->pBottom)

10. {

11. q = p->pNext;

12. free(p);

13. p = q;

14. }

15. pS->pTop = pS->pBottom;

16. return;

17. }

4.应用

函数调用

将g的地址和g函数里面的变量压入栈中，然后出栈，到了g的地址是返回f

中断

表达式求值

内存分配

缓冲处理

走迷宫