C++数据结构——栈 – Lickoo的小本本

1、栈(Stack)是一种线性存储结构，它具有如下特点：

（1）栈中的数据元素遵守“先进后出"(First In Last Out)的原则，简称FILO结构。（后进先出的叫法，也是可以的）

（2）限定只能在栈顶进行插入和删除操作。

#2、栈的相关概念：

（1）栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底。

（2）压栈：栈的插入操作，叫做进栈，也称压栈、入栈。

（3）弹栈：栈的删除操作，也叫做出栈。

#3、栈的常用操作为：

（1）弹栈，通常命名为pop

（2）压栈，通常命名为push

（3）求栈的大小

（4）判断栈是否为空

（5）获取栈顶元素的值

#4、栈的常见分类：

（1）基于数组的栈——以数组为底层数据结构时，通常以数组头为栈底，数组头到数组尾为栈顶的生长方向

（2）基于单链表的栈——以链表为底层的数据结构时，以链表头为栈顶，便于节点的插入与删除，压栈产生的新节点将一直出现在链表的头部

#5、实例分析

使用标准库的栈时, 应包含相关头文件，在栈中应包含头文件： #include< stack > 。定义：stack< int > s;

s.empty();         //如果栈为空则返回true, 否则返回false;
s.size();          //返回栈中元素的个数
s.top();           //返回栈顶元素, 但不删除该元素
s.pop();           //弹出栈顶元素, 但不返回其值
s.push();          //将元素压入栈顶

（1）基于数组的栈

#include <stack>
#include <iostream>
using namespace std;
 
int main()
{
	stack<int> mystack;
	int sum = 0;
	for (int i = 0; i <= 10; i++){
		mystack.push(i);
	}
	cout << "size is " << mystack.size() << endl;
	while (!mystack.empty()){
		cout << " " << mystack.top();
		mystack.pop();
	}
	cout << endl;
	system("pause");
	return 0;
}
//size is 11
// 10 9 8 7 6 5 4 3 2 1 0

（2）基于单链表的栈

#include <iostream>
using namespace std;
template<class T>class Stack
{
private:
	struct Node
	{
		T data;
		Node *next;
	};
	Node *head;
	Node *p;
	int length;
 
public:
	Stack()
	{
		head = NULL;
		length = 0;
	}
	void push(T n)//入栈
	{
		Node *q = new Node;
		q->data = n;
		if (head == NULL)
		{
			q->next = head;
			head = q;
			p = q;
		}
		else
		{
			q->next = p;
			p = q;
		}
		length++;
	}
 
	T pop()//出栈并且将出栈的元素返回
	{
		if (length <= 0)
		{
			abort();
		}
		Node *q;
		T data;
		q = p;
		data = p->data;
		p = p->next;
		delete(q);
		length--;
		return data;
	}
	int size()//返回元素个数
	{
		return length;
	}
	T top()//返回栈顶元素
	{
		return p->data;
	}
	bool isEmpty()//判断栈是不是空的
	{
		if (length == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	void clear()//清空栈中的所有元素
	{
		while (length > 0)
		{
			pop();
		}
	}
};
int main()
{
	Stack<char> s;
	s.push('a');
	s.push('b');
	s.push('c');
	while (!s.isEmpty())
	{
		cout << s.pop() << endl;
	}
	system("pause");
	return 0;
}