线性表——栈Stack的实现 C++_线性表实现栈

栈和队列是应用最多的数据结构之二，有数组实现和链表实现两种方式。当需要对容器做出限制，只允许一边插入和取出数据时，则需要用到栈。下面将总结数组实现的栈和阐述其原理。

一、线性表——栈Stack

1.1栈Stack定义

栈是一种特殊的线性表，其插入（也称为入栈或压栈）和删除（也称为弹出或出栈）操作都在表的同一端进行；该插入和删除的端口称为栈顶（top），另一端称为栈底（bottom）。

1.2栈的基本运算

1.2.1基本运算

(1) 初始化（构造一个空的栈）
(2) 计算栈长度（栈中节点个数）
(3) 插入节点（栈顶插入push）
(4) 删除节点（栈顶删除pop）
(5) 查找节点（栈顶查找top）
简单来说，就是实现栈的初始化、节点的增删查，没有改。

1.3线性表结构（链表）

图1 栈结构
由图1可知，栈是容纳一系列节点的容器，节点操作只能在一端进行插入和删除，节点对应代码里面的Element类对象。

1.4代码实现

common.h

#pragma once

typedef short int BYTE;
typedef unsigned int WORD32;
1
2
3
4

Element.h

#pragma once

#include "common.h"

class Element
{
public:
	Element();
	Element(BYTE key, WORD32 value);
	~Element();

	BYTE getKey() const;
	WORD32 getValue() const;
	void dump() const;

private:
	BYTE key;
	WORD32 value;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Stack.h

#pragma once
#include "Element.h"

class Stack
{
public:
	Stack(WORD32 capability);
	~Stack();
	const WORD32 getSize() const; // 返回实际元素个数
	const WORD32 getCapability() const; // 返回最大容量
	bool push(const Element& element); // 加入元素
	bool pop(); //删除元素
	Element* top() const; // 查找元素
	void showAllElements() const;

private:
	Element *element; // 指向元素数组指针
	WORD32 size; // 实际元素个数
	WORD32 capability; // 最大容量
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Element.cpp

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

Element::Element(BYTE key, WORD32 value)
	: key(key), value(value)
{
}

Element::Element() : key(0), value(0)
{
}

Element::~Element()
{
	static int count = 0;
//	std::cout << "Element::~Element() count:" << count++ << std::endl;
}

BYTE Element::getKey() const
{
	return key;
}

WORD32 Element::getValue() const
{
	return value;
}

void Element::dump() const
{
	std::cout << "key" << key << "  value" << value << std::endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

Stack.cpp

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

using namespace std;

Stack::Stack(WORD32 capability)
	: element(nullptr)
	, size(0)
	, capability(capability)
{
	if (capability == 0)
	{
		return;
	}
	element = new(std::nothrow) Element[capability];
	if (element == nullptr)
	{
		exit(0);
	}
}

Stack::~Stack()
{
	if (element != nullptr)
	{
		delete [] element;
	}
}
const WORD32 Stack::getSize() const
{
	return size;
}

const WORD32 Stack::getCapability() const
{
	return capability;
}

bool Stack::push(const Element& element)
{
	if (size >= capability)
	{
		cout << "capability is not enough!" << endl;
		return false;
	}
	this->element[size++] = element; // 深拷贝
	return true;
}

bool Stack::pop()
{
	if (size == 0)
	{
		cout << "size is zero, none node to be removed!" << endl;
		return false;
	}
	--size; // 不需要手动释放，析构的时候自动释放初始化分配的内存块。实际上增加节点只是修改已分配内存的数据而已
}

Element* Stack::top() const
{
	if (size == 0)
	{
		cout << "size is zero, none node to be removed!" << endl;
		return false;
	}
	if (size >= capability)
	{
		cout << "capability is not enough!" << endl;
		return nullptr;
	}
	return &element[size - 1];
}

void Stack::showAllElements() const
{
	for (auto i = 0; i < size; ++i)
	{
		cout << "key == " << element[i].getKey()
			<< "  value == " << element[i].getValue()
			<< "  size == " << size
			<< "  capability == " << capability << endl;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

main.cpp

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

using namespace std;

int main(int argc, char* argv[])
{
	cout << "\n-----------------创建栈-----------------------" << endl;
	Stack* stack = new(std::nothrow) Stack(64);
	if (stack == nullptr)
	{
		return false;
	}
	stack->showAllElements();
	
	cout << "\n-----------------增加三个元素-----------------------" << endl;
	stack->push(Element(1, 1));
	stack->push(Element(2, 2));
	stack->push(Element(99, 99));
	stack->showAllElements();
		
	cout << "\n-----------------查找一个元素-----------------------" << endl;
	auto element0 = stack->top();
	element0->dump();

	cout << "\n-----------------删除一个元素-----------------------" << endl;
	stack->pop();
	stack->showAllElements();

	delete stack;
	stack = nullptr;

	getchar();
	return 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

1.5输出结果

图2 栈输出结果图

1.6总结

由图二结果可知，栈结构比较简单，主要功能是增删查功能，没有修改，对元素的操作都限制在栈顶这一端，特点是后进先出。

参考内容

C++实现栈
哔哩哔哩 P3 3.栈结构

《数据结构、算法与应用 C++语言描述》 [美] 萨特吉-萨尼（Sartaj Sahni）著. 王立柱 刘志红译 page:175-180