一、概念
1、栈的定义
栈是仅限在表尾进行插入和删除的线性表。
栈又被称为后进先出(Last In First Out)的线性表,简称LIFO。
2、栈顶
栈是一个线性表,我们把允许插入和删除的一端称为栈顶
3、栈底
和栈顶相对,另一端称为栈底
二、接口
1、可写接口
(1)数据入栈
栈的插入操作,叫做入栈,也可称为进栈、压栈。
代表了两次入栈
(2)数据出栈
栈的删除操作,叫做出栈,也可以叫做弹栈
代表出了一次栈
(3)清空栈
一直出栈,直到栈为空
2、只读接口
(1)获取栈顶数据
对于一个栈来说只能获取栈顶数据,一般不支持获取其它数据
(2)获取栈元素个数
栈元素个数一般用一个额外变量存储,入栈时加一,出栈时减一
(3)栈的判空
当栈元素个数为零时,就是一个空栈,空栈不允许出栈操作
三、顺序表实现
1.数据结构定义
#define DataType int // (1)定义为整型
#define maxn 100005 // (2)代表栈的最大元素个数
struct Stack { // (3)结构体
DataType data[maxn]; // (4)栈元素存储方式-数组
int top; // (5)栈顶指针
};
2.入栈
void StackPushStack(struct Stack *stk, DataType dt) { // (1)stk指向栈对象的指针
stk->data[ stk->top ] = dt; // (2)将入栈的元素放入栈中
stk->top = stk->top + 1; // (3)栈顶指针上移
}
可将代码简洁写为:
void StackPushStack(struct Stack *stk, DataType dt) {
stk->data[ stk->top++ ] = dt;
}
3、出栈
void StackPopStack(struct Stack* stk) {
--stk->top;
}
直接将栈顶元素减一下移即可
4、清空栈
对于数组来说,我们将栈顶指针直接置为栈底,也就是数组下标为0即可,下次入栈的时候会将之前的内存重复使用
void StackClear(struct Stack* stk) {
stk->top = 0;
}
5、只读接口
DataType StackGetTop(struct Stack* stk) {
服务器托管网 return stk->data[ stk->top - 1 ]; // (1)获取栈顶元素
}
int StackGetSize(struct Stack* stk) {
return stk->top; // (2)获取栈元素个数
}
bool StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk); // (3)判断栈是否为空
}
6、栈的顺序表实现源码
#define DataType int
#define bool int
#define maxn 100010
struct Stack {
DataType data[maxn];
int top;
};
void StackClear(struct Stack* stk) {
stk->top = 0;
}
void StackPushStack(struct Stack *stk, DataType dt) {
stk->data[ stk->top++ ] = dt;
}
void StackPopStack(struct Stack* stk) {
--stk->top;
}
DataType StackGetTop(struct Stack* stk) {
return stk->data[ stk->top - 1 ];
}
int StackGetSize(struct Stack* stk) {
return stk->top;
}
bool StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk);
}
四、栈的链表实现
1.、数据结构定义
typedef int DataType; // (1)栈结点的数据域
struct StackNode; // (2)链表结点声明
struct StackNode { // (3)data为数据域,*next指针域
DataType data;
struct StackNode *next;
};
struct Stack {
struct StackNode *top; // (4)栈顶指针
int size; // (5)栈的元素个数,也就是链表的长度
};
2、入栈
类似头插法
void StackPushStack(struct Stack *stk, DataType dt) {
// (1)创建一个结点
struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) );
insertNode->next = stk->top; // (2)当前结点指向栈顶结点
insertNode->data = dt; // (3)赋值
stk->top = insertNode; // (4)栈顶指针指向新创建的结点
stk->size++; // (5)栈元素个数加一
}
3、出栈
出栈过程就是删除这个链表的头结点
void StackPopStack(struct Stack* stk) {
struct StackNode *temp = stk->top; // (1)temp指向栈顶元素
stk->top = temp->next; // (2)栈顶指针执行它的下一个结点
free(temp); // (3)将temp对应的结点释放
stk->size--; // (4)栈元素个数减一
}
4、清空栈
void StackClear(struct Stack* stk) {
while(!StackIsEmpty(stk)) { // (1)栈不为空
StackP服务器托管网opStack(stk); // (2)执行出栈操作
}
stk->top = NULL; // (3)将栈指针置NULL
}
5、只读接口
DataType StackGetTop(struct Stack* stk) {
return stk->top->data; // (1)获取栈顶元素
}
int StackGetSize(struct Stack* stk) {
return stk->size; // (2)栈元素个数
}
int StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk); //判空
}
6、栈的链表实现源码
typedef int DataType;
struct StackNode;
struct StackNode {
DataType data;
struct StackNode *next;
};
struct Stack {
struct StackNode *top;
int size;
};
void StackPushStack(struct Stack *stk, DataType dt) {
struct StackNode *insertNode = (struct StackNode *) malloc( sizeof(struct StackNode) );
insertNode->next = stk->top;
insertNode->data = dt;
stk->top = insertNode;
stk->size++;
}
void StackPopStack(struct Stack* stk) {
struct StackNode *temp = stk->top;
stk->top = temp->next;
stk->size--;
free(temp);
}
DataType StackGetTop(struct Stack* stk) {
return stk->top->data;
}
int StackGetSize(struct Stack* stk) {
return stk->size;
}
int StackIsEmpty(struct Stack* stk) {
return !StackGetSize(stk);
}
void StackClear(struct Stack* stk) {
while(!StackIsEmpty(stk)) {
StackPopStack(stk);
}
stk->top = NULL;
stk->size = 0;
}
五、两种实现的优缺点
1、顺序表实现
入栈和出栈的常数时间复杂度低,清空栈时间复杂度是O(1)
不足之处是需要预习申请好空间,而且当空间不够时需要申请空间
2、链表实现
入栈和出栈的常数时间复杂度略高,清空栈的时间复杂度为O(n)
好处是不用预先分配空间,可以一直入栈。
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
活动地址:毕业季·进击的技术er 大学是人生的第一次选择,而毕业面临的是第二次选择,两次选择有很强的关联性,但不是最终选择的前置条件!人生很短,选择很多,但决定人生的往往就在那关键几步,但人往往是不知道自己未来的命运的,也只能通过事后判断才知道自己当初的决…