C++实现栈与分析栈的知识点
目录
- 一、栈的概念
- 二、栈的基本组成和操作
- 三、栈元素的存储方式
- 四、C++实现静态栈
- （1）栈类的设计
- （1）isEmpty()判断是否为空
- （2）isFull()判断是否已满
- （3）push()压栈
- （4）pop()出栈
- （5）getTop()获取栈顶元素
- （6）clear()清空栈
一、栈的概念
栈的英文为stack，译为一叠或者一摞。栈是一种采用先进后出FILO（first in last out）或称为后进先出LIFO（last in first out）策略进行元素访问的数据结构。栈经常被比作是一摞碟子，最上面的碟子是最后放上去的，却是最先被拿走的。
二、栈的基本组成和操作
如果要正确的使用栈，则必须保证其含有栈顶指针和栈元素。此外，栈的基本操作含有：
- 初始化；
- 入栈；
- 出栈；
- 清空栈；
- 访问栈顶元素；
- 检测栈的状态；
其中，栈包含三种状态：栈空、一般状态、栈满。检测栈满是非常重要的步骤，防止在栈容量不能扩充时出现溢出现象，此时称为上溢。如果在栈空时进行出栈操作，此时会出现下溢。所以在入栈和出栈时，必须对栈的状态进行检查。
三、栈元素的存储方式
常用的实现方式分为两种;
- 第一种策略是使用静态数组实现，此时栈的容量是有限的；
- 第二种策略是使用动态数组或者链表，此时栈的容量可以动态扩充。
四、C++实现静态栈
使用静态数组实现栈结构时，栈底固定不变，栈顶随着压栈和出栈操作进行自加和自减。一般采用整型变量来表示栈顶，压栈时栈顶变量加一，出栈时栈顶变量减一。
（1）栈类的设计
根据前面对栈基本功能和组成的描述，栈类应该包含下述的公有函数成员和私有数据成员。其中currentSize为栈顶指针，用于压栈、入栈、判空、判满等操作；T表示模板参数类型，栈元素为T类型数组，可以在隐式或显式实例化时指定；SIZE表示栈的容量，一旦确定就不能更改。
代码如下：
template <typename T, int SIZE=10>
class Stack {
public:
bool isEmpty();
bool isFull();
void push(const T &data);
T pop();
void clear();
T getTop();
private:
// 栈顶指针
int currentSize=-1;
T array[SIZE];
};
（1）isEmpty()判断是否为空
如果栈顶指针值为0，则表示为栈为空，代码如下：
template<typename T, int SIZE>
bool Stack<T, SIZE>::isEmpty() {
if (currentSize == 0) {return true;}
else {return false;}
}
（2）isFull()判断是否已满
如果栈顶指针值等于栈的存储容量SIZE时，栈满：
template<typename T, int SIZE>
bool Stack<T, SIZE>::isFull() {
if (currentSize == SIZE) {return true;}
else { return false; }
}
（3）push()压栈
将数据压栈时，栈顶指针同步加一；
template<typename T, int SIZE>
void Stack<T, SIZE>::push(const T &data) {
// 栈顶压入
currentSize++;
array[currentSize] = data;
}
（4）pop()出栈
将数据弹出后，栈顶指针需要减一：
template<typename T, int SIZE>
T Stack<T, SIZE>::pop() {
if(currentSize>=1){return array[currentSize--];}
}
（5）getTop()获取栈顶元素
获取栈顶数据并不需要对栈顶指针进行移动：
template<typename T, int SIZE>
T Stack<T, SIZE>::getTop() {
return array[currentSize];
}
（6）clear()清空栈
由于采用的是静态数组，所以清空栈时无需进行内存释放，将栈顶指针归零即可：
template<typename T, int SIZE>
void Stack<T, SIZE>::clear() {
currentSize = -1;
}
到此这篇关于C++实现栈与分析栈的知识点的文章就介绍到这了,更多相关C++栈内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！
相关推荐
-
C++解决大数组栈内存不够问题的方法分析
本文实例讲述了C++解决大数组栈内存不够问题的方法.分享给大家供大家参考,具体如下: 在c++中,我们可以直接通过下面的方式创建一个数组: const int N = 6; const int Nx = 100; const int Ny = 100; double phi[N][Nx][Ny]; double phi_b[N][Nx][Ny]; 但是,如果上述的Nx和Ny比较小还好说,一旦Nx和Ny很大时,就会报错,导致编译失败. 为解决这一问题,我们可以采用下面的几种方法来解决此问题: 1.
-
C++Stack栈类模版实例详解
目录 1.栈的介绍 2.栈实现 3.代码测试 总结 1.栈的介绍 栈的实现方式分为3种 基于静态数组实现,内部预设一个很大的数组对象, 实现简单,缺点是空间受限. 基于动态数组实现,内部预设一个容量值,然后分配一段内存空间数组,如果入栈大于默认容量值时,则再次扩大分配新的内存数组,并将旧数组拷贝至新数组及释放旧数组. 基于双向循环链表实现 栈的函数需要实现如下所示: T pop() : 出栈并返回栈顶元素 void push(const T &t) : 入栈 const T & top(
-
c++显式栈实现递归介绍
目录 前言 1. 递归 2. 显式栈实现的思路 3. 代码解析 前言 在大学的课上老师有教过,也就是用循环来实现递归,现在自己回顾一下并且做一下记录. 1. 递归 假设有函数A, 和函数B, 函数B是一个递归函数, 函数A调用函数B.这个递归的过程分为: 函数A调用函数B,函数A将数据传给函数B.此时进入到函数B内部,函数B通过传参拿到函数A传过来的数据.执行本次调用的操作将新的数据作为参数传入函数B(递归过程, 内部再次执行2~3步骤,以此类推).退出递归结束. 2. 显式栈实现的思路 由上面
-
C++基于栈的深搜算法实现马踏棋盘
马踏棋盘(基于栈的深搜算法实现) 简单来说,从任意指定方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的一条路径,这就是马踏棋盘的简单描述. 话不多说,代码如下,要是有什么不懂的地方,欢迎讨论~ #include <stdio.h> #include <stdlib.h> #define M 8 //行 #define N 8 //列 typedef struct snode //坐标 { int flag; int x; int y; }sta
-
关于C++使用指针 堆和栈的区别分析
数据在内存的存放有以下几种形式 1.栈区--由编译器自动分配并且释放,该区域一般存放函数的参数值,局部变量的值等, 2.堆区--一般由程序员分配释放,如果程序员不释放,程序结束的时候才会被操作系统回收,3.寄存器区--用来保存栈顶指针和指令指针4.全局去--也是静态区,全局变量和静态变量都是存储在一起的,初始化的全局变量和静态变量都存储在一块,为初始化的全局变量和静态变量在相邻的另一个区域,程序结束后由系统释放.5.文字常量区--常量字符串就是放在这里的,程序结束后由系统释放,6.程序代码区--
-
详解C++内存的代码区,全局区,栈区和堆区
目录 代码区: 全局区: 栈区 堆区 总结 今天无意中刷到了一篇关于c++内存的帖子,我发现那个人好像写的不太对,然后同时我自己也发现我对一块还不够了解,所以我干脆就自己去了解整理了一下:首先我们要大概知道四个区都是干什么的 代码区: 顾名思义,就是存放我们写的代码的地方,不过要注意的是存放的是二进制代码. 注意:我们写的所有的写的代码(包括注释.变量.语句等)都会放到代码区中. 全局区: 存放全局,静态变量以及常量. 注意: 1.全局区里有一个部分叫常量区,储存的是常量,如const修饰的全局
-
C++实现栈与分析栈的知识点
目录 一.栈的概念 二.栈的基本组成和操作 三.栈元素的存储方式 四.C++实现静态栈 (1)栈类的设计 (1)isEmpty()判断是否为空 (2)isFull()判断是否已满 (3)push()压栈 (4)pop()出栈 (5)getTop()获取栈顶元素 (6)clear()清空栈 一.栈的概念 栈的英文为stack,译为一叠或者一摞.栈是一种采用先进后出FILO(first in last out)或称为后进先出LIFO(last in first out)策略进行元素访问的数据结构.栈
-
php线性表的入栈与出栈实例分析
本文实例讲述了php线性表的入栈与出栈用法.分享给大家供大家参考.具体如下: <?php $stack = array("Simon", "Elaine"); //定义数组 array_push($stack, "Helen", "Peter"); //入栈 print_r($stack); ?> <?php $stack = array("Simon", "Elaine&quo
-
Java内存模型中的虚拟机栈原理分析
Java虚拟机在执行Java程序的过程中会把它所管理的内存划分为若干个不同的数据区域,这些区域都会有各自的用途,以及创建和销毁的时间,有的区域会随着虚拟机进程的启动而存在,有些区域则依赖用户线程的启动和结束而建立和销毁.Java虚拟机所管理的内存将会包括以下几个运行时数据区域.如下图所示(图片来自<深入理解Java虚拟机>一书). 在内存中,栈分为两部分,一部分是本地方法栈,为虚拟机使用到的Native方法服务,具体的虚拟机可以自由实现,另一部分就是虚拟机栈,主要是为虚拟机执行Java方法服务
-
PHP实现的栈数据结构示例【入栈、出栈、遍历栈】
本文实例讲述了PHP实现的栈数据结构.分享给大家供大家参考,具体如下: 利用php面向对象思想,栈的属性有top.最大存储数.和存储容器(这里利用了php数组). 代码如下:实现了入栈.出栈.遍历栈的几个方法: <?php class Stack{ const MAXSIZE = 4;// 栈最大容量 private $top = -1; private $stack = array();// 利用数组存储数据 public function __construct(){ $this->sta
-
java使用链表来模拟栈的入栈出栈操作实例代码
栈:后进先出:最后一个放入堆栈中的物体总是被最先拿出来. 使用链表来模拟栈的入栈出栈操作. 1.节点类代码 public class Entry<T> { private T value; private Entry<T> next; public Entry() { this(null); } public Entry(T value) { this.value=value; this.next=null; } public void setValue(T value) { th
-
C#实现顺序栈和链栈的代码实例
自己定义的栈的接口,完全是按照栈的常用方法以及命名方式实现: 注意以下类,接口都是在一个命名空间下 栈的接口:包括了常用的方法 namespace 栈 { interface IStackDS<T> { int Count { get; } int GetLength(); bool IsEmpty(); void Clear(); void Push(T item); T Pop(); T Peek(); } } 顺序栈的实现,参照顺序表实现 namespace 栈 { class SeqS
-
Java定义栈结构，并实现入栈、出栈操作完整示例
本文实例讲述了Java定义栈结构,并实现入栈.出栈操作.分享给大家供大家参考,具体如下: package com.example.demo; import java.util.ArrayList; public class Stack { ArrayList<Object> list = new ArrayList<>(); //入栈 public void push(Object o){ list.add(o); } //出栈 public Object pop(){ Objec
-
C语言栈之顺序栈
目录 定义 1.建立空栈 2.进栈 3.出栈 4.读栈顶元素 5.遍历栈 总结 定义 用顺序存储方式实现的栈称为顺序栈,顺序栈对应于顺序表. 设栈中的数据元素的类型是整型,用一个足够长的一维数组s来存放元素,数组的最大容量为STACK_INTSIZE.同时假设栈顶指针top.(在以下的程序中,top不是指向当前的栈顶元素,而是指向下一次将要进栈的元素的存储位置) 顺序栈可以描述如下: #define STACK_INTSIZE 50 /*分配栈的最大存储空间*/ #define DataType
-
C语言深入刨析数据结构之栈与链栈的设计与应用
目录 一.栈的定义 二.栈的特点 三.栈的理解 四.链栈引入 五.链栈定义 六.链栈的结构体设计 七.链栈的基本操作 7.1链栈的初始化 7.2链栈判空 7.3链栈入栈 7.4链栈出栈 7.5取栈顶元素 八.总结 一.栈的定义 栈是限定仅在表尾进行插入和删除操作的数据结构(受到限制的线性表). 我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何元素为空栈. 二.栈的特点 后进先出 比如word,浏览器网页等一系列软件中,都有撤销的操作,就是利用栈的这种方式来实现的,可能不同软件的代码不
-
python栈的基本定义与使用方法示例【初始化、赋值、入栈、出栈等】
本文实例讲述了python栈的基本定义与使用方法.分享给大家供大家参考,具体如下: # -*- coding:utf-8 -*- #! python3 #在桟的设计中,我们需要定义一个实例属性top.三个实例方法:获取栈顶元素peek():出桟pop():入栈push() #栈的效果:先进后出 class Node(object): ##节点,包括两个属性,一个是节点的值,一个是节点的下一个指向 def __init__(self,value): self.value = value #赋值给节