数据结构-栈(stack)

简介

1. 栈是一种线性数据结构
2. 栈的特征是数据的插入和删除只能通过一端来实现，这一端称为“栈顶”，相应的另一端称为“栈底”

特点

1. 栈中的数据元素遵守”先进后出“(First In Last Out)的原则，简称FILO结构
2. 限定只能在栈顶进行插入和删除操作

队列的相关概念

1. 栈顶与栈底：允许元素插入与删除的一端称为栈顶，另一端称为栈底
2. 压栈：栈的插入操作，叫做进栈，也称压栈、入栈
3. 弹栈：栈的删除操作，也叫做出栈

队列的操作(stl中<stack>库)

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

队列的实现

基于数组的栈

#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;
	return 0;
}

输出为

size is 11
10 9 8 7 6 5 4 3 2 1 0

基于单链表的栈

#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;
	}
	return 0;
}

输出为

c
b
a

例题

用两个栈实现队列

栈的压入弹出序列

包含min函数的栈