数据结构【三】:栈和队列(C++)

顺序栈


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
#include<iostream>
using namespace std;
const int stackIncreament=20; //栈满时增加空间大小
template<class T>
class Stack
{
public:
Stack(int num); //构造函数 产生数据空间为num的栈
~Stack(){delete []data;}; //析构函数
void push(T &x); //将数据x压栈
bool pop(T &x); //将顶端数据出栈
bool getTop(T &x); //只是获取顶端数据
bool isEmpty()const; //判空函数
bool isFull()const; //判满函数
int getSize()const; //获取栈中元素个数
void makeEmpty(){top=-1;}; //置空栈
void output(); //输出
protected:
T *data;
int maxSize;
int top;
void overflowProcess();
} ;
template<class T>
Stack<T>::Stack(int num)
{
top=num;
data=new T[top--];
if(data==NULL)
{
cerr<<"申请空间失败";
exit(1);
}
for(int i=0;i<=top;i++)
cin>>data[i];
}
template<class T>
void Stack<T>::push(T &x)
{
if(isFull()) //判满设置
overflowProcess(); //扩容设置
data[++top]=x;
}
template<class T>
void Stack<T>::overflowProcess()
{
T *newData=new T[maxSize+stackIncreament];
if(newData==NULL)
{
cerr<<"申请空间失败";
exit(1);
}
for(int i=0;i<=top;i++)
newData[i]=data[i];
maxSize+=stackIncreament;
delete []data;
data=newData;
}
template<class T>
bool Stack<T>::pop(T &x)
{
if(isEmpty())
return false;
x=data[top--];
return true;
}
template<class T>
bool Stack<T>::getTop(T &x)
{
if(isEmpty())
return false;
x=data[top];
return true;
}
template<class T>
bool Stack<T>::isFull()const
{
if(top==maxSize-1) //注意判满条件
return true;
else
return false;
}
template<class T>
bool Stack<T>::isEmpty()const
{
if(top==-1)
return true;
else
return false;
}
template<class T>
int Stack<T>::getSize()const
{
return top+1;
}
template<class T>
void Stack<T>::output()
{
int i;
for( i=top;i>0;i--)
cout<<data[i]<<",";
cout<<data[i]<<endl;
}
int main()
{
int num;
cout<<"输入数据个数";
cin>>num;
Stack<int> test(num);
test.output();
cout<<"输入扩充数据";
cin>>num;
test.push(num);
test.output();
test.pop(num);
test.output();
}

/*
1、压栈的时候注意判满扩容设置
*/

顺序双栈

头和位同时存储数据,向中间靠拢。

链栈(带头节点)


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
141
142
143
144
145
#include<iostream>
using namespace std;
template <class T>
struct LinkNode
{
T data;
LinkNode<T> *next=NULL;
LinkNode()
{
next=NULL;
}
LinkNode(T x)
{
data=x;
};
LinkNode(LinkNode<T> *p)
{
next=p;
}
LinkNode(T x,LinkNode<T> *p)
{
data=x;
next=p;
}
};
template <class T>
class Stack
{
public:
Stack(); //构造函数
~Stack(){makeEmpty();}; //析构函数
void push(T &x); //将数据x压栈
bool pop(T &x); //将顶端数据出栈
bool getTop(T &x); //只是获取顶端数据
bool isEmpty()const; //判空函数
int getSize()const; //获取栈中元素个数
void makeEmpty(); //置空栈
void output(); //输出
protected:
LinkNode<T> *head;
};
template<class T>
Stack<T>::Stack()
{
head=new LinkNode<T>;
}
template<class T>
void Stack<T>::push(T &x)
{

LinkNode<T> *newNode=new LinkNode<T>(x); //使用前插法构建
if(newNode==NULL)
{
cerr<<"储存分配错误"<<endl;
exit(1);
}
newNode->next=head->next;
head->next=newNode;
}
template<class T>
bool Stack<T>::isEmpty()const
{
if(head->next==NULL)
return true;
else
return false;
}
template<class T>
bool Stack<T>::pop(T &x)
{
LinkNode<T> *p;
if(isEmpty())
return false;
else
{
p=head->next;
x=p->data;
head->next=p->next;
delete p;
return true;
}
}
template<class T>
bool Stack<T>::getTop(T &x)
{
if(isEmpty())
return false;
x=head->next->data;
return true;
}
template<class T>
int Stack<T>::getSize()const
{
LinkNode<T> *p=head->next;
int num=0;
while(p!=NULL)
{
num++;
p=p->next;
}
return num;
}
template<class T>
void Stack<T>::makeEmpty()
{
LinkNode<T> *p=head->next;
while(head->next!=NULL)
{
head->next=p->next;
delete p;
p=head->next;
}
}
template<class T>
void Stack<T>::output()
{
LinkNode<T> *p=head->next;
while(p!=NULL)
{
cout<<p->data<<",";
p=p->next;
}
}
int main()
{
int num,x;
cout<<"输入数据个数";
cin>>num;
Stack<int> test;
while(num--)
{
cin>>x;
test.push(x);
}
test.output();
test.pop(x);
cout<<x<<endl;
test.pop(x);
test.pop(x);
cout<<test.getSize();
test.output();
}
/*
//使用前插法构建栈
*/

