堆栈的链式存储实现

  1 #include<iostream>
  2 #define Max 50
  3 using namespace std;
  4 typedef int ElemType;
  5 typedef struct StackNode //链式栈结点的定义
  6 {
  7     struct StackNode* next;
  8     ElemType data;
  9 }StackNode;
 10 
 11 typedef struct LinkStack //链式栈的定义
 12 {
 13     struct StackNode* top;//栈顶结点指针
 14     int num;//栈结点数量
 15 }LinkStack;
 16 
 17 //栈方法声明
 18 
 19 LinkStack* CreateLinkStack();                          //创建一个空的栈
 20 void DestroyLinkStack(LinkStack* qstack);              //销毁栈
 21 void ClearLinkStack(LinkStack * qstack);               //清空栈内元素
 22 int GetHeightLinkStack(LinkStack* qstack);             //获取栈高度
 23 bool IsEmptyLinkStack(LinkStack * qstack);             //检测是否为空栈
 24 bool IsFullLinkStack(LinkStack* qstack);               //检测是否为满栈
 25 LinkStack* PushLinkStack(LinkStack * qstack, ElemType e);    //向栈内压入元素
 26 LinkStack* PopLinkStack(LinkStack * qstack, ElemType* e);    //将栈顶元素出栈
 27 int GetTopLinkStack(LinkStack * qstack);               //获取栈顶元素
 28 void ShowLinkStack(LinkStack* qstack);                 //遍历栈内元素
 29 
 30 //栈方法实现
 31 //创建一个空的栈
 32 LinkStack* CreateLinkStack() 
 33 {
 34     LinkStack* p = (LinkStack*)malloc(sizeof(LinkStack));
 35     if (p == nullptr)
 36         exit(-1);
 37     p->top = nullptr;//创建空栈
 38     p->num = 0;//
 39     return p;
 40 }
 41 //销毁栈
 42 void DestroyLinkStack(LinkStack* qstack)
 43 {
 44     ClearLinkStack(qstack);
 45     if (qstack)
 46         free(qstack);
 47 }
 48 //清空栈内元素
 49 void ClearLinkStack(LinkStack* qstack)
 50 {
 51     StackNode* p ;
 52     while (qstack->top)
 53     {
 54         p = qstack->top;
 55         qstack->top = qstack->top->next;
 56         qstack->num--;
 57         free(p);      
 58     }
 59 }
 60 //获取栈高度
 61 int GetHeightLinkStack(LinkStack* qstack)
 62 {
 63     return qstack->num;
 64 }
 65 //检测是否为空栈
 66 bool IsEmptyLinkStack(LinkStack* qstack)
 67 {
 68     return qstack->num==0;
 69 }
 70 //检测是否为满栈
 71 bool IsFullLinkStack(LinkStack* qstack)
 72 {
 73     return qstack->num == Max;
 74 }
 75 //向栈内压入元素
 76 LinkStack* PushLinkStack(LinkStack* qstack, ElemType e)
 77 {
 78     StackNode* p = (StackNode*)malloc(sizeof(StackNode));//申请新结点
 79     p->data = e;//给新结点赋值
 80     p->next = qstack->top;//新结点的下一个结点指向栈顶结点
 81     qstack->top = p;
 82     qstack->num++;  
 83     return qstack;
 84 }
 85 //将栈顶元素出栈
 86 LinkStack* PopLinkStack(LinkStack* qstack, ElemType* e)
 87 {
 88 
 89     if (IsEmptyLinkStack(qstack))
 90     {
 91         return nullptr;
 92     }
 93     else
 94     {
 95         StackNode* p = qstack->top;
 96         *e = qstack->top->data;//保存要弹出的元素
 97         qstack->top = p->next;//栈顶指针向后指
 98         free(p);//释放掉弹出结点的空间
 99         qstack->num--;//计数器减1       
100         return qstack;
101     }
102 }
103 //获取栈顶元素
104 int GetTopLinkStack(LinkStack* qstack)
105 {
106     return qstack->top->data;
107 }
108 //遍历栈内元素
109 void ShowLinkStack(LinkStack* qstack)
110 {
111     StackNode* q = qstack->top;
112     if (q == nullptr)
113         return;
114     cout << q->data << " ";
115     while (q->next)
116     {
117         q = q->next;
118         cout << q->data << " ";
119     }
120     cout << endl;
121 }
122 int main() {
123     LinkStack* lis = CreateLinkStack();;
124     LinkStack* p;
125     p = PushLinkStack(lis, 3);
126     p = PushLinkStack(lis, 4);
127     p = PushLinkStack(lis, 5);
128     p = PushLinkStack(lis, 6);
129     ShowLinkStack(p);
130     cout << GetTopLinkStack(lis) << endl;
131     int i = 5;
132     ElemType* e = &i;
133     PopLinkStack(lis, e);
134     ShowLinkStack(p);
135     cout << IsEmptyLinkStack(lis) << endl;
136     cout << IsFullLinkStack(lis) << endl;
137     ClearLinkStack(lis);
138     ShowLinkStack(p);
139     cout << IsEmptyLinkStack(lis) << endl;
140     cout << IsFullLinkStack(lis) << endl;
141     return 0;
142 
143 }