算法

数据结构(四):栈

2018-11-21  本文已影响1人  渔父歌

一、栈的定义

栈是只能在一端进行插入和删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。栈顶的位置是动态的,由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。

当栈中没有元素时,称为空栈。栈的插入操作通常称为入栈或者进栈,栈的删除操作一般称作出栈或者退栈。

栈的主要特点是 ”后进先出“ ,即后进栈的元素先出栈。每次进栈的元素都放在原来栈顶元素之前,成为新的栈顶元素,每次出栈的元素都是当前栈顶元素。所以栈也被称为后进先出表。

栈的抽象数据类型定义如下:

ADT List
{
    数据对象:
        D={a(i)|1=<i<=n, a(i)是 ElemType类型}
    数据关系:
        R={<a(i), a(i+1)>|a(i),a(i+1)属于 D, i=1,2,3,···,n-1}
    基本运算:
        InitStack(&s): 初始化栈,构建一个空栈 s
        ClearStack(&s): 销毁栈:释放栈 s所占的内存空间
        StackLength(s): 求栈的长度: 返回栈 s中的元素个数
        StackEmpty(s): 判断栈是否为空:若栈 s为空则返回真,否则返回假
        Push(&s, e): 进栈:将元素 e添加到栈顶
        Pop(&s, &e): 出栈:将栈顶元素赋值给 e并从栈顶删除
        GetTop(s, &e): 取栈顶元素:将当前栈顶元素的值赋值给 e
        DispStack(s):显示栈中所有元素的值:按照从栈顶到栈底的顺序显示栈中所有元素的值
}

二、栈的顺序存储结构与基本运算

使用顺序存储结构存储栈时,我们会分配一块连续的内存空间来存放栈中的元素,并用一个变量指向当前的栈顶。采用顺序存储结构的栈称为顺序栈。

定义顺序栈的结合体时,我们假设栈能够存储的最大元素数量为 MaxSize,指向栈顶的变量为 STop(在顺序存储结构中 STop是一个整数,表示当前栈顶元素的下标),存放栈中元素的数组 data。

所以我们可以定义栈的结构体为:

#define MaxSize 100

typedef char ElemType;
typedef struct Stack{
    int STop;
    ElemType data[MaxSize];
}Stack;

这里栈的最大大小我们通过宏来定义,在实现时也可以使用其他的方法定义,比如在栈中再加一个 MaxSize,data改为一个 ElemType[] 类型的指针,在初始化栈时,通过 malloc函数读取 MaxSize来为 data分配内存。

1、栈的初始化

void InitStack(Stack* &s) {
    s = (Stack*)malloc(sizeof(Stack));
    s->STop = -1;
 }//InitStack

在初始化函数里我我们把 s->STop赋值为 -1,以此来标记栈 s是空栈。

也可以把 STop赋值为 0,这与 -1区别不大,只是当初始化为 -1时 STop总是指向栈顶元素,而初始化为 0时 STop总是指向栈顶元素的前一位。

2、销毁栈

void ClearStack(Stack* &s) {
    free(s);
    s = NULL;
}//ClearStack

3、求栈的长度

int StackLength(Stack* s) {
    return s->STop + 1;
}//StackLengt

这里我们返回 STop+1是因为 STop总是指向栈顶元素,而栈顶元素的下标就是数组元素个数减一。

当 STop初始化为 0时我们就可以直接返回 STop。

4、判断栈是否为空

bool StackEmpty(Stack* s) {
    if (s->STop < 0) {
        return true;
    }
    else{
        return false;
    }
}//StackEmpty

5、进栈

void Push(Stack* &s, ElemType e) {
    s->STop++;
    
    if (s->STop > MaxSize || s->STop < 0) {
        throw;
    }
    else{
        s->data[s->STop] = e;
    }
}//Push

6、出栈

void Pop(Stack* &s, ElemType &e) {
    if (!StackEmpty(s)) {
        e = s->data[s->STop];
        s->STop--;
    }
    else {
        throw;
    }
}//Pop

7、取栈顶元素

void GetTop(Stack* s, ElemType &e) {
    if (!StackEmpty(s)) {
        e = s->data[s->STop];
    }
    else {
        throw;
    }
}//GetTop

8、打印栈

void DispStack(Stack* s) {
    if (StackEmpty(s)) {
        printf("stack is empty.\n");
    }
    else {
        int top = s->STop;
        while (top >= 0) {
            printf("index: %d, value: %c\n", top, s->data[top]);
            top--;
        }
    }
}//DispStack

三、栈的链式存储结构与基本运算

栈的链式存储结构叫做链栈,通常用单链表实现。链栈的有点是不用考虑满栈的情况,操作也很方便,我们只要在头节点处操作就行。最靠近头节点的节点是栈顶节点,而链表中与头节点相对的一端则是栈底。

链栈中节点的结构定义如下:

typedef char ElemType;
typedef struct LinkStack {
    ElemType data;
    struct LinkStack* next;
}LinkStack;

1、链栈的初始化

void InitStack(LinkStack* &s) {
    s = (LinkStack*)malloc(sizeof(LinkStack));
    s->next = NULL;
}

2、销毁链栈

void ClearStack(LinkStack* &s) {
    while(s->next != NULL) {
        LinkStack* temp = s->next->next;
        free(s->next);
        s->next = temp;
    }
    free(s);
    s = NULL;
}

3、求链栈的长度

int StackLength(LinkStack* s) {
    int i = 0;
    while (s->next != NULL) {
        i++;
        s->next = s->next->next;
    }
    return i;
}

4、判断链栈是否为空

bool StackEmpty(LinkStack* s) {
    return s->next == NULL;
}

5、进栈

void Push(LinkStack* &s, ElemType e) {
    LinkStack* new_node = (LinkStack*)malloc(sizeof(LinkStack));
    if (new_node == NULL) {
        throw;
    }

    new_node->data = e;
    new_node->next = s->next;
    s->next = new_node;
}

链栈进栈与单链表添加节点很相似,只是链栈进栈时我们只在头节点后面添加节点,而单链表则可以在链表的任意位置添加节点。

6、出栈

void Pop(LinkStack* &s, ElemType &e) {
    if (StackEmpty(s)) {
        throw;
    }

    LinkStack* temp = s->next;
    e = temp->data;
    s->next = temp->next;
    free(temp);
}

7、取栈顶元素

void GetTop(LinkStack* s, ElemType &e) {
    if (StackEmpty(s)) {
        throw;
    }

    e = s->next->data;
}

8、打印栈

void DispLStack(LinkStack* s) {
    LinkStack* temp = (LinkStack*)malloc(sizeof(LinkStack));
    *temp = *s;

    int i = 0;
    while (temp->next != NULL) {
        i++;
        printf("index: %d, value: %c\n", i, temp->next->data);
        temp->next = temp->next->next;
    }
}

这里使用一个 temp作为中间变量是为了避免直接修改 s所指向的内存。

上一篇下一篇

猜你喜欢

热点阅读