栈和队列（c++）

栈

概念（八股文）：

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

1. 栈中的数据元素遵守“先进后出"的原则。
2. 限定只能在栈顶进行插入和删除操作。

• 栈的相关概念：

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

• 栈的常用操作为：

  #include
  stack<int> s;
  s.pop();           //1. 弹栈，通常命名为pop，弹出栈顶元素, 但不返回其值
  s.push();          //2. 压栈，通常命名为push
  s.size();   	   //3. 求栈的大小 
  s.empty();         //4. 判断栈是否为空如果栈为空则返回true, 否则返回false;
  s.top();           //5. 获取栈顶元素的值
  1
  2
  3
  4
  5
  6
  7

• 栈的常见分类：

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

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

使用：

在使用方面我们在使用时要包含头文件#include 声明为stack s

操作

• 基于数组的操作：

#include 
#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 基于链表的操作：

#include 
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;
}
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
85
86
87
88
89
90
91
92
93

---

队列

一、queue初始化

queue (<数据类型，容器类型>）
初始化时必须要有数据类型，容器可省略，省略时则默认为deque 类型

初始化示例:

queue<int>q1;
queue<double>q2;  
queue<char>q3；
1
2
3

队列中的数据元素遵循“先进先出”（First In First Out）的原则，简称FIFO结构；

在队尾添加元素，在队头删除元素。

注意：不能用vector容器初始化queue

因为queue转换器要求容器支持front（）、back（）、push_back（）及 pop_front（），说明queue的数据从容器后端入栈而从前端出栈。所以可以使用deque和list对queue初始化，而vector因其缺少pop_front（），不能用于queue。

二、queue常用函数

常用函数:

push() 在队尾插入一个元素
pop() 删除队列第一个元素
size() 返回队列中元素个数
empty() 如果队列空则返回true
front() 返回队列中的第一个元素
back() 返回队列中最后一个元素
1
2
3
4
5
6

---