今天学习了栈的C++实现，跟单链表很像：
push相当于单链表在第一个位置插入元素；
pop相当于单链表在第一个位置删除元素；
1、空栈检查
int stack::isEmpty(Stack *S)
{
return S->next == NULL;
}
2、创建一个空栈
stack::Stack *stack::createStack()
{
Stack *S;
S = (Stack*)new(Stack);
//栈空间满后，溢出
if (S == NULL)
cout << "Out of space! " << '\n';
S->next = NULL;
makeEmpty(S);
return S;
}
空栈只有头结点，第9行表示若不为空栈则删除除头结点以外的所有结点。
3、清空栈（保留头结点）
void stack::makeEmpty(Stack *S)
{
if (isEmpty(S))
cout << "Donnot need to makeEmpty!" << '\n';
else
while (!isEmpty(S))
pop(S);
}
4、push操作
stack::Stack *stack::push(int x, Stack *S)
{
Stack *tem;
tem = (Stack*)new(Stack);
if (tem == NULL)
{
cout << "Out of space! " << '\n';
}
else
{
cout << "please input the data to push: " << '\n'; scanf_s("%d",&x); tem->Data = x;
tem->next = S->next;
S->next = tem;
return S;
}
}
5、top操作
int stack::top(Stack *S)
{
if (isEmpty(S))
{
cout << "Empty stack! " << '\n';
return -;
}
else
return S->next->Data;
}
6、pop操作（释放第一个结点后，显示该结点的数据元素）
stack::Stack *stack::pop(Stack *S)
{
Stack *p;
p = NULL;
if (isEmpty(S))
cout << "Empty stack! " << '\n';
else
{
p = S->next;
cout << "the Data be poped is : " << p->Data << endl;
S->next = p->next;
free(p);
return S;
}
}
7、处理栈（删除包括头结点）
void stack::disposeStack(Stack *S)
{
if (S == NULL)
cout << "Donnot need to disposeStack! " << '\n';
while (!isEmpty(S))
pop(S);
free(S);
}
8、主函数
int main()
{
cout << '\n' << "***************************************" << '\n' << '\n';
cout << "Welcome to the stack world! " << '\n';
cout << '\n' << "***************************************" << '\n' << '\n'; int i = ;
int j = ;
int topElement = ;
stack *a = new stack;
stack::Stack *S = NULL;
int x = ;
while (i)
{
cout << '\n' << "***************************************" << '\n';
cout << " 0 : end the stack " << '\n';
cout << " 1 : creat a stack " << '\n';
cout << " 2 : display the top element of stack " << '\n';
cout << " 3 : push a node in the stack " << '\n';
cout << " 4 : pop a node from the stack " << '\n';
cout << "***************************************" << '\n';
cout << "Please input the function your want with the number above : " << '\n';
scanf_s("%d", &j); switch (j)
{
case :
cout << "CreatStack now begin : ";
S = a->createStack();
break;
case :
topElement = a->top(S);
cout << "The top element of stack is : " << topElement;
break;
case :
cout << "push now begin : ";
S = a->push(x, S);
break;
case :
cout << "pop now begin : ";
S = a->pop(S);
break;
default:
cout << "End the stack. ";
a->disposeStack(S);
i = ;
break;
} }
}
运行结果：