C++栈-链式存储

LinkStack.h

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
#pragma once
#include<iostream>
using namespace std;


struct Node
{
int data;
Node* next;
};


class LinkStack
{
private:
Node* top; // 栈顶指针
Node* base; // 栈底指针
public:
LinkStack();
LinkStack(int array[],int n);

int GetTop(); // 获取栈顶元素

void Push(int e); // 入栈,通过e返回数据
bool Pop(int &e); // 出栈

void ShowAll(); // 头为栈底,尾为栈顶


};

LinkStack.cpp

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
#include "LinkStack.h"

LinkStack::LinkStack()
{
top = base = NULL;
}

LinkStack::LinkStack(int array[], int n)
{
top = base = NULL;
for (int i = 0; i < n; i++)
Push(array[i]);
}

// 获取栈顶元素,如果为空则则返回-1
int LinkStack::GetTop()
{
if (top == NULL)
return -1;
return top->data;
}

// 入栈
void LinkStack::Push(int e)
{
Node* p = new Node();
p->data = e;

if (base == NULL)
{
base = p;
top = p;
p->next = NULL;
return;
}
top->next = p;

top = p; // 栈顶指针总是指向最后一个节点


}

bool LinkStack::Pop(int& e)
{
// 通过e返回删除节点的元素

Node* prev = NULL, * p = base;

if (p == NULL)
return false;
e = top->data; // 返回删除的数据
while (p != NULL)
{
if (p == top)
break;
prev = p; // 每次prev记录的是上一个结点
p = p->next;
}
if (prev != NULL)
{
prev->next = NULL;
top = prev;
}
else
base = top = NULL; // 如果prev为NULL,则第一个结点就是需要删除的结点

delete(p);

return true;
}

void LinkStack::ShowAll()
{
Node* p = base;
while (p!=NULL)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}

main.cpp

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
#include<iostream>
using namespace std;

#include"LinkStack.h"

int main()
{
int n = 4;
int array[] = { 10,20,30,40 };

LinkStack stack(array,n);

stack.ShowAll();
int e;
stack.Pop(e);
stack.Pop(e);
stack.Pop(e);
stack.ShowAll();
stack.Pop(e);
stack.Pop(e);// 当栈为空时,此时出栈是否会报错

stack.ShowAll();
cout << endl;
return 0;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!