Datastructures-栈

后进先出的数据结构，很常用

STL中的stack

C++的STL提供了stack，将写好的各种功能封装，通过stack容器，可以很方便地使用栈。

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
#include<iostream>
#include<stack>
using namespace std;
void print(stack<int> k)
{
	stack<int>kk = k; //复制一份出来用于遍历。
	printf("栈中元素有：");
	for(int i = 0;i <= kk.size();++ i)
	{
		printf("%d ",kk.top());
		kk.pop();
	}
	printf("\n");
	printf("\n");
}
int main()
{
	stack<int> k;
	printf("5入栈\n");
	k.push(5);
	print(k);
	
	printf("7入栈\n");
	k.push(7);
	print(k);
	
	printf("66入栈\n");
	k.push(66);
	print(k);
	
	printf("%d出栈\n",k.top());
	k.pop();
	print(k);
	
	printf("%d出栈\n",k.top());
	k.pop();
	print(k);
	
	
	return 0;
}
//思考一下，为什么想要遍历还要复制一份出来。

这种用法在工程中常见。因为STL写好的栈，作为C++的重要工具，经过了高度优化，综合考虑了易用性、性能、安全性、扩展性、还能够自动管理内存，是比较成熟的技术。”因此，在可能的情况下，建议使用STL std::stack。“

