文档章节

堆栈的实现

陈洪波
 陈洪波
发布于 2015/05/19 19:33
字数 1084
阅读 29
收藏 1

堆栈,是一种数据结构,其插入和删除操作都在同一端进行,其中一端称作栈顶,另外一端称作栈底。其中,堆栈是一种先进后出的数据结构,既可以使用公式化描述实现,也可以使用链表描述进行实现。

例如,我们向栈中插入元素10,20.30,则从栈顶向栈底排列分别为30,20,10,则弹出的时候,分别以30,20,10的顺序弹出,在这篇中,先使用公式化描述和链表实现堆栈,在后面将学习几个使用堆栈的比较典型的例子,其中包括括号匹配,汉诺塔,火车重排,离线等价类,迷宫等问题。

好了,话不多说,堆栈的实现还是比较简单的,下面附上我的代码:

首先使用公式化描述实现的堆栈:

/** * 堆栈是一个线性表,其插入和删除操作都在同一端进行 * 其中一端成为栈顶,另一端成为栈底 * * 堆栈是一种先进后出或者是后进先出的数据结构 * 可以使用公式化描述实现堆栈,也可以使用链表实现堆栈 * */
#include "Exception.h"
#include <iostream>

using namespace std;

/** * 适用公式化描述实现LinearStack */
template<class T>
class LinearStack{
public:
    LinearStack(int MaxLinearStackSize = 10);
    ~LinearStack(){delete [] stack;}
    bool isEmpty() const{return top == -1;}    //返回栈是否为空
    bool isFull() const{return top == MaxTop;} //栈是否已满
    T Top() const;  //获取栈顶元素
    LinearStack<T>& Add(const T& x);    //向栈中添加一个元素
    LinearStack<T>& Delete(T& x);   //从栈中删除一个元素
    int Size() const;   //获取堆栈的大小
    LinearStack<T>& Add(T array[],int addedSize);  //输入一个堆栈
    void print(); //输出堆栈中的数据

private:
    int top;  //栈顶
    int MaxTop; //栈的最大容量
    T *stack;
};

template <class T>
LinearStack<T>::LinearStack(int MaxLinearStackSize){
    MaxTop = MaxLinearStackSize - 1;
    top = -1;
    stack = new T[MaxLinearStackSize];
}

template<class T>
T LinearStack<T>::Top() const{
    if(isEmpty()) throw OutOfBounds();

    else return stack[top];
}

template<class T>
LinearStack<T>& LinearStack<T>::Add(const T& x){
    if(isFull()) throw OutOfBounds();

    top ++;
    stack[top] = x;

    return *this;
}

template<class T>
LinearStack<T>& LinearStack<T>::Delete(T& x){
    if(isEmpty()) throw OutOfBounds();

    x = stack[top--];

    return *this;
}

template<class T>
int LinearStack<T>::Size() const{

    int size = top+1;

    return size;
}

template<class T>
LinearStack<T>& LinearStack<T>::Add(T array[],int addedSize){
    int size = this->Size();

    int left = MaxTop + 1 - size;

    if(left < addedSize)
        throw OutOfBounds();

    for(int i = 0;i < addedSize;i++){
        this->Add(array[i]);
    }

    return *this;
}

template<class T>
void LinearStack<T>::print(){
    int size = this->Size();

    for(int i = size-1;i >= 0;i--){
        cout << stack[i] << " ";
    }

    cout << endl;
}

下面一个是使用链表实现的堆栈:

/* * LinkedStack.cpp * * Created on: 2015年5月7日 * Author: 洪波 */

#include "Exception.h"
#include <iostream>

using namespace std;

template<class T>
class LinkedStack;

template<class T>
class Node{
friend class LinkedStack<T>;

private:
    T data;
    Node<T> *link;
};

template<class T>
class LinkedStack{
public:
    LinkedStack(){top = 0;}
    ~LinkedStack();
    bool IsEmpty() const{return top == 0;}
    bool IsFull() const;
    T Top() const;
    LinkedStack<T>& Add(const T& x);
    LinkedStack<T>& Delete(T& x);
    void print();

private:
    Node<T> *top;  //指向栈顶节点
};

template<class T>
LinkedStack<T>::~LinkedStack(){
    Node<T> *next;
    while(top){
        next = top->link;
        delete top;

        top = next;
    }
}

template<class T>
bool LinkedStack<T>::IsFull() const{
    try{
        Node<T> *p = new Node<T>();
        delete p;
        return false;
    }catch(NoMem &nm){
        return true;
    }
}

