侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

kaixindeken
2021-04-18 / 0 评论 / 0 点赞 / 63 阅读 / 2,162 字

数组和链表,从逻辑角度来说,它们都是线性结构(就是排成一条线的结构,只有前后两个方向,非线性结构包括树、图等,后面会讲到),从存储角度来说,一个是顺序存储,一个是链式存储,各有利弊,数组需要预先申请连续内存,超出限制会溢出,但是对明确知道规模的小型数据集而言,使用数组会更加高效,随机访问的特性也更加方面数组读取,但插入和删除性能要差一些;链表的话没有空间限制,但是需要额外空间存储指针,插入、删除效率很高,但不支持随机访问。

虽说 PHP 中很少接触到这些,但是你学习使用 C 语言的话这些基础还是需要了解的。接下来我们要介绍两种特殊的线性结构,或者说用于满足特定场景需求的线性结构:栈和队列。

首先来看栈。

栈又叫堆栈,是限定只能在一端进行插入和删除操作的线性表,并且满足后进先出(LIFO)的特点。我们把允许插入和删除的一端叫做栈顶,另一个端叫做栈底,不含任何数据的栈叫做空栈。

栈支持通过数组/链表实现,通过数组实现的通常叫做顺序栈,通过链表实现的叫做链栈。下面通过 C++ 实现一个简单的顺序栈:

  • stack.hpp
#pragma once
#include<iostream>
using namespace std;
template <typename Type>//模板函数,有效区域该声明下面一行代码
class Stack {
private:
    Type *stk; //起始地址
    int top; //始终指向栈顶元素
    int MAXN;//栈的最大存储容量
public:
    Stack(int size) ; //构造函数,初始化一个栈时需要指定初始大小
    ~Stack() ;//析构函数
    int push(Type x);
    int pop(Type * px);
    Type getTop();
    int isEmpty ()const;
    int isFull ()const;
    int size()const;
};
template <typename Type>
//注意要加上尖括号模板,和普通变量类型不同
Stack<Type>::Stack(int size) {
    MAXN = size;
    stk = new Type[MAXN];
    top = -1;
}
template <typename Type>
Stack<Type>::~Stack() {
    delete stk;
}
template <typename Type>
int Stack<Type>::push(Type x) {
    if (top >= MAXN - 1)return -1;
    stk[++top] = x;
    return 0;
}
template <typename Type>
int Stack<Type>::pop(Type *x) {
    if (top == -1)return 0;
    *x = stk[top--];
}
template <typename Type>
Type Stack<Type>::getTop() {
    if (top == -1)return NULL;
    return stk[top];
}
template <typename Type>
int Stack<Type>::isEmpty()const {
    return top == -1;
}
template <typename Type>
int Stack<Type>::isFull()const {
    return top == MAXN - 1;
}
template <typename Type>
int Stack<Type>::size() const{
    return top+1;
}
  • main.cpp
#include <iostream>
#include "stack.hpp"

int main() {
    Stack<int> s(20);
    cout << "empty: " << s.isEmpty() << endl;
    s.push(100);
    s.push(50);
    s.push(10);
    cout <<"size: "<< s.size() << endl;
    int x = 0;
    s.pop(&x);
    cout <<"deleted element: "<< x << endl;
    cout <<"size after delete: "<< s.size()<<endl;
    cout << "top: " << s.getTop() << endl;
    return 0;
}

堆栈的概念比较简单,理解起来也不复杂,下面给出一个图示,帮助你形象了解栈的操作流程:

1.png

堆栈在日常开发和软件使用中,应用非常广泛,比如我们的浏览器前进、倒退功能,编辑器/IDE 中的撤销、取消撤销功能,程序代码中的函数调用、递归、四则运算等等,都是基于堆栈这种数据结构来实现的,就连著名的 stackoverflow 网站也是取「栈溢出」,需要求教之意。

0

评论区