数据结构笔记(三): 栈的顺序存储结构与链式存储结构实现

发布于 / 程序猿 / 0 条评论

使用顺序存储结构(顺序表)链式存储结构(链表)来实现栈,完成栈的基本操作。若文中存在错误,敬请指出,感谢阅读。


基本知识

  • 栈的简介:栈是后进先出的容器
  • 栈的基本操作
#include <stack>
stack <int> s;
s.push();//压栈
s.pop();//出栈
s.top();//获取栈顶元素

栈是一种特殊的线性表,只是对它的插入和删除操作做了限定。栈只能在表尾(栈顶)进行插入和删除操作,遵从先进后出的规则。它的一些应用,像是文档编辑器中的撤销操作,网页的后退操作,还有编辑器的对递归函数的处理,和四则运算表达式求值都用到了栈这样的数据结构。


演示

  • 创建一个栈

  • 99入栈

  • 99出栈

  • 19出栈


代码:

  • 顺序存储结构
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int ARRAYLIST_INIT_SIZE = 1;

struct ArrayList_Tag
{
    int *elem;
    int length;
    int capacity;
};

typedef ArrayList_Tag* ArrayList; // 使用 ArrayList 代替 ArrayList_Tag*
typedef ArrayList ArrayStack; // 使用 ArrayStack 代替 ArrayStack

// 线性表操作

int _reserve(ArrayList List, int newCapacity) // 存储空间不足时重新分配内存
{
    // realloc()函数用法参照线性表实现中问题部分

    if (newCapacity <= List->capacity) // 原存储空间足够
        return 0;

    int *pt = NULL;
    if (!(pt=(int *)malloc(newCapacity*sizeof(int)))) // 内存分配失败返回-1
        return -1;

    for (int i = 0; i < List->length; ++i) // 内存分配成功则复制原有数据
        pt[i] = List->elem[i];

    free(List->elem); // 释放原有数据所占空间
    List->elem = pt;
    List->capacity = newCapacity;

    return 0;
}

ArrayList createArrayList() // 初始化--创建线性表
{
    ArrayList ret = NULL;
    if (!(ret = (ArrayList)malloc(sizeof(ArrayList_Tag)))) // ret内存分配失败返回NULL
        return NULL;

    ret->elem = NULL;
    if (!(ret->elem = (int*)malloc(ARRAYLIST_INIT_SIZE*sizeof(int)))) //ret中数据elem内存分配失败则释放ret空间并返回NULL
    {
        free(ret);
        return NULL;
    }
    ret->capacity = ARRAYLIST_INIT_SIZE; // 内存分配成功后初始化
    ret->length = 0;
    return ret;
}

int insertArrayList(ArrayList List, int pos, int newValue) // 插入
{
    if (pos < 0 || pos > List->length) // 插入位置不合法返回-1
        return -1;

    if (List->length == List->capacity) // 当前存储空间已满,重新分配内存
    {
        if (-1 == _reserve(List, List->capacity*2)) // 重新分配内存失败时返回-1
            return -1;
    }

    for (int i = List->length; i > pos; --i) // 插入操作
        List->elem[i] = List->elem[i-1];
    List->elem[pos] = newValue;
    ++List->length;
    return 0;
}

int removeArrayList(ArrayList List, int pos) // 删除
{
    if (pos < 0 || pos > List->length) // 删除位置不合法返回-1
        return -1;

    int i;
    for (i = pos; i < List->length; ++i) // 删除操作
        List->elem[i] = List->elem[i+1];
    --List->length;
    return 0;
}

int atArrayList(ArrayList const List, int pos, int *pResult) // 查询
{
    // 解决查询bug,使用第三个参数保存查询结果,也可使用引用

    if (pos < 0 || pos > List->length) // 查询位置不合法返回-1
        return -1;

    *pResult = List->elem[pos]; // 保存查询值
    return 0;
}

int destoryArrayList(ArrayList *pt) // 销毁线性表(回收空间)
{
    free((*pt)->elem);
    free(*pt);
    pt = NULL;
    return 0;
}


// 栈操作--调用线性表基本函数

ArrayStack createArrayStack() // 创建栈
{
    return createArrayList();
}

int pushArrayStack(ArrayStack Stack, int newValue) // 入栈
{
    return insertArrayList(Stack, Stack->length, newValue);
}

int topArrayStack(ArrayStack const Stack, int *pResult) // 取栈顶元素
{
    return atArrayList(Stack, Stack->length - 1, pResult);
}

int popArrayStack(ArrayStack Stack) // 出栈
{
    return removeArrayList(Stack, Stack->length-1);
}

int isEmptyArrayStack(ArrayStack Stack) // 判断栈是否为空
{
    return 0 == Stack->length; // 空返回true否则返回false
}

int destoryArrayStack(ArrayStack *pt) // 销毁栈回收空间
{
    return destoryArrayList(pt);
}