template<class T>
T LinkedStack<T>::Top() const{

    return top->data;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Add(const T& x){

    Node<T> *node = new Node<T>();
    node->data = x;
    node->link = top;

    top = node;

    return *this;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Delete(T& x){
    if(IsEmpty()) throw OutOfBounds();

    Node<T> *p = top;
    x = top->data;
    top = top->link;

    delete p;

    return *this;
}

template<class T>
void LinkedStack<T>::print(){
    Node<T> *p = top;

    while(p){
        cout << p->data << " ";
        p = p->link;
    }

    cout << endl;
}

下面是我的测试类:

/* * Test.cpp * * Created on: 2015年5月7日 * Author: 洪波 */
#include "LinearStack.cpp"
#include "LinkedStack.cpp"

int main(){

    /********************************************** * 测试 LinearStack * **********************************************/
// LinearStack<int> ls(10);
//
// ls.Add(10);
// ls.Add(20);
//
//
// ls.print();
//
// int array[3] = {30,40,50};
//
// ls.Add(array,3);
//
// ls.print();

    /*====================================================*/

    /********************************************** * 测试 LinkedStack * **********************************************/

    LinkedStack<int> linkedS;
    linkedS.Add(10);
    linkedS.Add(20);

    linkedS.print();

    int n;
    linkedS.Delete(n);
    cout << n << endl;
    return 0;
}

其中,头文件”Exception.h”在我之前数据结构和算法的代码中有。堆栈在平常使用中用的还是挺多的。但相对来说其实现方式还是比较简单的,其插入和删除操作的时间复杂度都是O(1),即压栈和弹出的时间复杂度都是O(1)。效率还是蛮高的。

向程序运行过程中,函数的调用,在保存状态点的时候,都是保存到栈中的。其中比较典型的应用实例就是火车重排问题,离线等价类问题,汉诺塔问题,迷宫求解问题,括号匹配问题等。我会将在下面一章节中学习这些实例的实现。

本文转载自:http://blog.csdn.net/hongbochen1223/article/details/45569033

陈洪波
粉丝 2
博文 76
码字总数 1552
作品 0
济南
程序员
私信 提问
数据结构-堆栈和队列最简单的实现(Python实现)

OK,上篇博客我们介绍了双向链表以及代码实现,这篇文章我们来学习堆栈和队列。 队、栈和链表一样,在数据结构中非常基础一种数据结构,同样他们也有各种各样、五花八门的变形和实现方式。但...

浩然haoran
07/16
0
0
Java提高篇(三一)—–Stack

在Java中Stack类表示后进先出(LIFO)的对象堆栈。栈是一种非常常见的数据结构,它采用典型的先进后出的操作方式完成的。每一个栈都包含一个栈顶,每次出栈是将栈顶的数据取出,如下: Stac...

6pker
2016/10/24
58
0
【数据结构基础】栈简介(使用ES6)

数据结构这词大家都不陌生吧,这可是计算机专业人员的必修课专业之一,如果想成为专业的开发人员,必须深入理解这门课程,在这系列文章里,笔者将使用ES6,让大家熟悉数据结构这门专业课的内...

05/19
0
0
「译」如何以及为什么 React Fiber 使用链表遍历组件树

原文地址:The how and why on React’s usage of linked list in Fiber to walk the component’s tree 原文作者:Max Koretskyi 译文出自:阿里云翻译小组 译文链接:github.com/dawn-ple...

阿里云前端
01/06
0
0
每天理解一点Linux内核之进程的四个要素

1.程序 程序是静态的代码,而进程是运行的程序。程序好比是剧本,而进程就是戏,戏是按照剧本演的。 2.私有财产 每个进程都有自己专有的系统堆栈空间 3.户口 在内核中有一个task_struct数据结...

u010278923
2018/04/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 别问,问就是没空

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌,请使劲儿戳(这里) @wqp0010 :周...

小小编辑
今天
253
5
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
5
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
5
0
Spring Boot + Mybatis-Plus 集成与使用(二)

前言: 本章节介绍MyBatis-Puls的CRUD使用。在开始之前,先简单讲解下上章节关于Spring Boot是如何自动配置MyBatis-Plus。 一、自动配置 当Spring Boot应用从主方法main()启动后,首先加载S...

伴学编程
昨天
8
0
用最通俗的方法讲spring [一] ──── AOP

@[TOC](用最通俗的方法讲spring [一] ──── AOP) 写这个系列的目的(可以跳过不看) 自己写这个系列的目的,是因为自己是个比较笨的人,我曾一度怀疑自己的智商不适合干编程这个行业.因为在我...

小贼贼子
昨天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部