用List实现Stack基本功能

Stack是一种特殊的串行形式的数据结构。

      特点：

         1、只允许在栈顶压入新元素（push）；

         2、只允许先由栈顶元素输出，也就是后进先出（pop）；

      下面我打算用List来实现Stack最简单的功能。


     我的思路：

         根据List的知识，允许在List里面删除，插入元素，而stack不过是删除和插入的元素都是最后一个而已（top），所以，我想，stack不过是List的一个更具体的特殊功能的List。

         首先，创建List。

1
2
3
4
5
6
7
8
9
10
11
12
    
//Item
struct Itemtype
{
    int num;
};
//-------------------
//List
struct List
{
    Itemtype item;
    List *next;
};

           Item是自定义数据类型，里面可以有很多基本数据类型，例如int，float之类的。目前我只定义了一个int类型的。

          接下来，定义一个stack类。

          里面的公共接口也就是功能，看函数名字可以意会。私有数据有stack的大小，还有头指针，尾指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    
//Stack
class Stack
{
public:
    void Stack_Init(int Init_size);
    int Stack_Length();
    void Stack_Destroy();
    void Stack_Export();
    void Stack_Push(int item);
    int Stack_Pop();
private:
    int List_Size;
    List *head;
    List *top;
};

       

          接下来的事情也就是List的事情了，不过其中的很多细节还是要注意的。比如，stack已经为NULL了，那么再执行pop弹出函数就应该输出警示stack为NULL。同样的，超出长度也应该提示超出信息。

         具体的东西，都在源代码里面了，看不懂可以留言，欢迎交流。

         源代码：

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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
    
#include
using namespace std;
//-------------------
//Item
struct Itemtype
{
    int num;
};
//-------------------
//List
struct List
{
    Itemtype item;
    List *next;
};
//-------------------
//Stack
class Stack
{
public:
    void Stack_Init(int Init_size);
    int Stack_Length();
    void Stack_Destroy();
    void Stack_Export();
    void Stack_Push(int item);
    int Stack_Pop();
private:
    int List_Size;
    List *head;
    List *top;
};
//----------------------
//
void Stack::Stack_Init(int Init_size)
{
     List *temp;
     int num;
     top = new List;
     head = temp = new List;
     cout<<"Input "<      List_Size = Init_size;
     for(int i=1; i<=Init_size; ++i)
     {
         cin>>num;
         temp->item.num = num;
         if(i < Init_size)
         {
         temp->next = new List;
         temp = temp->next;
         }
         if(i == Init_size)
         {
             top = temp;
             break;
         }
     }
}
//---------------------------
//
void Stack::Stack_Push(int item)
{
    List *temp = new List;
    if(List_Size == 0)
    {
        head->item.num = item;
        List_Size++;
        return;
    }
    else
    {
    temp->item.num = item;
    top->next = temp;
    top = temp;
    List_Size++;
    }
}
//--------------------------
//
int Stack::Stack_Pop()
{
    List *temp = new List;
    int t;
    temp = head;
    if(List_Size == 0)
    {
        cout<<"Overflow!"<         return 0;
    }
    for(int i=0; i     {
        temp = temp->next;
    }
    t = top->item.num;
    delete(top);
    top = temp;
    List_Size--;
    return t;
}
//---------------------------
//
void Stack::Stack_Export()
{
    List *temp;
    temp = head;
    if(List_Size <= 0)
    {
        cout<<"Stack is Empty!"<         return;
    }
    for(int i=0; i     {
       cout<item.num<<" ";
       temp = temp->next;
    }
}
//----------------------------
//
void Stack::Stack_Destroy()
{
    List *temp;
    List *D_temp;
    temp =head;
    while(temp != top)
    {
        D_temp = temp;
        temp = temp->next;
        delete(D_temp);
    }
    delete(top);
    head = top;
    List_Size = 0;
}
//--------------------------------
//
int Stack::Stack_Length()
{
    if(List_Size <= 0)
    {
        cout<<"Stack is Empty!"<         return 0;
    }
    return List_Size;
}
//--------------------------------
//main
int main()
{
    Stack s;
    int sele_num;
    int Init_size;
    bool IF = false;
loop:
    cout<<"-------------Stack menu-------------"<     cout<<"1.Stack_Init"<     cout<<"2.Stack_Push"<     cout<<"3.Stack_Pop"<     cout<<"4.Stack_Length"<     cout<<"5.Stack_Export"<     cout<<"6.Stack_Destroy"<     cout<<"Select:";
    cin>>sele_num;
    if(sele_num == 1)
    {
        IF = true;
    }
    if(IF == false)
    {
        cout<<"Sorry! you have to Init_Stack first!"<         goto loop;
    }
    switch(sele_num)
    {
    case 1:
        {
           cout<<"Input the Init size of Stack:"<            cin>>Init_size;
           s.Stack_Init(Init_size);
           goto loop;
        }
    case 2:
        {
            int num;
            cout<<"push num: "<             cin>>num;
            s.Stack_Push(num);
            goto loop;
        }
    case 3:
        {
            cout<<"pop num: "<< s.Stack_Pop()<             goto loop;
        }
    case 4:
        {
            cout<<"size of Stack: "<             cout<             goto loop;
        }
    case 5:
        {
            cout<<"Stack Export: ";
            s.Stack_Export();
            cout<             goto loop;
        }
    case 6:
        {
            s.Stack_Destroy();
            cout<<"The Stack has been destroyed!"<             IF = false;
            goto loop;
        }
    default:
        {
        cout<<"Not in range!"<         goto loop;
        }
    }
    return 0;
}