int main()
{
    int a[10] = {2, 5, 3, 4, 6, 8, 9, 7};
    ArrayStack A = createArrayStack();
    for (int i = 0; i < 8; ++i) // 将数组元素入栈
        pushArrayStack(A, a[i]);
    while (!isEmptyArrayStack(A)) // 如果栈不为空,则输出栈顶元素并出栈
    {
        int result = 0;
        topArrayStack(A, &result);
        cout << result << endl;
        popArrayStack(A);
    }
    destoryArrayStack(&A);
    return 0;
}

/*
7
9
8
6
4
3
5
2
*/
  • 链式存储结构
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

struct  Node
{
    int data; // 节点数据(存储当前节点数据)
    Node * next; // 节点指针(指向下一个指针)
};

typedef Node* LinkedList; // 使用LinkedList代替Node*

typedef LinkedList LinkedStack;  // 使用LinkedStack代替LinkedList

// 链表操作

Node* _advanceLinkedList(LinkedList List, int pos) // 用循环使指针找到相应位置
{
    Node* pt = List;
    int i = -1; // 初始位置从-1开始
    while (pt && i < pos)
    {
        pt = pt->next; // 后移一个节点
        ++i;
    }
    return pt; // 返回
}

LinkedList createLinkedList() // 创建链表
{
    LinkedList ret = NULL; // 初始化
    ret = (LinkedList)malloc(sizeof(LinkedList)); // 分配内存
    ret->next = NULL; // 指向空
    return ret;
}

int insertLinkedList(LinkedList List, int pos, int newvalue) // 插入
{
    Node* pt = _advanceLinkedList(List, pos - 1); // 找到插入位置前一个
    if (!pt) // 如果链表为空则返回-1
        return -1;

    Node* q = (Node *)malloc(sizeof(Node)); // 分配内存存储插入的值
    q->data = newvalue; // 三步操作完成插入
    q->next = pt->next;
    pt->next = q;
    return 0;
}

int removeLinkedList(LinkedList List, int pos) // 删除
{
    Node *pt = _advanceLinkedList(List, pos - 1); // 找到删除位置前一个
    if (!pt) // 如果链表为空则返回-1
        return -1;

    Node* q = pt->next; // 三步操作完成删除
    pt->next = q->next;
    free(q);
    return 0;
}

int atLinkedList(LinkedList const List, int pos, int *pResult) // 查询
{
    Node *pt = _advanceLinkedList(List, pos); // 找到查询位置
    if (!pt) // 如果链表为空则返回-1
        return -1;

    *pResult = pt->data; // 保存查询的值 -- 改掉线性表中bug
    return 0;
}

int sizeLinkedList(LinkedList const List) // 链表大小,无需修改故加const限定
{
    int ret = -1; // 初始位置从-1开始
    Node const *pt = List;
    while (pt) // 不停后移直至为空
    {
        pt = pt->next; // 后移一个节点
        ++ret;
    }
    return ret;
}

int destroyLinkedList(LinkedList *pt) //销毁线性表,回收内存
{
    while ((*pt)->next) // 不为空,则删除
        removeLinkedList(*pt, 0);
    free(pt); // 最后释放pt
    pt = NULL;
    return 0;
}

// 栈操作--调用链表基本函数

LinkedStack createLinkedStack() // 创建链表
{
    return createLinkedList();
}

int pushLinkedStack(LinkedStack stack,int newValue) // 入栈
{
    return insertLinkedList(stack,0,newValue);
}

int popLinkedStack(LinkedStack stack) // 出栈
{
    return removeLinkedList(stack,0);
}

int topLinkedStack(LinkedStack const stack,int*pResult) // 取栈顶元素
{
    return atLinkedList(stack,0,pResult);
}

int isEmptyLinkedStack(LinkedStack const stack) // 判断是否非空
{
    return 0 == sizeLinkedList(stack); // 空返回true否则返回false
}

int destroyLinkedStack(LinkedStack *pt) // 销毁栈回收空间
{
    return destroyLinkedList(pt);
}


int main()
{
    int a[10] = {2, 5, 3, 4, 6, 8, 9, 7};
    LinkedStack S = createLinkedStack();
    for (int i = 0; i < 8; ++i)
        pushLinkedStack(S, a[i]);
    while (!isEmptyLinkedStack(S))
    {
        int result = 0;
        topLinkedStack(S, &result);
        cout << result << endl;
        popLinkedStack(S);
    }
    return 0;
}

/*
7
9
8
6
4
3
5
2
*/

时间复杂度

  • 使用顺序表实现时,都在表尾进行插入删除操作,为0(1)
  • 使用链表实现时,都是在表头进行插入删除操作,为0(1)

本文及下文基础知识部分来自于博客园:栈的实现c++

最后,致敬迅哥


The end.
2017-10-26 星期四

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(三): 栈的顺序存储结构与链式存储结构实现
Not Comment Found