文章目录
- 1.用C的方式实现栈
- 2.用C++数据抽象的方式实现栈
1.用C的方式实现栈
（1）入栈
往栈中压入一个数据项的过程：
初始状态：head——>NULL;栈的头指针head指向NULL
生成一个新的节点node1，将node1的next指针指向头指针head指向的节点NULL，然后将头指针head指向新插入的节点，然后断开head——>NULL;
再产生一个节点node2，让后让该节点的next指针域指向head指针指向的节点，然后将头指针指向新插入的节点，然后断开上面的head——>node1;
（2）出栈
将头节点node2出栈出来，然后将头指针指向其下一个节点node1，以此类推
- eg：20cpp\20cpp\20cpp\01.cpp
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//栈内部的数据结构用链表来表示
struct Link
{
int data;//链表存储的数据类型
struct Link* next;//链表的指针域
};
struct Stack
{
struct Link* head;//指向链表头节点的指针
int size;//栈的大小
};
//栈的初始化
void StackInit(struct Stack* stack)
{
stack->head = NULL;//栈的头指针置为空
stack->size = 0;//栈的大小为0
}
//入栈：往栈中压入一个数据项
void StackPush(struct Stack* stack, const int data)
{
//先创建一个节点
struct Link* node;
node = (struct Link*)malloc(sizeof(struct Link));
assert(node != NULL);
node->data = data;
node->next = stack->head;//新创建一个节点node，其next指针域应指向头节点
stack->head = node;//然后将头指针指向新创建的节点
++stack->size;
}
int StackEmpty(struct Stack* stack)
{
return (stack->size == 0);
}
//出栈
int StackPop(struct Stack* stack, int* data)
{
//判定栈是否为空，只需盘点栈的大小是否为0
if (StackEmpty(stack))
{
return 0;
}
//保存原来的头节点，因为头节点发生了改变，所以要保存原来的头节点
struct Link* tmp = stack->head;
//将头节点出栈
*data = stack->head->data;
//将头指针指向下一个节点
stack->head = stack->head->next;
//把一个节点出栈，所以要将以前的头节点释放掉
free(tmp);
--stack->size;
return 1;
}
void StackCleanup(struct Stack* stack)
{
struct Link* tmp;
while (stack->head)
{
//tmp指向下一个节点，然后将tmp释放掉
tmp = stack->head;
stack->head = stack->head->next;
free(tmp);
}
stack->size = 0;
}
int main(void)
{
struct Stack stack;
StackInit(&stack);
int i;
for (i=0; i<5; i++)
{
StackPush(&stack, i);
}
while (!StackEmpty(&stack))
{
StackPop(&stack, &i);
printf("%d ", i);
}
printf("\n");
return 0;
}
- 测试：
用c实现
2.用C++数据抽象的方式实现栈
- eg：20cpp\20cpp\20cpp\02.cpp
#include <iostream>
using namespace std;
/*
struct Link
{
int data;
struct Link* next;
};
struct Stack
{
struct Link* head;
int size;
};
void StackInit(struct Stack* stack)
{
stack->head = NULL;
stack->size = 0;
}
void StackPush(struct Stack* stack, const int data)
{
struct Link* node;
node = (struct Link*)malloc(sizeof(struct Link));
assert(node != NULL);
node->data = data;
node->next = stack->head;
stack->head = node;
++stack->size;
}
int StackEmpty(struct Stack* stack)
{
return (stack->size == 0);
}
int StackPop(struct Stack* stack, int* data)
{
if (StackEmpty(stack))
{
return 0;
}
struct Link* tmp = stack->head;
*data = stack->head->data;
stack->head = stack->head->next;
free(tmp);
--stack->size;
return 1;
}
void StackCleanup(struct Stack* stack)
{
struct Link* tmp;
while (stack->head)
{
tmp = stack->head;
stack->head = stack->head->next;
free(tmp);
}
stack->size = 0;
}
int main(void)
{
struct Stack stack;
StackInit(&stack);
int i;
for (i=0; i<5; i++)
{
StackPush(&stack, i);
}
while (!StackEmpty(&stack))
{
StackPop(&stack, &i);
printf("%d ", i);
}
printf("\n");
return 0;
}
*/
class Stack
{
//这个栈的内部用链表来实现
//嵌套类的默认数据成员是公有的
//结构体实际上也是一个类，也可以定义构造函数
struct Link
{
int data_;
Link* next_;
Link(int data, Link* next) : data_(data), next_(next)
{
}
};
public:
//C语言中的NULL是：(void*)0
//C++中的NULL=0，因为0赋值给指针，C++会自动做转换
//栈的初始化用构造函数
Stack() : head_(0), size_(0)
{
}
//StackCleanup栈的释放用析构函数来实现
~Stack()
{
Link* tmp;
while (head_)
{
tmp = head_;
head_ = head_->next_;
delete tmp;
}
}
void Push(const int data)
{
Link* node = new Link(data, head_);
head_ = node;//然后将头指针指向新创建的节点
++size_;
}
bool Empty()
{
return (size_ == 0);
}
bool Pop(int& data)
{
if (Empty())
{
return false;
}
Link* tmp = head_;
data = head_->data_;
head_ = head_->next_;
delete tmp;//释放掉原来的头节点
--size_;
return true;
}
private:
Link* head_;//链表的头指针
int size_;//栈的大小
};
//C++与C区别（1）
// 避免名称冲突，C语言：StackPush，C++是Push，作用域在类内，完全不用担心
//或者使用namespace A
/*
namespace A
{
}
使用时：A::Stack，加上名称空间A
*/
//C++与C区别（2）
// 类型的扩充，指的是：类类型
//C++与C区别（3）
// 数据封装、能够保护内部的数据结构不遭受外界破坏，指的是：私有数据成员
int main(void)
{
Stack stack; // 抽象数据类型 类类型
int i;
for (i=0; i<5; i++)
{
//与C相比，每个函数的传递不必传递栈的地址
//StackPush(&stack, i);
stack.Push(i); // 其实第一个参数是：this = &stack，是隐含的this指针，指向stack
}
//while (!StackEmpty(&stack))
while (!stack.Empty())
{
//StackPop(&stack, &i);
//printf("%d ", i);
stack.Pop(i);
cout<<i<<" ";
}
//printf("\n");
cout<<endl;
return 0;
}
- 测试：
用c++实现
