文档章节

如何用C++实现栈

BWH_Steven
 BWH_Steven
发布于 10/22 21:53
字数 1986
阅读 9
收藏 0

栈的定义

栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。 ——百度百科

简单定义:栈就是一种只允许在表尾进行插入和删除操作的线性表

如何理解栈的概念

举一个生活中的例子:我在一个储物箱中,堆了一堆衣服,我的一件球衣在最下面,而我要拿这件衣服,就意味着我必须将上面的衣服全部拿出来才可以,但是由于箱子只有一个口,我也只能从上面拿东西,心里还默默想着,当初就不该将球衣早早的放进去,导致结果就是先进后出!

你就不能举个计算机中的例子?这就安排!

计算机中很多操作都是使用栈的原理来实现的,我们就比如常见的浏览器中的 “前进键” “后退键” 就可以利用栈的原理来实现,我们来用图说明一下

我们想要实现前进后退,可以使用两个栈(暂时称作 M、N)来实现

  • 我们分别浏览了页面A、页面B、页面C,所以我们将这些页面依次压入栈,即图中打开页面部分

  • 当用户点击后退时,我们需要退回到页面B中去,但是由于页面C在B上方,我们就必须将页面C从栈M中先弹出,放到栈N中,即图中后退部分

  • 但是如果用户突然又想回到页面C去,原理相似的,只需要把栈N中的页面C弹出,重新压入栈M即可

  • 而如果用户在浏览B界面的时候,打开了新的界面D,那么C就无法通过前进后退访问了,所以栈M中压入页面D的同时还需要清空栈N

栈的术语说明

栈顶:允许进行插入和进行删除操作的一段成为栈顶

栈底:表的另一端称为栈底 (第一个元素进入的位置)

压栈:在栈顶位置插入元素的操作叫做压栈,或入栈、进栈

出栈:删除栈顶元素的操作叫做出栈,也叫作弹栈,或者退栈

空栈:不含元素的空表

栈溢出:当栈满的时候,如果再有元素压栈,则发生上溢,当栈空的时候,再出栈则发生下溢

栈的抽象数据类型

#ifndef _STACK_H_
#define _STACK_H_
#include <exception>
using namespace std;


template <class T>
class Stack { 
public: 
	virtual bool empty() const = 0; 
	virtual int size() const = 0; 
	virtual void push(const T &x) = 0; 
	virtual T  pop() = 0;              
	virtual T getTop() const = 0;  
	virtual void clear() =0;
	virtual ~Stack() {}
};

/*
	自定义异常类
*/

// 用于检查范围的有效性
class outOfRange:public exception {
public:    
   const char* what()const throw()    
   {    return "ERROR! OUT OF RANGE.\n";    } 
};  

// 用于检查长度的有效性
class badSize:public exception {
public:    
   const char* what()const throw()    
   {    return "ERROR! BAD SIZE.\n";    }  
};

#endif

顺序栈——栈的顺序存储结构

开头我们就已经提过了,栈实际上就是一种线性表的特例,所以栈的实现和线性表一样,均使用数组实现,我们使用一个一维数组来存储元素,那么总得有个头阿,我们就需要确定栈底的位置,通常我们选择 0 的一端作为栈底,这样更加方便理解与操作,特别的是,我们设置了一个整型变量top 用来存放栈顶元素的位置(下标),也称作栈顶指针

(一) 顺序栈的类型描述

初始的时候,给top赋值-1,表示栈为空,元素进栈以后,top + 1,元素出栈后,top - 1

//  array-based stack: definition and implementation for some methods 
 
#ifndef _SEQSTACK_H_
#define _SEQSTACK_H_

#include "Stack.h" 
 
template <class T> 	 
class seqStack : public Stack<T> {       
private:
	T * data;
	int top;
	int maxSize;
	void resize();
public:
	seqStack(int initSize = 100) {
		if(initSize<=0) throw badSize();
		data = new T[initSize];
		maxSize = initSize ;    
		top = -1;  
	}	   
	~seqStack(){ delete [] data;}
	bool empty() const{ return top == -1;}      
	int size() const{ return top + 1; } 
	void clear() { top = -1; } 				// 清空栈内容 
	void push(const T &value);   
	T  pop();   
	T  getTop() const;	  	  
}; 

#endif

(二) 进栈

template <class T>
void seqStack<T>::push(const T &value) {	
	if (top == maxSize - 1) resize();
	data[++top] = value;
}   

(三) 出栈

template <class T>
T seqStack<T>::pop() { 	
	if(empty())throw outOfRange();
	return data[top--];	
}   

(四) 取栈顶元素

template <class T>
T seqStack<T>::getTop() const{
	if(empty())throw outOfRange();
	return data[top];
}

(五) 扩容

template <class T>
void seqStack<T>::resize(){
	T * tmp = data;
	data = new T[2 * maxSize];
	for (int i = 0; i < maxSize; ++i)
		data[i] = tmp[i];
	maxSize *= 2;
	delete[] tmp;
} 

(六) 两栈共享空间

栈这种数据结构相比较于线性表,没了有插入和删除的时候需要移动元素的情况,但是仍然有一个比较大的不足,那就是我们必须事先分配空间大小,如果一旦空间满了,再有元素近栈就必须使用编程手段对数组进行扩容,还是比较麻烦的

而有时候我们往往需要多个栈,我们之前的处理手段就是尽量的根据实际问题设计大小合适的数组,但是这显然是有一定难度的,而且常常是这样的,一个栈已经满了,而另一个栈可能还空着很多空间,如果能将那些空闲的位置利用起来就好了,而我们下面就要来提到一个这样的技巧的思路

