【锐格】数据结构-栈和队列

本文最后更新于:2021年10月24日 晚上

欢迎加入NEFU计算机编程交流群:523539085

顺序栈

4909

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
149
150
151
152
153
154
155
156
157
#include<iostream>
using namespace std;

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

class SeqStack {
private:
int *array;
int maxSize;
int top;
void stackFull();
public:
SeqStack(int sz=0);
void Push(const int &x);
bool Pop(int &x);
bool getTop(int &x);
bool isEmpty() const
{
return (top==-1)?true:false;
}
bool isFull() const
{
return (top==maxSize-1)?true:false;
}
int getSize() const
{
return top+1;
}
};

SeqStack::SeqStack(int sz):top(-1),maxSize(sz)
{
array = new int[maxSize];
}

void SeqStack::Push(const int &x)
{
if (this->isFull())
this->stackFull();
array[++top] = x;
}

bool SeqStack::Pop(int &x)
{
if (this->isEmpty())
return false;
x = array[top--];
return true;
}

bool SeqStack::getTop(int &x)
{
if (this->isEmpty())
return false;
x = array[top];
return true;
}

void SeqStack::stackFull()
{
maxSize = maxSize*2;
int *temp = new int[maxSize];
int i;
for (i=0;i<=top;i++)
temp[i] = array[i];
delete []array;
array = temp;
}

class LinkList {
private:
Node *first;
public:
LinkList();
void Insert(const int &x);
int Length();
void Reverse();
void output();
};

LinkList::LinkList()
{
first = new Node();
first->next = NULL;
}

void LinkList::Insert(const int &x)
{
Node *t = first;
while (t->next!=NULL)
t = t->next;
Node *n = new Node();
n->data = x;
n->next = t->next;
t->next = n;
}

int LinkList::Length()
{
int count=0;
Node *t = first;
while (t->next!=NULL) {
t = t->next;
count++;
}
return count;
}

void LinkList::Reverse()
{
//write your code here
SeqStack S(Length());
Node *p=first->next;
int x;
//output();
first->next=NULL;
//output();
while(p!=NULL)
{
S.Push(p->data);
p=p->next;
}
//output();
while(!S.isEmpty())
{
S.Pop(x);
Insert(x);
}
}

void LinkList::output()
{
Node *t = first;
while (t->next!=NULL) {
t=t->next;
cout << t->data << " ";
}
cout << endl;
}

int main()
{
LinkList l;
int x;
cin >> x;
while (x!=-1) {
l.Insert(x);
cin >> x;
}
l.output();
l.Reverse();
l.output();
return 0;
}

4908

从上一道题cv就行

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

class SeqStack {
private:
int *array;
int maxSize;
int top;
void stackFull();
public:
SeqStack(int sz=0);
void Push(const int &x);
bool Pop(int &x);
bool getTop(int &x);
bool isEmpty() const
{
return (top==-1)?true:false;
}
bool isFull() const
{
return (top==maxSize-1)?true:false;
}
int getSize() const
{
return top+1;
}
int getMaxSize() const
{
return maxSize;
}
void MakeEmpty()
{
top = -1;
}
};

SeqStack::SeqStack(int sz):top(-1),maxSize(sz)
{
//write your code here
array=new int[maxSize];
}

void SeqStack::Push(const int &x)
{
//write your code here
if(this->isFull())
this->stackFull();
array[++top]=x;
}

bool SeqStack::Pop(int &x)
{
//write your code here
if(this->isEmpty())
return false;
x=array[top--];
return true;
}

bool SeqStack::getTop(int &x)
{
//write your code here
if(this->isEmpty())
return false;
x=array[top];
return true;
}

void SeqStack::stackFull()
{
//write your code here
maxSize*=2;
int *tmp=new int[maxSize];
for(int i=0;i<=top;i++)
tmp[i]=array[i];
delete []array;
array=tmp;
}

int main()
{
int x;
SeqStack ss(4);
ss.Push(1);
ss.Push(2);
ss.Push(3);
ss.Push(4);
ss.Push(5);
ss.Pop(x);
cout << x << endl;
cout << ss.getSize() << endl;
cout << ss.getMaxSize() << endl;
return 0;
}

4873待解决

4870

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

#define maxsize 10000

typedef struct
{
int data[maxsize]; //存放栈中元素
int top; //栈顶指针
}SqStack;

//初始化栈
void initStack(SqStack &st)
{
st.top = -1;
}

//进栈算法
int Push(SqStack &st, int x)
{
if(st.top == maxsize - 1)
return 0;
++(st.top); //先移动指针再进栈
st.data[st.top] = x;
return 1;
}

//出栈算法
int Pop(SqStack &st , int &x)
{
if(st.top == -1)
return 0;
x = st.data[st.top];
--(st.top);
return 1;
}

void isEmpty(SqStack st)
{
//write your own codes
if(st.top==-1)
printf("Stack is empty\n");
else
printf("Stack is not empty\n");
}

