定义:
栈(stack)是一种遵循先入后出逻辑的线性数据结构。
把栈顶部称为“栈顶”,底部称为“栈底”。将把元素添加到栈顶的操作叫作“入栈”,删除栈顶元素的操作叫作“出栈”。
分析:
栈的常用操作有:
1. 入栈;
2. 出栈;
3. 获取栈顶元素;
4. 获取栈大小;
5. 删除栈。
下面,采用链表结构实现栈:
代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//链表
typedef struct ListNode
{
int data;
ListNode *next;
};
//基于链表实现的栈
typedef struct StackNode
{
ListNode *top;
int size;
}LinkListStack;
//栈初始化(构造函数)
LinkListStack *creatLinkListStack()
{
LinkListStack *s = (LinkListStack *) malloc(sizeof(LinkListStack));
s->top = NULL;
s->size = 0;
return s;
}
//析构函数,删除栈
void delLinkedListStack(LinkListStack *s)
{
while(s->top){
ListNode *n = s->top->next;
free(s->top);
s->top = n;
}
free(s);
printf("栈已删除\n");
}
//获取栈的长度
int getSize(LinkListStack *s)
{
return s->size;
}
//判断栈是否为空
bool isEmpty(LinkListStack *s)
{
return getSize(s)==0;
}
//入栈
void push(LinkListStack *s,int num)
{
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->next = s->top;
node->data = num;
s->top = node;
s->size++;
}
//访问栈顶元素
int gettop(LinkListStack *s)
{
if(s->size == 0)
{
printf("栈为空\n");
return INT_MAX;
}
return s->top->data;
}
//出栈
int pop(LinkListStack *s)
{
int e = gettop(s);
ListNode *temp = s->top;
s->top=s->top->next;
free(temp);
temp=NULL;
s->size--;
return e;
}
//打印栈
void Print_Stack(LinkListStack *s)
{
if(s==NULL)
{
printf("栈已删除\n");
return ;
}
else
{
ListNode *p = s->top;
printf("\n栈中元素为:\n");
while(p)
{
printf("\t%d\n",p->data);
p=p->next;
}
printf("****************\n");
}
}
int main(){
LinkListStack *Stack = creatLinkListStack();
int num;
char op[10];
while(scanf("%s",op)!=EOF)
{
//入栈测试
if(strcmp(op,"push")==0)
{
scanf("%d",&num);
push(Stack,num);
}
//出栈测试
else if(strcmp(op,"pop")==0)
{
num=pop(Stack);
}
//打印栈
else if(strcmp(op,"show")==0)
{
Print_Stack(Stack);
}
//删除栈
else if(strcmp(op,"delete")==0)
{
delLinkedListStack(Stack);
}
//获取栈顶元素
else if(strcmp(op,"top")==0)
{
num = gettop(Stack);
printf("%d\n",num);
printf("****************\n");
}
}
return 0;
}
测试:
输入:
push 1
push 4
push 3
push 5
show
pop
show
pop
show
top
delete
输出:
栈中元素为:
5
3
4
1
****************栈中元素为:
3
4
1
****************栈中元素为:
栈已删除
4
1
****************
4
****************