栈的C++数组实现

  1 #include "pch.h"
  2 #include <iostream>
  3 #include <stdlib.h>
  4 using namespace std;
  5 
  6 #define EmptyTOS -1        
  7 #define MinStackSize 5    //限定栈的最小容量
  8 #define INCREMENT 5        //容量不足时内存分配增量
  9 
 10 struct StackRecord
 11 {
 12     int cap;//记录栈的容量
 13     int topOfStack;//记录栈的顶端位置
 14     int *array;//指向栈（数组）的指针
 15 };
 16 typedef struct StackRecord* stack;
 17 
 18 //创建一个空栈,自定义容量大小
 19 stack create_empty_stack(int capacity)
 20 {
 21     if (capacity < MinStackSize)
 22         cout << "请指定一个更大的栈" << endl;
 23     else
 24     {
 25         stack S = (stack)malloc(sizeof(StackRecord));
 26         S->cap = capacity;
 27         S->topOfStack = EmptyTOS;
 28         S->array = (int*)malloc(sizeof(int)*capacity);
 29         return S;
 30     }
 31 }
 32 //判断一个栈是否为空栈
 33 bool isempty(stack S)
 34 {
 35     return S->topOfStack == EmptyTOS;
 36 }
 37 //判断是否满栈
 38 bool isfull(stack S)
 39 {
 40     return (S->topOfStack+1) == S->cap;
 41 }
 42 //目前栈的大小
 43 int length_stack(stack S)
 44 {
 45     return S->topOfStack + 1;
 46 }
 47 //释放栈
 48 void dispose_stack(stack S)
 49 {
 50     if (isempty(S))
 51     {
 52         free(S->array);
 53         free(S);
 54     }
 55 }
 56 //进栈
 57 void push_stack(stack S,int x)
 58 {
 59     if (isfull(S))
 60     {
 61         int old_cap = S->cap;
 62         S->array = (int*)realloc(S->array, sizeof(int)*(S->cap + INCREMENT));//分配新空间
 63         if (S == NULL) exit(OVERFLOW);
 64         S->cap = old_cap+INCREMENT;
 65         S->array[++S->topOfStack] = x;
 66     }
 67     else
 68         S->array[++S->topOfStack] = x;
 69 
 70 }
 71 //出栈
 72 void pop_stack(stack S)
 73 {
 74     if (isempty(S))
 75         cout << "栈已空" << endl;
 76     else
 77         S->topOfStack--;
 78 }
 79 //将栈顶返回
 80 int top(stack S)
 81 {
 82     if (isempty(S))
 83         cout << "栈已空" << endl;
 84     else
 85         return S->array[S->topOfStack];
 86 }
 87 //将栈顶返回并出栈
 88 int top_and_pop(stack S)
 89 {
 90     if (isempty(S))
 91         cout << "栈已空" << endl;
 92     else
 93     {
 94         return S->array[S->topOfStack];
 95         S->topOfStack--;
 96     }
 97 }
 98 int main()
 99 {
100     stack S;
101     S=create_empty_stack(5);//创建一个容量为10的栈
102     if (isempty(S))
103         cout << "这是一个空栈" << endl;
104     for (int i = 0; i < 5; i++)
105         push_stack(S, i);
106     if (isfull(S))
107         cout << "栈已满" << endl;
108     push_stack(S, 5);//继续进栈
109     cout << length_stack(S) << endl;//目前栈的大小
110     cout << top_and_pop(S) << endl;
111     system("pause");
112     return 0;
113 }