用单链表实现栈的定义和实现

#include<iostream> using namespace std; struct Node; typedef struct Node* PtrToNode; typedef PtrToNode Stack; typedef PtrToNode Position; //创建栈节点 struct Node { int element;//节点数据域 PtrToNode next;//指针域 }; //判断栈是否为空 int IsEmpty(Stack S) { return S->next == NULL; } //弹出数据 int Pop(Stack S) { int X; PtrToNode FirstCell; if (IsEmpty(S)) return -1; else { FirstCell = S->next;//将头结点赋值给暂时存储位置 S->next = S->next->next; X = FirstCell->element;//弹出的数据 free(FirstCell);//free掉第一个即最后一个输入的数据 cout << "弹出" << X << endl; return 0; } cout << endl; } //置空数据 int MakeEmpty(Stack S) { if (S == NULL) return -1; else while (!IsEmpty(S)) Pop(S); return 0; } //创建栈 Stack CreateStack() { Stack S = (PtrToNode)malloc(sizeof(struct Node)); S->next = NULL; return S; } //将数据输入到栈中 int Push(int X, Stack S) { PtrToNode TmpCell; TmpCell = (PtrToNode)malloc(sizeof(struct Node)); if (TmpCell == NULL) return -1; else { TmpCell->element = X; TmpCell->next = S->next; S->next = TmpCell; return 0; } } //返回栈顶 int Top(Stack S) { int x; if (!IsEmpty(S)) { x = S->next->element; return x; } return -1; } //输出栈中的内容 void Show(Stack& S) { Position p = S->next; if (p == NULL) cout << "栈已空！" << endl; else { while (p != NULL) { cout << p->element << " "; p = p->next; } } cout << endl; } int main() { //创建栈测试 cout << "-----------创建栈测试------------" << endl; Stack S; S = CreateStack(); for (int i = 0; i < 10; i++) { Push(i, S); } Show(S); cout << "-----------栈顶测试------------" << endl; cout << "栈顶:" << Top(S) << endl; cout << "-----------弹出栈测试------------" << endl; Pop(S); MakeEmpty(S); cout << "栈置空后："; Show(S); cout << "-----------输入栈测试------------" << endl; cout << "输入10后的栈："; Push(10, S); Show(S); cout << "-----------输入栈后栈顶测试------------" << endl; cout << "栈顶:"; cout<<Top(S); return 0; }