顺序(循环)队列


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
#include<iostream>
using namespace std;
template <class T>
class Queue
{
public:
Queue(int size); //构造函数
~Queue(){delete []data;}; //析构函数
bool enQueue(T &x); //入队函数
bool deQueue(T &x); //出队函数
bool getFront(T &x); //获取队头的元素函数
void makeEmpty(); //置空
bool isEmpty()const; //判空
bool isFull()const; //判满
int getSize()const; //获取队列元素数量
protected:
T *data;
int front,rear;
int maxSize;
};
template<class T>
Queue<T>::Queue(int size)
{
maxSize=size+1; //因为需要空出一个作为判断空满状态的空间
data=new T[size];
front=rear=0;
}
template<class T>
bool Queue<T>::isEmpty()const
{
if(rear==front) //注意判空条件
return true;
else
return false;
}
template<class T>
bool Queue<T>::isFull()const
{
if((rear+1)%maxSize==front) //注意判满条件
return true;
else
return false;
}
template<class T>
int Queue<T>::getSize()const
{
return (rear-front+maxSize)%maxSize; //注意队列长度如何计算
}
template<class T>
bool Queue<T>::enQueue(T &x)
{
if(isFull())
return false;
else
{
data[rear]=x;
rear=(rear+1)%maxSize; //注意每次进数后 rear+1 并且求余数
return true;
}
}
template<class T>
bool Queue<T>::deQueue(T &x)
{
if(isEmpty())
return false;
x=data[front];
front=(front+1)%maxSize; //注意每次取数后 rear+1 并且求余数
return true;
}
template<class T>
bool Queue<T>::getFront(T &x)
{
if(isEmpty())
return false;
x=data[front];
return true;
}
template<class T>
void Queue<T>::makeEmpty()
{
front=rear=0;
}
int main()
{
int num,x;
Queue<int> test1(3);
cout<<"输入需要的数据数量";
cin>>num;
for(int i=0;i<num;i++)
{
cin>>x;
test1.enQueue(x);
}
for(int i=0;i<num;i++)
{
if(test1.deQueue(x))
cout<<x<<",";
}
}
/*
1、顺序循环表的判空满有很多种方法,这里我们使用一种方法申请的空间中要有一个空间空出来,用来判断空满状态。
2、rear=front为空
3、(rear+1)%maxSize==front 避免如:max=8,7+1!=0判为不满的情况
4、入队列 每次都要rear=(rear+1)%maxSize,保存下标在范围内循环
5、同理,出队列每次也要front=(front+1)%maxSize
6、计算队列长为(rear-front+maxSize)%maxSize,避免负数计算错误
*/

1、顺序循环表的判空满有很多种方法,这里我们使用一种方法申请的空间中要有一个空间空出来,用来判断空满状态。

2、rear=front为空

3、(rear+1)%maxSize==front 避免如:max=8,7+1!=0判为不满的情况

4、入队列 每次都要rear=(rear+1)%maxSize,保存下标在范围内循环

5、同理,出队列每次也要front=(front+1)%maxSize

6、计算队列长为(rear-front+maxSize)%maxSize,避免负数计算错误

链(循环)队列(带头节点)


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
141
142
143
144
145
146
147
148
#include<iostream>
using namespace std;
template <class T>
struct LinkNode
{
T data;
LinkNode *next;
LinkNode()
{
next=NULL;
}
LinkNode(T x)
{
data=x;
}
LinkNode(LinkNode<T> *p)
{
next=p;
}
LinkNode(T x,LinkNode<T> *p)
{
data=x;
next=p;
}
};
template<class T>
class Queue
{
public:
Queue(); //构造函数
~Queue(){makeEmpty();}; //析构函数
bool enQueue(T &x); //入队函数
bool deQueue(T &x); //出队函数
bool getFront(T &x); //获取队头的元素函数
void makeEmpty(); //置空
bool isEmpty()const; //判空
int getSize()const; //获取队列元素数量
void output();
protected:
LinkNode<T> *head,*rear; //多定义一个rear,入队列时方便后续插入
};
template<class T>
Queue<T>::Queue()
{
head=rear=new LinkNode<T>;
head->next=head;
}
template<class T>
bool Queue<T>::isEmpty()const
{
if(head->next==head)
return true;
else
return false;
}
template<class T>
int Queue<T>::getSize()const
{
LinkNode<T> *p=head->next;
int num=0;
while(p!=head)
{
num++;
p=p->next;
}
return num;
}
template<class T>
bool Queue<T>::enQueue(T &x)
{
LinkNode<T> *newNode=new LinkNode<T>(x);
if(newNode==NULL)
{
cerr<<"申请空间失败";
exit(1);
}
newNode->next=rear->next;
rear->next=newNode;
rear=newNode; //移动队尾
return true;
}
template<class T>
bool Queue<T>::deQueue(T &x)
{
LinkNode<T> *p;
if(isEmpty())
return false;
else
{
p=head->next;
x=p->data;
head->next=p->next;
delete p;
return true;
}
}
template<class T>
bool Queue<T>::getFront(T &x)
{
if(isEmpty())
return false;
x=head->next->data;
return true;
}
template<class T>
void Queue<T>::makeEmpty()
{
LinkNode<T> *p=head->next;
while(head->next!=head)
{
head->next=p->next;
delete p;
p=head->next;
}
}
template<class T>
void Queue<T>::output()
{
LinkNode<T> *p=head->next;
while(p!=head)
{
cout<<p->data;
p=p->next;
}
}
int main()
{
int num,x;
Queue<int> test1;
cout<<"输入需要的数据数量";
cin>>num;
for(int i=0;i<num;i++)
{
cin>>x;
test1.enQueue(x);
}
test1.output();

for(int i=0;i<num;i++)
{
test1.deQueue(x);
cout<<x<<",";
}
}
/*
1、因为是单向循环不是双向循环所以多定义一个rear,入队列时方便后续插入
2、后插法创建队列
*/

1、因为是单向循环不是双向循环所以多定义一个rear,入队列时方便后续插入

2、后插法创建队列

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~