栈

0. 顺序存储结构

---

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

#define MAXSIZE 20

typedef struct Node {
  
  int Data[MAXSIZE];
  
  int Top;
  
}SNode, *Stack;

// 生成空堆栈
Stack CreateStack(int MaxSize) {
  
  Stack PtrS;
  
  PtrS = (Stack)malloc(sizeof(SNode));
  
  PtrS -> Top = -1;
  
  return PtrS;
  
}

// 入栈
void Push(Stack PtrS, int item) {
  
  if (PtrS -> Top == MAXSIZE - 1) {
    
    printf("堆栈满");
    
    return;
    
  } else {
    
    PtrS -> Data[++(PtrS -> Top)] = item;
    
    return;
    
  }
  
}

// 出栈
int Pop(Stack PtrS) {
  
  if (PtrS -> Top == -1) {
    
    printf("堆栈空");
    
    return -2;
    
  } else {
    
    return (PtrS -> Data[(PtrS -> Top)--]);
    
  }
  
}

typedef struct DNode {
  
  int Data[MAXSIZE];
  
  int Top1;
  
  int Top2;
  
}DSNode, *DStack;

// 生成空堆栈
DStack CreateDStack(int MaxSize) {
  
  DStack PtrS;
  
  PtrS = (DStack)malloc(sizeof(DSNode));
  
  PtrS -> Top1 = -1;
  
  PtrS -> Top2 = MAXSIZE;
  
  return PtrS;
  
}

void DPush(DStack PtrS, int item, int Tag) {
  
  if (PtrS -> Top2 - PtrS -> Top1 == 1) {
    
    printf("堆栈满");
    
    return;
    
  }
  
  if (Tag == 1) {
    
    PtrS -> Data[++(PtrS -> Top1)] = item;
    
  } else {
    
    PtrS -> Data[--(PtrS -> Top2)] = item;
    
  }
  
}

int DPop(DStack PtrS, int Tag) {
  
  if (Tag == 1) {
    
    if (PtrS -> Top1 == -1) {
      
      printf("堆栈1空");
      
      return -2;
      
    } else {
      
      return PtrS -> Data[(PtrS -> Top1)--];
      
    }
    
  } else {
    
    if (PtrS -> Top2 == MAXSIZE) {
      
      printf("堆栈1空");
      
      return -2;
      
    } else {
      
      return PtrS -> Data[(PtrS -> Top2)++];
      
    }
    
  }
  
}

---

1. 链式存储结构

---

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

typedef struct Node {
  
  int data;
  
  struct Node *Next;
  
}SNode, *Stack;

Stack CreateStack() {
  
  Stack S;

  S = (Stack)malloc(sizeof(SNode));
  
  S -> Next = NULL;
  
  return S;
  
}

int IsEmpty(Stack S) {
  
  return (S -> Next == NULL);
  
}

void Push(int item, Stack S) {
  
  Stack TmpCell;
  
  TmpCell = (Stack)malloc(sizeof(SNode));
  
  TmpCell -> data = item;
  
  TmpCell -> Next = S -> Next;
  
  S -> Next = TmpCell;
  
}

int Pop(Stack S) {
  
  Stack FirstCell;
  
  int TopItem;
  
  if (IsEmpty(S)) {
    
    printf("堆栈空");
    
    return -2;
    
  } else {
    
    FirstCell = S -> Next;
    
    S -> Next = FirstCell -> Next;
    
    TopItem = FirstCell -> data;
    
    free(FirstCell);
    
    return TopItem;
    
  }
  
}

---