数组模拟的stack

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
#include<bits/stdc++.h>
using namespace std;
int k[10];
int pointer = -1;
void print()
{
	printf("栈中元素有：");
	for(int i = 0;i <= pointer;++ i)
	{
		printf("%d ",k[i]);
	}
	printf("\n");
	printf("\n");
}
int main()
{
	
	printf("5入栈\n");
	k[++pointer] = 5;
	print();
	
	printf("7入栈\n");
	k[++pointer] = 7;
	print();
	
	printf("66入栈\n");
	k[++pointer] = 66;
	print();
	
	printf("%d出栈\n",k[pointer]);
	pointer--;
	print();
	
	printf("%d出栈\n",k[pointer]);
	pointer--;
	print();
	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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<stdio.h>
#include<stdlib.h>
#define MAXN 1000
#define maxsize 5
typedef int Elementtype;
typedef struct LNode *Stack;
struct LNode{
	Elementtype Data[MAXN];
	int Top;
};

Stack CreateStack();
int Isempty(Stack S);
int IsFull(Stack S);
void Push(Stack S,Elementtype item);
Elementtype Pop(Stack S);
void Print(Stack S);

Stack CreateStack()
{
	Stack S;
	S = (Stack)malloc(sizeof(struct LNode));
	S->Top = -1;
	return S;
}
void Push(Stack S,Elementtype item)
{
	if(IsFull(S)){
		printf("栈满\n");
		return ;
	}
	S->Top ++ ;
	S->Data[S->Top] = item;
}
int IsFull(Stack S)
{
	return (S->Top == maxsize-1);
}
int Isempty(Stack S)
{
	return (S->Top == -1);
}
Elementtype Pop(Stack S)
{
	if(Isempty(S))
	{
		printf("栈空\n");
		return -1;
	}else{
		Elementtype val = S->Data[S->Top];
		S->Top--;
		return val;
	}
}
void Print(Stack S)
{
	int i;  
	printf("栈内元素有: ");
	for (i = S->Top; i >= 0; i--) {  
		printf("%d ", S->Data[i]);  
	}  
	printf("\n");  
}
/*
  void Print(Stack S) {  
	  Stack copy = CopyStack(S);  
	  if (!copy) {  
		  printf("内存分配失败\n");  
		  return;  
	  }  
	  for (int i = copy->Top; i >= 0; i--) {  
		  printf("%d ", copy->Data[i]);  
	  }  
	  printf("\n");  
	  free(copy); // 释放复制栈的内存  
  }  
 */
int main()
{
	Stack S;
	S = CreateStack();
	printf("5入栈\n");
	Push(S,5);
	printf("\n");
	
	Print(S);
	printf("7入栈\n");
	Push(S,7);
	printf("\n");
	
	Print(S);
	printf("66入栈\n");
	Push(S,66);
	printf("\n");
	
	Print(S);
	printf("99入栈\n");
	Push(S,99);
	Print(S);
	printf("\n");
	
	printf("100入栈\n");
	Push(S,100);
	Print(S);
	printf("\n");
	
	printf("110入栈\n");
	Push(S,110);
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	
	printf("%d出栈\n",Pop(S));
	Print(S);
	printf("\n");
	return 0;
}

思考：先入后出怎么被实现的？
思考：被注释掉的那个Print()能起到同样的作用吗，哪个更好？

链表实现

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
#include<stdio.h>
#include<malloc.h>
typedef int ElementType;
typedef struct SNode *Stack;
struct SNode{
	ElementType Data;
	Stack Next;
};


Stack CreateStack();  // 初始化链栈 
int IsEmpty(Stack S);  // 判断链栈是否为空 
void Push(Stack S,ElementType item);  // 入栈 
ElementType Pop(Stack S);  // 出栈
 

// 初始化 
Stack CreateStack(){
	Stack S;
	S = (Stack)malloc(sizeof(struct SNode));
	S->Next = NULL;
	return S;
}

// 判断是否为空 
int IsEmpty(Stack S){
	return (S->Next == NULL);
}

// 入栈
void Push(Stack S,ElementType item){
	Stack tmp;
	tmp = (Stack)malloc(sizeof(struct SNode));
	tmp->Data = item;
	// 链栈栈顶元素是链表头结点，新入栈的链表在栈顶元素后面 
	tmp->Next = S->Next;   
	S->Next = tmp;
} 

// 出栈
ElementType Pop(Stack S){
	Stack First;
	ElementType TopVal;
	if(IsEmpty(S)){
		printf("堆栈空");
		return;
	}else{
		First = S->Next;   // 出栈第一个元素在栈顶元素后面 
		S->Next = First->Next;  //把第一个元素从链栈删除 
		TopVal = First->Data;   // 取出被删除结点的值 
		free(First);  // 释放空间 
		return TopVal;
	}
} 

int main(){
	Stack S;
	S = CreateStack();
	printf("5入栈\n");
	Push(S,5);
	printf("7入栈\n");
	Push(S,7);
	printf("66入栈\n");
	Push(S,66);
	printf("%d出栈\n",Pop(S));
	printf("%d出栈\n",Pop(S));
	return 0;
}

思考：咦！这个链表的哑结点怎么不是头指针？
我们知道，链表是可以调整的，让s->Next一直指向栈顶元素，即可实现先入后出
不会就只能不断抄程序了。万一睡一觉起来就会了呢？

STL源码解析-stack

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
template <class T, class Sequence = deque<T> >
class stack {
//__STL_NULL_TMPL_ARGS是定义在 <stl_config.h>中，# define __STL_NULL_TMPL_ARGS <> 
  friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
  friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
  typedef typename Sequence::value_type value_type;
  typedef typename Sequence::size_type size_type;
  typedef typename Sequence::reference reference;
  typedef typename Sequence::const_reference const_reference;
protected:
// 底层容器
  Sequence c;
public:
//stack下面的这些操作都是借助底层容器的操作来完成
  bool empty() const { return c.empty(); }
  size_type size() const { return c.size(); }
  //两个函数的区别：
  reference top() { return c.back(); } //stack<int> a;a.top();会调用
  const_reference top() const { return c.back(); }  //const stack<int> a;a.top();会调用
  void push(const value_type& x) { c.push_back(x); }
  void pop() { c.pop_back(); }
};
//stack的比较实际上就是底层容器的比较，会调用底层容器的重载操作符==、<
template <class T, class Sequence>
bool operator==(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  return x.c == y.c;
}

template <class T, class Sequence>
bool operator<(const stack<T, Sequence>& x, const stack<T, Sequence>& y) {
  return x.c < y.c;
}

面向对象编程，通过模板类，友元函数，运算符重载等等实现
是不是很短？为什么这点代码就能实现？
把相应的已有的容器作为底部结构，将其接口改变，使之符合stack的特性，就形成一个stack
SGI STL stack默认底层容器是deque。

Theory > 数据结构与算法
#栈
Datastructures-栈
https://43.242.201.154/2024/09/08/Datastructures-栈/
Author
Dong
Posted on
September 8, 2024
Licensed under