C动态栈

àì夳堔傛蜴生んèń 2022-06-09 06:38 386阅读 0赞

/\*  
时间：2012/07/21 14:42  
目的：自己模拟一个动态栈  
\*/  
\# include <stdio.h>  
\# include <malloc.h>  
\# include <stdlib.h>

typedef struct Node //创建一个节点类型的结构体  
\{  
 int data; //数据域  
 struct Node \* pNext; //指针域  
\}NODE, \* PNODE;

typedef struct Stack  
\{  
 PNODE pTop; //指向栈顶的指针  
 PNODE pBottom; //指向栈底的指针  
\}STACK, \* PSTACK;

void init(PSTACK);  
void push(PSTACK, int);  
void traverse(PSTACK);  
bool pop(PSTACK, int \*);//如果栈为空的话，出栈操作将无法进行。因此，此方法要有返回值来表示出栈操作是否成功。  
void toPop(PSTACK);  
void clear(PSTACK pS);  
bool isEmpty(PSTACK pS);

int main(void)  
\{  
 STACK s; //相当于 struct Stack s;  
   
 init(&s);  
 push(&s, 5);  
 push(&s, 7);  
 traverse(&s);  
 toPop(&s);  
 toPop(&s);  
 toPop(&s);

for (int i=1; i<10; i++)  
  push(&s, i);  
   
 traverse(&s);  
 clear(&s);  
 traverse(&s);

return 0;  
\}

void init(PSTACK pS)  
\{  
 pS->pBottom = (PNODE)malloc( sizeof(NODE) );

if (NULL == pS->pBottom)  
 \{  
  printf("内存分配失败，程序终止。");  
  exit(-1);  
 \}  
 else  
 \{  
  pS->pTop = pS->pBottom;  
  pS->pBottom->pNext = NULL; //设置尾节点的指针域为空  【注】尾节点无实际意义，只是为了方便程序的操作。  
 \}  
\}

void push(PSTACK pS, int val)  
\{  
 PNODE pNew = (PNODE)malloc( sizeof(NODE) );  
 if (NULL == pNew)  
 \{  
  printf("内存分配失败，程序终止。");  
  exit(-1);  
 \}  
 else  
 \{  
  pNew->data = val; //设置新入栈节点的数据域  
  pNew->pNext = pS->pTop; //设置新入栈节点的指针域 指向 原栈顶的节点  
  pS->pTop = pNew; //设置新入栈的节点为栈顶的节点  
 \}  
\}

void traverse(PSTACK pS)  
\{  
 PNODE p = pS->pTop;

while (p != pS->pBottom)  
 \{  
  printf("%d ", p->data);  
  p = p->pNext;  
 \}  
 printf("\\n");  
\}

bool isEmpty(PSTACK pS)  
\{  
 if (pS->pTop == pS->pBottom) //栈为空时  
 \{  
  return true;  
 \}  
 else  
 \{  
  return false;  
 \}  
\}  
/\*  
参数：pS为栈的指针  
   oldVal为指向 被出栈节点的数据域 的指针，通过\*oldVal即可设置被出栈节点的数据域的值，从而向调用函数返回被出栈节点的数据域的值。  
返回值：为true时，出栈操作成功；为false时，出栈操作失败，即栈中没有有效的元素，没有有效的节点。  
\*/  
bool pop(PSTACK pS, int \* oldVal)  
\{  
 if ( isEmpty(pS) ) //栈为空时  
 \{  
  return false;  
 \}  
 else  
 \{  
  PNODE p = pS->pTop; //把原栈顶节点的指针赋值给一个临时变量，方便在后面释放内存  
  \*oldVal = pS->pTop->data; //把原栈顶节点的数据域的值返回给调用的函数中的val变量，即main方法中的val变量。  
  pS->pTop = pS->pTop->pNext; //设置栈顶节点 为 原栈顶节点所指向的下一个节点  
  free(p); //释放原栈顶节点所占用的内存  
  //p = NULL;

return true;  
 \}  
\}

void toPop(PSTACK pS)  
\{  
 int val;  
 if ( pop(pS, &val) )  
  printf("被出栈的元素是：%d\\n", val);  
 else  
  printf("已经是空栈了，不用再进行出栈操作了！\\n");  
\}

/\*  
清空栈的方法  
\*/  
void clear(PSTACK pS)  
\{  
 if ( isEmpty(pS) )  
  return; //栈本来就为空时，让方法直接返回。减少因为运行下面的代码，所带来的时间和内存的消耗。

PNODE p = pS->pTop;  
 PNODE q = NULL; //q存次栈顶节点

while (p != pS->pBottom)  
 \{  
  q = p->pNext; //把栈顶节点下一个节点的指针存起来，以避免栈顶节点被释放后无法找到它的下一个节点。  
  free(p); //释放栈顶节点所占的内存  
  p = q; //更新栈顶节点 为 它的下一个节点  
 \}

pS->pTop = pS->pBottom; //【注】千万别忘记把pS->pTop指向尾节点。因为，此时栈已经被清空了，已经没有任何有效元素了。  
\}

/\*  
程序的运行结果：  
==========================================================================  
7 5  
被出栈的元素是：7  
被出栈的元素是：5  
已经是空栈了，不用再进行出栈操作了！  
9 8 7 6 5 4 3 2 1  
==========================================================================

总结：  
\-----------------------------------------------------------------------------------------------  
栈：后进先出  
静态栈：用数组实现的。  用静态分配内存的方式，声明一个数组作为栈  
动态栈：用链表实现的。  用动态分配内存的方式，构造一个链表作为栈  
\-----------------------------------------------------------------------------------------------  
\*/

![1342869756_9092.png][]

[1342869756_9092.png]: https://img-my.csdn.net/uploads/201207/21/1342869756_9092.png