int main()
{
int n , i , e;
SqStack S;
initStack(S);
isEmpty(S); //需要写的函数
scanf("%d",&n);
for(i = 0 ; i < n; ++i)
{
scanf("%d",&e);
Push(S,e);
}
isEmpty(S);
scanf("%d",&n);
for(int i = 0 ;i < n ; ++i)
Pop(S,e);
isEmpty(S);
return 0;
}

4869

cv大法好

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

#define maxsize 10000

typedef struct
{
int data[maxsize]; //存放栈中元素
int top; //栈顶指针
}SqStack;

//初始化栈
void initStack(SqStack &st)
{
st.top = -1;
}

//进栈算法
int Push(SqStack &st, int x)
{
if(st.top == maxsize - 1)
return 0;
++(st.top); //先移动指针再进栈
st.data[st.top] = x;
return 1;
}

//出栈算法
int Pop(SqStack &st , int &x)
{
if(st.top == -1)
return 0;
x = st.data[st.top];
--(st.top);
return 1;
}

bool isEmpty(SqStack st)
{
//write your own codes
if(st.top==-1)
return true;
return false;
}

//输出栈中的元素
int print_S(SqStack st)
{
if( isEmpty(st) )
{
printf("Stack is Empty");
return 0;
}
int iPointer = st.top;
while(iPointer != -1)
{
printf("%d ",st.data[iPointer]);
--iPointer;
}
printf("\n");
return 1;
}

int main()
{
int n , i , e;
SqStack S;
initStack(S);
scanf("%d",&n);
for(i = 0 ; i < n; ++i)
{
scanf("%d",&e);
Push(S,e); //要写的函数:进栈操作
}
print_S(S);
scanf("%d",&n);
for(int i = 0 ;i < n ; ++i)
{
Pop(S,e); //要写的函数:出栈操作
printf("%d ",e);
}
printf("\n");
print_S(S);
return 0;
}

4868

cvcv

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

#define maxsize 10000

typedef struct
{
int data[maxsize]; //存放栈中元素
int top; //栈顶指针
}SqStack;

//初始化栈
void initStack(SqStack &st)
{
st.top = -1;
}

//进栈算法
int Push(SqStack &st, int x)
{
if(st.top == maxsize - 1)
return 0;
++(st.top); //先移动指针再进栈
st.data[st.top] = x;
return 1;
}

bool isEmpty(SqStack st)
{
//write your own codes
if(st.top==-1)
return true;
return false;
}

//输出栈中的元素
int print_S(SqStack st)
{
if( isEmpty(st) )
{
printf("Stack is Empty");
return 0;
}
int iPointer = st.top;
while(iPointer != -1)
{
printf("%d ",st.data[iPointer]);
--iPointer;
}
printf("\n");
return 1;
}

int main()
{
int n , i , e;
SqStack S;
initStack(S);
scanf("%d",&n);
for(i = 0 ; i < n; ++i)
{
scanf("%d",&e);
Push(S,e);
}
print_S(S); //需要写出的函数:打印栈
return 0;
}

链式栈

4225

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
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define TRUE 1
#define FALSE 0
#define s top

typedef int Status;

typedef struct Node
{
char data;
struct Node *next;
}Node;

Node *top;

const Status isEmpty()
{
return (top==NULL)?TRUE:FALSE;
}

void Push(const char x)
{
Node *n = (struct Node *)malloc(sizeof(struct Node));
n->data = x;
n->next = top;
top = n;
}

Status Pop(char *x)
{
if (isEmpty())
return FALSE;
*x = top->data;
Node *t = top;
top = top->next;
free(t);
return TRUE;
}

Status getTop(char *x)
{
if (isEmpty())
return FALSE;
*x = top->data;
return TRUE;
}

Status match(char f[]) {
char* p = f;
char ch;
while (*p != '\0') {
if (*p == 39) {//单引号
++p;
while (*p != 39)//小括号
++p;
++p;
}
else if (*p == 34) {//双引号
++p;
while (*p != 34)//小括号
++p;
++p;
}
else {
switch (*p) {
case '(':
case '{':
case '[':Push(*p); break;
case ')':getTop(&ch);
if (ch == '(')
Pop(&ch);
else return 0;
break;
case '}':getTop(&ch);
if (ch == '{')
Pop(&ch);
else return 0;
break;
case ']':getTop(&ch);
if (ch == '[')
Pop(&ch);
else return 0;
}
++p;
}
}
if (isEmpty())//如果栈为空,表示括号都已经匹配
return 1;
else
return 0;
}

int main()
{
top = NULL;
char str[100];
gets(str);
if (match(str))
printf("YES\n");
else
printf("NO\n");
return 0;
}

栈与递归

4227

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<stdio.h>

// write your code here
int sum(int a[],int x)
{
if(x<1) return 0;
return a[x-1]+sum(a,--x);
}

int main()
{
int a[6],i;
for (i=0;i<6;i++)
scanf("%d", a+i);
printf("%d\n", sum(a, 6));
return 0;
}

4226

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>

// write your code here
int max(int a[], int x)
{
if(x<1) return -1;
int tmp=max(a, x-1);
return a[x-1]>tmp?a[x-1]:tmp;
}

