数据结构——栈
定义
限定仅在表尾进行插入和删除操作的线性表。(先入后出)
顺序结构
C定义
[cpp]
#define MAXSIZE 20
#pragma mark 顺序栈
typedef int SElemType;
typedef struct {
SElemType data[MAXSIZE];
int top;
}SqStack;
#define MAXSIZE 20
#pragma mark 顺序栈
typedef int SElemType;
typedef struct {
SElemType data[MAXSIZE];
int top;
}SqStack;
压栈操作
[cpp]
int Push(SqStack *S, SElemType e)
{
if (S->top == MAXSIZE -1)
return 0;
S->data[++S->top] = e;
return 1;
}
int Push(SqStack *S, SElemType e)
{
if (S->top == MAXSIZE -1)
return 0;
S->data[++S->top] = e;
return 1;
}
弹栈操作
[cpp]
int Pop(SqStack *S, SElemType *e)
{
if (S->top == -1)
return 0;
*e = S->data[S->top--];
return 1;
}
int Pop(SqStack *S, SElemType *e)
{
if (S->top == -1)
return 0;
*e = S->data[S->top--];
return 1;
}
共享栈
共享栈可以看做是两个顺序栈倒下,栈尾相对的数据结构。通常在两个栈空间需求有相反关系时使用,例如买入就要卖出等等。
C定义
[cpp]
typedef struct {
SElemType data[MAXSIZE];
int top1;
int top2;
}SqDoubleStack;
typedef struct {
SElemType data[MAXSIZE];
int top1;
int top2;
}SqDoubleStack;
压栈
[cpp]
int PushDouble(SqDoubleStack *S, SElemType e, int stackNumber)
{
//栈满
if (S->top1 + 1 == S->top2)
return 0;
if (stackNumber == 1)
S->data[++S->top1] = e;
else if (stackNumber == 2)
S->data[--S->top2] = e;
return 1;
}
int PushDouble(SqDoubleStack *S, SElemType e, int stackNumber)
{
//栈满
if (S->top1 + 1 == S->top2)
return 0;
if (stackNumber == 1)
S->data[++S->top1] = e;
else if (stackNumber == 2)
S->data[--S->top2] = e;
return 1;
}
弹栈
[cpp]
int PopDouble(SqDoubleStack *S, SElemType *e, int stackNumber)
{
if (stackNumber == 1)
if (S->top1 == -1)
return 0;
*e = S->data[S->top1--];
if (stackNumber == 2)
if (S->top2 == MAXSIZE)
return 0;
*e = S->data[S->top2++];
return 1;
}
int PopDouble(SqDoubleStack *S, SElemType *e, int stackNumber)
{
if (stackNumber == 1)
if (S->top1 == -1)
return 0;
*e = S->data[S->top1--];
if (stackNumber == 2)
if (S->top2 == MAXSIZE)
return 0;
*e = S->data[S->top2++];
return 1;
}
链栈
栈的链式存储结构类似于线性表中的链式存储结构。
C定义
[cpp]
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack{
LinkStackPtr top;
int count;
}LinkStack;
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack{
LinkStackPtr top;
int count;
}LinkStack;
压栈
[cpp]
int PushLink(LinkStack *S,SElemType e)
{
LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
p->data = e;
p->next = S->top;
S->top = p;
S->count++;
return 1;
}
int PushLink(LinkStack *S,SElemType e)
{
LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
p->data = e;
p->next = S->top;
S->top = p;
S->count++;
return 1;
}
弹栈
[cpp]
int PopLink(LinkStack *S,SElemType *e)
{
LinkStackPtr p;
*e = S->top->data;
p = S->top;
S->top = S->top->next;
free(p);
S->count--;
return 1;
}
int PopLink(LinkStack *S,SElemType *e)
{
LinkStackPtr p;
*e = S->top->data;
p = S->top;
S->top = S->top->next;
free(p);
S->count--;
return 1;
}
对比顺序栈和链栈
两个数据结构操作都不复杂,时间复杂度相同为O(1)。
顺序栈需要固定的长度,但是存取时定位方便。
链栈要求有指针域,因此需要增加一些内存开销,但不同于顺序栈限制长度。
栈的应用 —— 递归
例如比较有名的斐波那契数列:
[cpp]
int Fbi(int i)
{
if (i < 2)
return i == 0? 0: 1;
return Fbi(i - 1) + Fbi(i - 2);
}
int Fbi(int i)
{
if (i < 2)
return i == 0? 0: 1;
return Fbi(i - 1)
补充:软件开发 , C++ ,