数据结构——问题:一个数组实现两个堆栈

问:请用一个数组实现两个堆栈,要求最大地利用数组空间,使数组只要有空间入栈操作就可以成功

分析:一种比较聪明的方法是使这两个栈分别从数组的两头开始向中间生长;当两个栈的栈顶指针相遇时,表示两个栈都满了

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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXSIZE 10

typedef struct SNode
{
int data[MAXSIZE];
int top1, top2;
}DoubleStack;

DoubleStack* InitDoubleStack()
{
DoubleStack* ds = (DoubleStack*)malloc(sizeof(DoubleStack));
ds->top1 = -1;
ds->top2 = MAXSIZE;

return ds;
}

bool Push(DoubleStack* ds, int x, int tag)
{ // tag取1和2
bool ret = true;
if(ds->top2 - ds->top1 == 1)
{
printf("栈满\n");
ret = false;
}
else
{
if(tag == 1)
{
ds->data[++(ds->top1)] = x;
}
else
{
ds->data[--(ds->top2)] = x;
}
}
return ret;
}

int Pop(DoubleStack* ds, int tag)
{
if(tag == 1)
{
if(ds->top1 == -1)
{
printf("栈1空\n");
// return ERROR; 特殊值标志错误
}
else
{
return ds->data[ds->top1--];
}
}
else
{
if(ds->top2 == MAXSIZE)
{
printf("栈2空\n");
// return ERROR; 特殊值标志错误
}
else
{
return ds->data[ds->top2++];
}
}
}

int main()
{
DoubleStack* ds = InitDoubleStack();

int i;
for(i = 0; i < 5; i++)
{
Push(ds, 5 - i, 1);
Push(ds, 10 - i, 2);
}
Push(ds, 100, 1);
Push(ds, 1000, 2);

for(i = 0; i < 5; i++)
{
int x = Pop(ds, 1);
printf("%d\n", x);
}
Pop(ds, 1);

for(i = 0; i < 5; i++)
{
int x = Pop(ds, 2);
printf("%d\n", x);
}
Pop(ds, 2);

return 0;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2020-2021 zhangguoliu
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信