基本概念
栈的定义
栈（Stack）是只允许在一端进行插入或删除的线性表。首先栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。
1
栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。
栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构
栈的常见基本操作
- InitStack(&S)：初始化一个空栈S
- StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false
- Push(&S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶
- Pop(&S, &x)：出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回
- GetTop(S, &x)：读栈顶元素，若栈S非空，则用x返回栈顶元素
- DestroyStack(&S)：栈销毁，并释放S占用的存储空间（“&”表示引用调用）
栈的顺序存储结构
栈的顺序存储
采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针（top）指示当前栈顶元素的位置。
若存储栈的长度为StackSize，则栈顶位置top必须小于StackSize。当栈存在一个元素时，top等于0，因此通常把空栈的判断条件定位top等于-1。
若现在有一个栈，StackSize是5，则栈的普通情况、空栈、满栈的情况分别如下图所示：
2.1
代码实现
代码实现与顺序表的思路差不多。不过栈是后进先出。头文件如下所示。
1
2
3
4
5
6
7
8
9
10
| #include<String>
#include<iostream>
using namespace std;
typedef int elemtype;
typedef struct {
elemtype* elem;
int top;
int size;
}stack;
|
实现的功能如下所示。进栈函数可改成动态的。若栈已满可扩容，思路与顺序表扩容一样。以下代码并未实现。
1
2
3
4
5
6
7
| bool Initstack(stack& S , int size);
bool stackempty(stack* S);
bool push(stack* S, elemtype x);
bool pop(stack* S, elemtype x);
elemtype gettop(stack* S);
bool delstack(stack &S);
void display(stack* S);
|
函数具体细节如下所示
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
| bool Initstack(stack& S, int size) {
S.elem = new elemtype[size];
S.size = size;
if (S.elem == NULL){
return false;
}
S.top = -1;
return true;
}
bool stackempty(stack* S) {
if (S->top == -1){
return true;
}
return false;
}
bool push(stack* S, elemtype x) {
if (S->top == (S->size -1)){
return false;
}
S->top++;
S->elem[S->top] = x;
return true;
}
bool pop(stack* S, elemtype x) {
if (S->top == -1){
return false;
}
x = S->elem[S->top];
S->top--;
return true;
}
elemtype gettop(stack* S) {
elemtype x;
if (S->top == -1){
return -1;
}
x = S->elem[S->top];
return x;
}
bool delstack(stack& S) {
S.elem = NULL;
S.top = -1;
S.size = 0;
delete[] S.elem;
if (S.elem == NULL){
return true;
}
return false;
}
void display(stack* S) {
int n = S->top;
while (n>-1){
cout << S->elem[n];
n--;
}
cout << endl;
}
|
调试主代码如下所示。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| int main () {
stack S;
int x = 0;
Initstack(S,4);
stackempty(&S);
x = gettop(&S);
cout << "top is : " << x << endl;
cout << " input 4 num :" <<endl;
for (int i = 0; i < 4; i++){
cin >> x;
push(&S, x);
}
display(&S);
pop(&S,x);
display(&S);
bool re = delstack(S);
if (re == 1) {
cout << "del success" << endl;
}
return 0;
}
|
实验结果
3
共享栈（两栈共享空间）
概念
利用栈底位置相对不变的特征，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如下图所示：
4
两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top0+1=top1）时，判断为栈满。当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减一再赋值出栈时则刚好相反。
代码实现与顺序栈差不多。就是两个栈共享一段存储空间，元素入栈、出栈时需要判断对哪个栈进行操作。
栈的链式存储结构
链栈
采用链式存储的栈称为链栈，链栈的优点是便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定所有操作都是在单链表的表头进行。这里规定链栈没有头节点，Lhead指向栈顶元素，如下图所示。
5
对于空栈来说，链表原定义是头指针指向空，那么链栈的空其实就是top=NULL的时候。
链栈进栈
对于链栈的进栈push操作，假设元素值为e的新节点是s，top为栈顶指针，示意图如下：
6.1
链栈的出栈
链栈的出栈pop操作，也是很简单的三句操作。假设变量p用来存储要删除的栈顶结点，将栈顶指针下移以为，最后释放p即可，如下图所示：
7
代码实现
链栈的进栈相当于链表的前向插入，first in last out。以下代码思想主要是借鉴list链表的构建方法，使用head指针一直指向top。入栈时则head指向新的node，新的node的next指向之前的top。
头文件如下所示
1
2
3
4
5
6
7
8
9
| #include<String>
#include<iostream>
using namespace std;
typedef struct Node {
int data;
Node* next;
int cout;
}Node;
|
实现的函数如下
1
2
3
4
5
| void Initstack(Node *head);
Node* addnode(Node *head, int data);
int display(Node* head, int x);
Node* findnode(Node* head, int x);
bool delnode(Node* head, int n);
|
具体函数细节如下
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
| void Initstack(Node* head) {
head->next = NULL;
head->cout = 0;
}
Node* addnode(Node* head, int data) {
Node* s = new Node;
Node* tail = NULL;
s->data = data;
if (head->cout ==0){
head->next = s;
s->next = NULL;
head->cout++;
}
else{
s->next = head->next;
head->next = s;
head->cout++;
}
return head;
}
int display(Node* head, int x) {
int count = 0;
Node* p = head->next;
cout << p->data << " ";
cout << "链栈中的元素有：";
while (p!= NULL) {
cout << p->data << " ";
if (x == p->data) {
count++;
}
p = p->next;
}
return count;
}
Node* findnode(Node* head, int x) {
Node* p = head->next;
while (p != NULL) {
if (x == p->data) {
return p;
}
p = p->next;
}
return NULL;
}
bool delnode(Node* head, int n) {
Node* p = head->next;
if (p ==NULL){
return false;
}
n = p->data;
Node* after = p->next;
cout << "ssssss: " << after->data;
head->next = after;
head->cout--;
delete[] p;
return true;
}
|
实验截图如下所示
8
数据结构：栈和队列(Stack & Queue)【详解】-CSDN博客