int main()
{
int a[6],i;
for (i=0;i<6;i++)
scanf("%d", a+i);
printf("%d\n", max(a, 6));
return 0;
}

4228

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>

// write your code here
float average(float a[],int n,int y)
{
if (n == 1)
return a[0];
else
return ((n - 1) * average(a, n - 1, y) + a[n - 1]) / n;
}

int main()
{
float a[6];
int i;
for (i=0;i<6;i++)
scanf("%f", a+i);
printf("%.2f\n", average(a, 6, 6));
return 0;
}

队列

4236

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
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define TRUE 1
#define FALSE 0

typedef int Status;

typedef struct Node {
int data;
struct Node *next;
}Node, *pNode;

pNode p;

void InitQueue()
{
p = (struct Node *)malloc(sizeof(struct Node));
p->next = p;
}

void EnQueue(const int x)
{
// write your code here
Node *s;
s = (Node *)malloc(sizeof(Node));
s->data = x;
if (p == NULL)
{
p = s;
p->next = p;
}
else
{
s->next = p->next; //将s作为*p之后的结点
p->next = s;
p = s; //*p指向*s
}
}

const Status isEmpty()
{
// write your code here

}

Status DeQueue(int *x)
{
// write your code here
Node *s;
if (p == NULL)
return 0;
if (p->next == NULL)
{ //只有一个结点的情况
*x = p->data;
free(p);
p = NULL;
}
else
{ //将*p之后结点的data域值赋给x,然后删除之
s = p->next;
*x = s->data;
p->next = s->next;
free(s);
}
return 1;
}

const void Print()
{
Node *t = p->next;
while (t->next!=p->next) {
printf("%d ", t->next->data);
t = t->next;
}
printf("\n");
}

int main()
{
InitQueue();
int x;
EnQueue(1);
EnQueue(2);
EnQueue(3);
DeQueue(&x);
EnQueue(4);
DeQueue(&x);
DeQueue(&x);
DeQueue(&x);
EnQueue(5);
Print();
return 0;
}

4915

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

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

class LinkList {
private:
Node *first;
public:
LinkList();
void Insert(const int &x);
Node *First();
int Length(Node *n);
};

LinkList::LinkList()
{
first = new Node();
first->next = NULL;
}

void LinkList::Insert(const int &x)
{
Node *t = first;
while (t->next!=NULL)
t = t->next;
Node *n = new Node();
n->data = x;
n->next = t->next;
t->next = n;
}

Node *LinkList::First()
{
return first;
}

//write your code here
int LinkList::Length(Node *n)
{
if(n==NULL) return -1;
return 1+Length(n->next);
}

int main()
{
LinkList l;
int x;
cin >> x;
while (x!=-1) {
l.Insert(x);
cin >> x;
}
//write your code here
printf("%d\n", l.Length(l.First()));
return 0;
}

4872

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
#include<stdio.h>
#include<stdlib.h>

typedef struct QNode
{
int data;
struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;


int InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if( !Q.front) exit(0);
Q.front->next = NULL;
return 1;
}

int EnQueue(LinkQueue &Q, int e)
{
QNode* p=(QueuePtr)malloc(sizeof(QNode));
//printf("--\n");
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return 1;
}

int DeQueue(LinkQueue &Q,int &e)
{
QNode *p=Q.front->next;
Q.front->next=p->next;
if(p==Q.rear) Q.rear==Q.front;
e=p->data;
free(p);
return 1;
}
int main()
{
int m,n;
int i,e;
LinkQueue Q;
InitQueue(Q);
scanf("%d",&n);
for(i = 0 ; i < n ; ++i)
{
scanf("%d",&e);
EnQueue(Q,e);
}
scanf("%d",&m);
for(i = 0 ; i < m ; ++i)
{
DeQueue(Q,e);
printf("%d ",e);
}
printf("\n");
return 0;
}

4235

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
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

#define TRUE 1
#define FALSE 0

typedef int Status;

int *q;
int maxSize;
int front;
int rear;
int tag;

const Status isFull()
{
// write your code here
if(rear%maxSize==front&&tag==1)
return 1;
return 0;
}

const Status isEmpty()
{
// write your code here
if(rear==front&&tag==0)
return 1;
return 0;
}

void InitStack(int sz)
{
maxSize = sz;
q = (int *)malloc(maxSize*sizeof(int));
front = 0;
rear = 0;
tag = 0;
}

void output()
{
int i;
for (i=0;i<maxSize;i++)
printf("%d ", q[i]);
}

Status EnQueue(int x)
{
// write your code here
if(isFull()) return 0;
q[rear]=x;
rear=(rear+1)%maxSize;
if(rear==front) tag=1;
return 1;
}

Status DeQueue(int x)
{
// write your code here
if(isEmpty()) return 0;
x=q[front];
front=(front+1)%maxSize;
if(rear==front) tag==0;
return 1;
}

int main()
{
InitStack(4);
int m;
EnQueue(1);
DeQueue(m);
DeQueue(m);
EnQueue(2);
EnQueue(0);
EnQueue(4);
EnQueue(5);
DeQueue(m);
DeQueue(m);
EnQueue(6);
output();
return 0;
}