34.数据结构-栈的概念与实现（上）

2024-01-21 21:33:10

文章目录

一.栈的定义与特性

1.栈的定义

栈是一种特殊的线性表，只可以在线性表是一端进行操作，其中栈顶（Top）是允许操作的一端，栈底（bottom）是不允许操作的一端

2.栈的特性

后进先出，（Last In First Out）,最后放进去的结点先出来

二.栈的实现

2.1 栈的继承

栈分为顺序栈和链式栈，可以将栈作为顶层抽象父类，顺序栈和链式栈作为子类继承，继承结构为

2.2 顶层父类栈需要实现的函数

push ():入栈
pop () :出栈
top () : 返回栈顶元素
clear() :清空栈
size() :返回栈的大小

2.3 顶层抽象父类的实现

stack.h

#ifndef STACK_H
#define STACK_H


template<class T>
class Stack
{
public:
	virtual void push(const T& e) = 0;//入栈
	virtual void pop()			  = 0;//出栈
	virtual T    top() const	  = 0;//返回栈顶元素
	virtual void clear()		  = 0;//清空栈
	virtual int  size()			  = 0;//返回栈的大小
};

#endif

三.栈的顺序实现

用一片连续的内存空间来容纳栈中的元素，设置一个标志变量表示栈顶(top)，当栈为空时，top指向的位置下标为-1，当栈满时则指向栈的大小-1的地方

3.1 顺序栈的类定义

使用原生数组作为栈的存储空间，通过原生数组存储栈的数据
使用模板参数决定栈的最大容量
top元素作为栈顶标识

3.2 栈的初始化

在构造函数里面使top的标识符指向-1，并且当前数据长度为

	StaicStack()
	{
		m_top	= -1;//栈空
		m_size  = 0; //当前数据长度为0
	}

3.3 栈的压栈

先判断当前栈长度是否小于栈容量

void push(const T& e)
	{
		if (m_size < N)
		{
			m_space[m_top + 1] = e;
			m_size++;
			m_top++;
		}
		else
		{
			cout << "there are not space to insert" << endl;
		}
	}

3.4 出栈

先判断栈中有无元素，有的话将top标识符减一，并且将栈的数据长度减一

void pop()
	{
		//判断当前栈是否有数据元素
		if (m_size > 0)
		{
			m_top--;
			m_size--;//当前栈中元素少了一个
		}
		else
		{
			cout << "stack is empty" << endl;
		}
	}

3.5 获取栈顶元素

先判断栈中有无元素,有的话将栈顶标识符作为下标，并返回数组值


	T top()const
	{
		if (m_size > 0)
		{
			return m_space[m_top];
		}
		else
		{
			cout << "stack is empty" << endl;
		}
	}

3.6 清空栈

void clear()
	{
		m_size = 0;
		m_top = -1;
	}

3.7 完整代码

Stack.h:抽象父类

#ifndef STACK_H
#define STACK_H


template<class T>
class Stack
{
public:
	virtual void push(const T& e) = 0;//入栈
	virtual void pop()			  = 0;//出栈
	virtual T    top() const	  = 0;//返回栈顶元素
	virtual void clear()		  = 0;//清空栈
	virtual int  size()			  = 0;//返回栈的大小
};

#endif

staticStack:静态栈

#ifndef STATICSTACK_H
#define STATICSTACK_H

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

using namespace std;

template<class T,int N>
class staicStack :public Stack<T>
{
protected:
	T m_space[N];
	int m_top;
	int m_size;
public:
	staicStack()
	{
		m_top	= -1;//栈空
		m_size  = 0; //当前数据长度为0
	}

	//返回栈的最大存储容量
	int capacity()
	{
		return N;
	}

	//实现压栈操作
	void push(const T& e)
	{
		if (m_size < N)
		{
			m_space[m_top + 1] = e;
			m_size++;
			m_top++;
		}
		else
		{
			cout << "there are not space to insert" << endl;
		}
	}

	void pop()
	{
		//判断当前栈是否有数据元素
		if (m_size > 0)
		{
			m_top--;
			m_size--;//当前栈中元素少了一个
		}
		else
		{
			cout << "stack is empty" << endl;
		}
	}

	T top()const
	{
		if (m_size > 0)
		{
			return m_space[m_top];
		}
		else
		{
			cout << "stack is empty" << endl;
		}
	}

	void clear()
	{
		m_size = 0;
		m_top = -1;
	}

	int size()
	{
		return m_size;
	}
};

#endif // !STATICSTACK_h

3.8 测试代码

#include <iostream>

#include "staticStack.h"

using namespace std;


int main()
{
	staicStack<int, 5> stack;

	for (int i = 0; i < 5; i++)
	{
		stack.push(i);
	}

	while (stack.size() > 0)
	{
		cout << stack.top() << endl;
		stack.pop();
	}
}

结果：

四.小结

栈只允许在线性表的一端进行操作
静态栈使用原生数组作为内部存储空间
静态栈最大容量由模板参数决定

码农公寓