栈

发表于   |   更新于 | 分类于
字数统计: 756

栈

基本概念

栈是一种特殊的线性表，它所有的插入和删除都限制在表的同一端及逆行，表重允许进行插入、删除操作的一端叫做栈的顶，表中的另一端叫做栈的底，当栈中没有元素时，称之为空栈，栈的插入运算通常称为进栈或入栈，栈的删除运算通常称为退栈或出栈。

抽象数据结构

1
2
3
4
5
6
7
8
ADT Stack is
    operation
    Stack createEmptyStack(void)/*创建一个空栈*/
    int isEmptyStack(Stack st)/*判断栈st是否为空*/
    void push(Stack st,DataType x)/*往栈st的栈顶插入一个值为x的元素*/
    void pop(Stack st)/*从栈st的栈顶删除一个元素*/
    DataType top(Stack st)/*求栈顶元素的值*/
end ADT Stack

栈的顺序实现

用顺序的方式表示栈时，栈的类型可定义如下：

1
2
3
4
5
6
struct SeqStack{/*顺序栈类型定义*/
    int MAXNUM;/*栈中最大元素个数*/
    int t;/*t<MAXNUM,指示栈顶位置，而不是元素个数*/
    DataType *s;
};
typedef struct SeqStack * PSeqStack;/*顺序栈指针类型*/

由于栈是一个动态结构，而数组是静态结构，因此会出现溢出问题。当栈中已经有MAXNUM个元素时，如果再做进栈运算，则会产生溢出，通常称为上溢（overflow），而对空栈进行出栈运算时也会产生溢出，通常称为下溢（underflow)。

进栈运算

1
2
3
4
5
6
7
8
9
10
11
void push_seq(PSeqStack pastack,DataType x)
{
    /*在栈内压入一个元素*/
    if(pastack->t >= MAXNUM-1)
        printf("Overflow!\n");
    else
    {
        pastack->t = pastack->t+1;
        pastack->s[pastack->t] = x;
	}
}

出栈运算

1
2
3
4
5
6
7
8
void pop_seq(PSeqStack pastack)
{
    /*删除栈顶元素*/
    if(pastack->t == -1)
        printf("Underflow!\n");
    else
        pastack->t = pastack->t-1;
}

取栈顶元素

1
2
3
4
5
6
7
8
DataType top_seq(PSeqStack pastack)
{
    /*当pastack所指的栈不为空栈时，求栈顶元素的值*/
    if(pastack->t == -1)
        printf("It is empty!\n");
    else
        return (pastack->s[pastack->t]);
}

链接表示

每个节点的结构可以定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct Node;/*单链表节点*/
typedef struct Node * PNode;/*指向节点的指针类型*/
struct Node
{
    /*单链表节点定义*/
    DataType info;
    Pnode link;
};

/*为了强调栈顶是栈的一个属性，对栈增加了一层封装，引入LinkList结构的定义*/
struct LinkStack/*链接栈类型定义*/
{
    PNode top;/*指向栈顶节点*/
}
typedef struct LinkStack *PLinkStack;
/*链接栈类型的指针类型*/

创建空链接栈

1
2
3
4
5
6
7
8
9
10
PLinkStack createEmptyStack_link(void)
{
    PLinkStack plstack;
    plstack = (PLinkStack)malloc(sizeof(struct LinkStack));
    if(plstack != NULL)
        plstack->top = NULL;
    else
        printf("Out of space!\n");
    return plstack;
}

判断栈是否为空

1
2
3
4
int isEmptyStack_link(PLinkStack plstack)
{
    return (plstack->top==NULL);
}

进栈运算

1
2
3
4
5
6
7
8
9
10
11
12
13
void push_link(PLinkStack plstack,DataType x)
{
    PNode p;
    p = (PNode)malloc(sizeof(struct Node));
    if(p==NULL)
        printf("Out of space!\n");
    else
    {
        p->info=x;
        p->link=plstack->top;
        plstack->top=p;
    }
}

出栈运算

1
2
3
4
5
6
7
8
9
10
11
12
void pop_link(PLinkStack plstack)    
{
    PNode p;
    if(isEmptyStack_link(plstack))
        printf("Empty stack pop!\n");
    else
    {
        p=plstack->top;
        plstack->top = plstack->top->link;
        free(p);
    }
}

取栈顶元素

1
2
3
4
5
6
7
DataType top_link(PLinkStack plstack)
{
    if(pastack->top == NULL)
        printf("Stack is empty!\n");
    else
        return (plstack->top->info);
}