栈

栈这种数据结构就太常见了

其特性也就是last in first out (lifo)，也就是因为它的这个特性，其是计算机的组成中的一个重要的数据结构

栈有两种形式，顺序结构和链式结构

①顺序栈

 1 #ifndef _SEQSTACK_H_
 2 #define _SEQSTACK_H_
 3 
 4 typedef void SeqStack;
 5 
 6 SeqStack* SeqStack_Create(int capacity);
 7 
 8 void SeqStack_Destroy(SeqStack* stack);
 9 
10 void SeqStack_Clear(SeqStack* stack);
11 
12 int SeqStack_Push(SeqStack* stack, void* item);
13 
14 void* SeqStack_Pop(SeqStack* stack);
15 
16 void* SeqStack_Top(SeqStack* stack);
17 
18 int SeqStack_Size(SeqStack* stack);
19 
20 int SeqStack_Capacity(SeqStack* stack);
21 
22 #endif

#include "SeqStack.h"
#include "SeqList.h"

SeqStack* SeqStack_Create(int capacity)
{
    return SeqList_Create(capacity);
}

void SeqStack_Destroy(SeqStack* stack)
{
    SeqList_Destroy(stack);
}

void SeqStack_Clear(SeqStack* stack)
{
    SeqList_Clear(stack);
}

int SeqStack_Push(SeqStack* stack, void* item)
{
    return SeqList_Insert(stack, item, SeqList_Length(stack));
}

void* SeqStack_Pop(SeqStack* stack)
{
    return SeqList_Delete(stack, SeqList_Length(stack) - 1);
}

void* SeqStack_Top(SeqStack* stack)
{
    return SeqList_Get(stack, SeqList_Length(stack) - 1);
}

int SeqStack_Size(SeqStack* stack)
{
    return SeqList_Length(stack);
}

int SeqStack_Capacity(SeqStack* stack)
{
    return SeqList_Capacity(stack);
}

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "SeqStack.h"
 4 
 5 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 6 
 7 int main(int argc, char *argv[]) 
 8 {
 9     SeqStack* stack = SeqStack_Create(20);
10     int a[10];
11     int i = 0;
12     
13     for(i=0; i<10; i++)
14     {
15         a[i] = i;
16         
17         SeqStack_Push(stack, a + i);
18     }
19     
20     printf("Top: %d
", *(int*)SeqStack_Top(stack));
21     printf("Capacity: %d
", SeqStack_Capacity(stack));
22     printf("Length: %d
", SeqStack_Size(stack));
23     
24     while( SeqStack_Size(stack) > 0 )
25     {
26         printf("Pop: %d
", *(int*)SeqStack_Pop(stack));
27     }
28     
29     SeqStack_Destroy(stack);
30     
31     return 0;
32 }

链式表

 1 #ifndef _LINKSTACK_H_
 2 #define _LINKSTACK_H_
 3 
 4 typedef void LinkStack;
 5 
 6 LinkStack* LinkStack_Create();
 7 
 8 void LinkStack_Destroy(LinkStack* stack);
 9 
10 void LinkStack_Clear(LinkStack* stack);
11 
12 int LinkStack_Push(LinkStack* stack, void* item);
13 
14 void* LinkStack_Pop(LinkStack* stack);
15 
16 void* LinkStack_Top(LinkStack* stack);
17 
18 int LinkStack_Size(LinkStack* stack);
19 
20 #endif

 1 #include <malloc.h>
 2 #include "LinkStack.h"
 3 #include "LinkList.h"
 4 
 5 typedef struct _tag_LinkStackNode
 6 {
 7     LinkListNode header;
 8     void* item;
 9 } TLinkStackNode;
10 
11 LinkStack* LinkStack_Create()
12 {
13     return LinkList_Create();
14 }
15 
16 void LinkStack_Destroy(LinkStack* stack)
17 {
18     LinkStack_Clear(stack);
19     LinkList_Destroy(stack);
20 }
21 
22 void LinkStack_Clear(LinkStack* stack)
23 {
24     while( LinkStack_Size(stack) > 0 )
25     {
26         LinkStack_Pop(stack);
27     }
28 }
29 
30 int LinkStack_Push(LinkStack* stack, void* item)
31 {
32     TLinkStackNode* node = (TLinkStackNode*)malloc(sizeof(TLinkStackNode));
33     int ret = (node != NULL) && (item != NULL);
34     
35     if( ret )
36     {
37         node->item = item;
38         
39         ret  = LinkList_Insert(stack, (LinkListNode*)node, 0);
40     }
41     
42     if( !ret )
43     {
44         free(node);
45     }
46     
47     return ret;
48 }
49 
50 void* LinkStack_Pop(LinkStack* stack)
51 {
52     TLinkStackNode* node = (TLinkStackNode*)LinkList_Delete(stack, 0);
53     void* ret = NULL;
54     
55     if( node != NULL )
56     {
57         ret = node->item;
58         
59         free(node);
60     }
61     
62     return ret;
63 }
64 
65 void* LinkStack_Top(LinkStack* stack)
66 {
67     TLinkStackNode* node = (TLinkStackNode*)LinkList_Get(stack, 0);
68     void* ret = NULL;
69     
70     if( node != NULL )
71     {
72         ret = node->item;
73     }
74     
75     return ret;
76 }
77 
78 int LinkStack_Size(LinkStack* stack)
79 {
80     return LinkList_Length(stack);
81 }

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include "LinkStack.h"
 4 
 5 /* run this program using the console pauser or add your own getch, system("pause") or input loop */
 6 
 7 int main(int argc, char *argv[]) 
 8 {
 9     LinkStack* stack = LinkStack_Create();
10     int a[10];
11     int i = 0;
12     
13     for(i=0; i<10; i++)
14     {
15         a[i] = i;
16         
17         LinkStack_Push(stack, a + i);
18     }
19     
20     printf("Top: %d
", *(int*)LinkStack_Top(stack));
21     printf("Length: %d
", LinkStack_Size(stack));
22     
23     while( LinkStack_Size(stack) > 0 )
24     {
25         printf("Pop: %d
", *(int*)LinkStack_Pop(stack));
26     }
27     
28     LinkStack_Destroy(stack);
29     
30     return 0;
31 }

栈这种数据结构虽然简单，但是却用的很频繁