我们其实就是将两个栈的栈底全部放到了,数组的两端,然后两个栈处于相向位置,逐渐向中间靠拢,只要两个top指针不相遇,两个栈就可以一直用

链栈——栈的链式存储结构

链栈就是使用链式存储结构的栈,和我们在单链表中的链式存储的感觉相似,我们会设置一个指向栈顶的指针top,同时当top == NULL时为空栈

(一) 链栈的类型定义

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_
#include <iostream> 

#include "Stack.h" 

template <class T>
class linkStack : public Stack<T> 
{
private:
	struct Node {
		T data;
		Node* next;
		Node(){ next = NULL; }
		Node(const T &value, Node *p = NULL){ data = value; next = p;}
	};
	Node* top;
public:
	linkStack(){ top = NULL; }
	~linkStack(){ clear(); }
	void clear();
	bool empty()const{ return top == NULL; }
	int size()const;
	void push(const T &value);
	T  pop();
	T getTop()const;
};
#endif

(二) 清空栈

template <class T>
void linkStack<T>::clear() {
	Node *p;
	while (top != NULL) {
		p = top;
		top = top->next;
		delete p;
	}
}

(三) 求栈中元素个数

template <class T>
int linkStack<T>::size()const {
	Node *p = top;
	int count = 0;
	while (p){
		count++;
		p = p->next;
	}
	return count;
}

(四) 进栈

template <class T>
void linkStack<T>::push(const T &value) {
	Node *p = new Node(value, top);
	top = p; 
}

(五) 出栈

template <class T>
T linkStack<T>::pop() {
	if (empty())throw outOfRange();
	Node *p = top;
	T value = p->data;
	top = top->next;
	delete p;
	return value;
}

(六) 获取栈顶元素

template <class T>
	T linkStack<T>::getTop() const { 
	if(empty())throw outOfRange();
	return top->data;
}

结尾:

如果文章中有什么不足,或者错误的地方,欢迎大家留言分享想法,感谢朋友们的支持!

如果能帮到你的话,那就来关注我吧!如果您更喜欢微信文章的阅读方式,可以关注我的公众号

在这里的我们素不相识,却都在为了自己的梦而努力 ❤

一个坚持推送原创开发技术文章的公众号:理想二旬不止

© 著作权归作者所有

BWH_Steven
粉丝 1
博文 45
码字总数 132917
作品 0
珠海
私信 提问
C语言/C++编程学习:栈的代码实现之数组方案

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你学知识
2018/06/14
19
0
C++ STL学习——stack

栈是最为常用的数据结构了,很多算法都是依靠栈来实现的,比如递归。我们要手动来实现栈,显得十分繁琐和麻烦,而且复用性不好。C++ 的STL中已经帮我们封装好了栈,我们只要方便的进行调用即...

chenyufeng1991
2016/08/22
0
0
【转载】数据结构利器之私房STL

数据结构利器之私房STL 此系列的文章适合初学有意剖析STL和欲复习STL的同学们。 学过c++的同学相信都有或多或少接触过STL。STL不仅仅是c++中很好的编程工具(这个词可能有点歧义,用类库更恰...

悠米海
2012/12/02
208
0
10个Objective-C基础面试题,iOS面试必备

苹果的iOS系统越来越火了,苹果这个金矿平台也吸引了大量的iOS开发者参与其中,这也促使越来越多的公司向iOS应用开发方向靠拢,因此市场上 对iOS开发的人才需求自然也非常巨大。如果你准备去...

ruby_chen
2013/07/15
56.4K
18
C# vs C++之二:GC vs RAII

C# vs C++之二:GC vs RAII 资源管理 C中资源管理极为繁琐易错,大多复杂C系统都面临内存泄露、悬挂指针等问题 一方面由底层语言特点决定;另一方面也由于C语言特性相对较少,严重依赖程序员...

ddatsh
2011/06/28
1K
6

没有更多内容

加载失败,请刷新页面

加载更多

IT兄弟连 HTML5教程 CSS3属性特效 边框

通过CSS3,我们能够创建圆角边框,向矩形添加阴影,使用图片来绘制边框。并且不需使用设计软件,比如photoshop。 1 边框图片border-image border-image为边框应用图片,顾名思义就是为图片应...

老码农的一亩三分地
22分钟前
4
0
3个例子详解C++ 11 中push_back 和 emplace_back差异

本文首发于个人博客https://kezunlin.me/post/b83bc460/,欢迎阅读最新内容! cpp11 push_back and emplace_back Guide case1 #include <iostream>#include <vector>class A{public: A......

kezunlin
23分钟前
5
0
OSChina 周五乱弹 —— 你已经是个成熟的熊猫了

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @Sharon啊 :#今日歌曲推荐# 分享黑鸭子的单曲《羞答答的玫瑰静悄悄的开》 《羞答答的玫瑰静悄悄的开》- 黑鸭子 手机党少年们想听歌,请使劲儿...

小小编辑
今天
488
9
结合Spring Security进行web应用会话安全管理

在本文中,将为大家说明如何结合Spring Security 和Spring Session管理web应用的会话。 一、Spring Security创建使用session的方法 Spring Security提供4种方式精确的控制会话的创建: alwa...

fightinging
今天
6
0
83、Mybatis和Hibernate重要区别

Mybatis;入门简单,程序容易上手开发,节省开发成本。Mybatis需要程序猿自己编写sql语句,是一个不完全的ORM框架,对sql修改和优化非常容易实现。 Mybatis适合开发需求变更频繁的系统,比如...

lianbang_W
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部