数据结构（九）栈的基本使用

定义

可以实现“先进后出”的存储结构，类似于堆箱子。栈分为静态栈和动态栈。栈的基本操作是出栈和压栈。栈常用于函数调用、中断、表达式求值、内存分配、缓冲处理、走迷宫算法等。

#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 pS);
void push(PSTACK pS, int val);
bool pop(PSTACK pS, int *pVal);
bool empty(PSTACK pS);
void traverse(PSTACK pS);
void clear(PSTACK pS);
int main(void) {
      STACK S;
      int val;
      init(&S);
      push(&S,1);
      push(&S,2);
      push(&S,3);
      push(&S,4);
      push(&S,5);
      push(&S,6);
      
      if (pop(&S, &val)) {
        printf("出栈成功，出栈的元素是%d\n", val);
    } else {
          printf("出栈失败");
    }
      traverse(&S);
      clear(&S);
      push(&S, 12);
      traverse(&S);
      return 0;
}

void init(PSTACK pS) {
    pS->pTop = (PNODE)malloc(sizeof(NODE));
      if (NULL == pS->pTop) {
        printf("动态分配内存失败！\n");
          exit(-1);
    } else {
          pS->pBottom = pS->pTop;
          pS->pTop->pNext = NULL;
    }
}

void push(PSTACK pS, int val) {
      PNODE pNew = (PNODE)malloc(sizeof(NODE));
      pNew->data = val;
      pNew->pNext = pS->pTop;
      pS->pTop = pNew;
      return;
}

void traverse(PSTACK pS) {
      PNODE p = pS->pTop;
      while (p != pS->pBottom) {
        printf("%d ", p->data);
          p = p->pNext;
      }
      printf("\n");
      return;
}

bool empty(PSTACK pS) {
      if (pS->pTop == pS->pBottom) {
        return true;    
    } else {
          return false;
    }
}

bool pop(PSTACK pS, int *pVal) {
  if (empty(pS)) {
     return false;    
  } else {
      PNODE r = pS->pTop;
      *pVal = r->data;
      pS->pTop = r->pNext;
      free(r);
      r = NULL;
      return true;
  }
}

void clear(PSTACK pS) {
      if (empty(pS)) {
         return;    
    } else {
          PNODE p = pS->pTop;
          PNODE q = NULL;
          while(p != pS->pBottom) {
            q = p->pNext;
              free(p);
              p = q;
          }
          pS->pTop = pS->pBottom;
    }
}