16 files changed, 546 insertions, 0 deletions

diff --git a/c/dataStructure/栈和队列/栈/链栈/ack.c b/c/dataStructure/栈和队列/栈/链栈/ack.c
new file mode 100755
index 0000000..9d12544
--- /dev/null
+++ b/c/dataStructure/栈和队列/栈/链栈/ack.c
@@ -0,0 +1,20 @@
+#include "stack.h"
+
+int ack (int m, int n)
+{
+    if (m == 0)
+        return n+1;
+    else if (n == 0)
+        return ack(m-1,1);
+    else
+        return ack(m-1,ack(m,n-1));
+}
+
+int main(void)
+{
+    int m = 2, n = 1;
+
+    printf("%d\n",ack(m,n));
+
+    return 0;
+}
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/栈/链栈/conversion.c b/c/dataStructure/栈和队列/栈/链栈/conversion.c
new file mode 100755
index 0000000..ebc2161
--- /dev/null
+++ b/c/dataStructure/栈和队列/栈/链栈/conversion.c
@@ -0,0 +1,29 @@
+#include "stack.h"
+
+int main(void)
+{
+    Stack s;
+
+    int number, ans;
+
+    InitStack(&s);
+
+    printf("Please enter a number: ");
+    scanf("%d", &number);
+
+    while (number)
+    {
+        Push(&s, number%2);
+        number /= 2;
+    }
+
+    while (!StackIsEmpty(&s))
+    {
+        printf("%d",GetTop(&s));
+        Pop(&s, &ans);
+    }
+
+    putchar('\n');
+
+    return 0;
+}
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/栈/链栈/main.c b/c/dataStructure/栈和队列/栈/链栈/main.c
new file mode 100755
index 0000000..f211ae4
--- /dev/null
+++ b/c/dataStructure/栈和队列/栈/链栈/main.c
@@ -0,0 +1,21 @@
+#include "stack.h"
+
+int main(void) {
+    Stack s;
+    int p;
+
+    InitStack(&s);
+
+    for (int i = 0; i < 3; i++)
+        Push(&s, i);
+    
+    for (int i = 0; i < 3; i++) {
+        printf("Get top: %d\n",GetTop(&s));
+        Pop(&s,&p);
+        printf("Pop: %d\n",p);
+    }
+
+    DestroyStack(&s);
+
+    return 0;
+}
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/栈/链栈/p_match.c b/c/dataStructure/栈和队列/栈/链栈/p_match.c
new file mode 100755
index 0000000..44efecd
--- /dev/null
+++ b/c/dataStructure/栈和队列/栈/链栈/p_match.c
@@ -0,0 +1,41 @@
+#include "stack.h"
+
+int main(void)
+{
+    ElemType ch;
+    Stack s;
+    ElemType pop, top;
+    bool flag = true;
+
+    InitStack(&s);
+
+    while ((ch = getchar()) != '\n' && flag)
+    {
+        switch (ch)
+        {
+            case '(':   Push(&s,ch);
+                        break;
+            case '[':   Push(&s,ch);
+                        break;
+            case ')':   if (StackIsEmpty(&s) || (top = GetTop(&s)) != '(')
+                            flag = false;
+                        else if (top == '(')
+                            Pop(&s,&pop);
+                        break;
+            case ']':   if (StackIsEmpty(&s) || (top = GetTop(&s)) != '[')
+                            flag = false;
+                        else if (top == '[')
+                            Pop(&s,&pop);
+                        break;
+        }
+    }
+
+    if (StackIsEmpty(&s) && flag)
+        printf("Matching successful!\n\n");
+    else
+    {
+        fprintf(stderr,"Matching failed!\n\n");
+        DestroyStack(&s);
+    }
+    return 0;
+}
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/栈/链栈/palindrome.c b/c/dataStructure/栈和队列/栈/链栈/palindrome.c
new file mode 100755
index 0000000..c8a9a7f
--- /dev/null
+++ b/c/dataStructure/栈和队列/栈/链栈/palindrome.c
@@ -0,0 +1,64 @@
+#include<ctype.h>
+#include "stack.h"
+
+int main(void)
+{
+    ElemType ch,a1,a2;
+    Stack s,p;
+    int size = 0;
+    bool flag = false;
+
+    InitStack(&s);
+    InitStack(&p);
+
+    while ((ch = getchar()) != '\n')
+    {
+        Push(&s,tolower(ch));
+        size++;
+    }
+
+    if (size == 0)
+        return 0;
+    if (size % 2 == 0)
+        flag = true;
+    size /= 2;
+
+    if (!flag)
+        size++;
+
+    for (int i = 0; i < size; i++)
+    {
+        if (flag)
+        {
+            Pop(&s,&ch);
+            Push(&p,ch);
+        }
+        else
+        {
+            if (i == size - 1)
+                ch = GetTop(&s);
+            else
+                Pop(&s,&ch);
+            Push(&p,ch);
+        }
+    }
+
+    while (s)
+    {
+        Pop(&s,&a1);
+        Pop(&p,&a2);
+        if (a1 != a2)
+            break;
+    }
+
+    if (s)
+    {
+        printf("Not palindrome word!\n");
+        DestroyStack(&s);
+        DestroyStack(&p);
+    }
+    else
+        printf("Is palindrome word!\n");
+    
+    return 0;
+}
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/栈/链栈/stack.c b/c/dataStructure/栈和队列/栈/链栈/stack.c
new file mode 100755
index 0000000..e47dd81
--- /dev/null
+++ b/c/dataStructure/栈和队列/栈/链栈/stack.c
@@ -0,0 +1,56 @@
+#include "stack.h"
+
+bool InitStack(Stack * s) {
+    *s = NULL;
+    return true;
+}
+
+bool DestroyStack(Stack * s) {
+    Stack p;
+
+    while (*s) {
+        p = *s;
+        *s = (*s)->next;
+        free (p);
+    }
+    return true;
+}
+
+bool Push(Stack * s, ElemType n) {
+    Stack p = (stack *) malloc (sizeof(stack));
+    if (!p) {
+        fprintf(stderr,"No enough memory\n");
+        return false;
+    }
+    p->data = n;
+    p->next = *s;
+
+    *s = p;
+
+    return true;
+}
+
+bool Pop(Stack * s, ElemType * n) {
+    if (!*s) {
+        fprintf(stderr,"No element in stack!\n");
+        return false;
+    }
+    *n = (*s)->data;
+    Stack p = *s;
+    *s = (*s)->next;
+    free(p);
+
+    return true;
+}
+
+ElemType GetTop(Stack * s) {
+    if (*s)
+        return (*s)->data;
+    return -1;
+}
+
+bool StackIsEmpty (Stack * s) {
+    if (!*s)
+        return true;
+    return false;
+}
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/栈/链栈/stack.h b/c/dataStructure/栈和队列/栈/链栈/stack.h
new file mode 100755
index 0000000..33e9ffe
--- /dev/null
+++ b/c/dataStructure/栈和队列/栈/链栈/stack.h
@@ -0,0 +1,25 @@
+#ifndef _STACK_H
+#define _STACK_H
+
+#include<stdio.h>
+#include<stdlib.h>
+#include<stdbool.h>
+#include"tree.h"
+
+typedef Node * ElemType;
+
+typedef struct stack{
+    ElemType data;
+    struct stack * next;
+} stack;
+
+typedef stack * Stack;
+
+bool InitStack(Stack * s);
+bool DestroyStack(Stack * s);
+bool Push(Stack * s, ElemType n);
+bool Pop(Stack * s, ElemType * n);
+ElemType  GetTop(Stack * s);
+bool StackIsEmpty (Stack * s);
+
+#endif
diff --git a/c/dataStructure/栈和队列/栈/顺序栈/main.c b/c/dataStructure/栈和队列/栈/顺序栈/main.c
new file mode 100755
index 0000000..93fcad8
--- /dev/null
+++ b/c/dataStructure/栈和队列/栈/顺序栈/main.c
@@ -0,0 +1,21 @@
+#include "stack.h"
+
+int main(void) {
+    int p;
+    Stack s;
+
+    InitStack(&s);
+
+    for (int i = 0; i < 8; i++)
+        Push(&s,i);
+    
+    for (int i = 0; i < 8; i++) {
+        printf("Get top: %d\n",GetTop(&s));
+        Pop(&s,&p);
+        printf("Pop: %d\n",p);
+    }
+
+    DestroyStack(&s);
+    
+    return 0;
+}
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/栈/顺序栈/stack.c b/c/dataStructure/栈和队列/栈/顺序栈/stack.c
new file mode 100755
index 0000000..b124e59
--- /dev/null
+++ b/c/dataStructure/栈和队列/栈/顺序栈/stack.c
@@ -0,0 +1,50 @@
+#include "stack.h"
+
+bool InitStack(Stack * s) {
+    s->base = (int *) malloc (sizeof(int) * MAXIMUM);
+
+    if (!s->base) {
+        fprintf(stderr,"Create stack error!\n");
+        return false;
+    }
+    s->top = s->base;
+    s->size = MAXIMUM;
+    
+    return true;
+}
+
+bool DestroyStack(Stack * s) {
+    if (!s->base){
+        fprintf(stderr,"Stack not initialize!\n");
+        return false;
+    }
+    free(s->base);
+
+    return true;
+}
+
+bool Push(Stack * s, int n) {
+    if (s->top - s->base == s->size) {
+        fprintf(stderr,"Stack is full!\n");
+        return false;
+    }
+    *s->top++ = n;  // *s->top = n; *s->top++;
+
+    return true;
+}
+
+bool Pop(Stack * s, int * n) {
+    if (s->top == s->base) {
+        fprintf(stderr,"Empty stack!\n");
+        return false;
+    }
+    *n = *--s->top; // --s->top; *n = *s->top;
+
+    return true;
+}
+
+int GetTop(Stack * s) {
+    if (s->top != s->base)
+        return *(s->top - 1);
+    return -1;
+}
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/栈/顺序栈/stack.h b/c/dataStructure/栈和队列/栈/顺序栈/stack.h
new file mode 100755
index 0000000..2d63452
--- /dev/null
+++ b/c/dataStructure/栈和队列/栈/顺序栈/stack.h
@@ -0,0 +1,23 @@
+#ifndef _STACK_H
+#define _STACK_H
+
+#include<stdio.h>
+#include<stdlib.h>
+#include<stdbool.h>
+
+#define MAXIMUM 5
+#define RESIZE 1
+
+typedef struct stack {
+    int * base;
+    int * top;
+    int size;
+} Stack;
+
+bool InitStack(Stack * s);
+bool DestroyStack(Stack * s);
+bool Push(Stack * s, int n);
+bool Pop(Stack * s, int * n);
+int  GetTop(Stack * s);
+
+#endif
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/队列/循环队列/main.c b/c/dataStructure/栈和队列/队列/循环队列/main.c
new file mode 100755
index 0000000..e69de29
--- /dev/null
+++ b/c/dataStructure/栈和队列/队列/循环队列/main.c
diff --git a/c/dataStructure/栈和队列/队列/循环队列/queue.c b/c/dataStructure/栈和队列/队列/循环队列/queue.c
new file mode 100755
index 0000000..2c7f781
--- /dev/null
+++ b/c/dataStructure/栈和队列/队列/循环队列/queue.c
@@ -0,0 +1,53 @@
+#include "queue.h"
+
+bool InitQueue(Queue * q)
+{
+    q->base = (int *) malloc (sizeof(int) * MAXSIZE);
+    if (!q->base)
+    {
+        fprintf(stderr,"Failed to allocate memory!\n");
+        return false;
+    }
+
+    q->front = q->rear = 0;
+}
+
+bool EnQueue(Queue * q, int e)
+{
+    if ((q->rear + 1)%MAXSIZE == q->front)
+    {
+        fprintf(stderr,"Queue is full!\n");
+        return false;
+    }
+
+    q->base[q->rear] = e;
+    q->rear = (q->rear + 1) % MAXSIZE;
+
+    return true;
+}
+
+bool DeQueue(Queue * q, int * e)
+{
+    if (q->front == q->rear)
+    {
+        fprintf(stderr,"Queue is empty");
+        return false;
+    }
+
+    *e = q->base[q->front];
+    q->front = (q->front + 1) % MAXSIZE;
+
+    return true;
+}
+
+int LengthQueue(Queue * q)
+{
+    return (q->rear - q->front + MAXSIZE) % MAXSIZE;
+}
+
+int GetHead(Queue * q)
+{
+    if (q->front != q->rear)
+        return q->base[q->front];
+    return -1;
+}
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/队列/循环队列/queue.h b/c/dataStructure/栈和队列/队列/循环队列/queue.h
new file mode 100755
index 0000000..11806b5
--- /dev/null
+++ b/c/dataStructure/栈和队列/队列/循环队列/queue.h
@@ -0,0 +1,17 @@
+#include<stdio.h>
+#include<stdlib.h>
+#include<stdbool.h>
+
+#define MAXSIZE 5
+
+typedef struct queue {
+    int * base;
+    int front;
+    int rear;
+} Queue;
+
+bool InitQueue (Queue * q);
+bool EnQueue (Queue * q, int e);
+bool DeQueue (Queue * q, int * e);
+int  LengthQueue (Queue * q);
+int  GetHead (Queue * q);
\ No newline at end of file
diff --git a/c/dataStructure/栈和队列/队列/链队列/main.c b/c/dataStructure/栈和队列/队列/链队列/main.c
new file mode 100755
index 0000000..db5ae9a
--- /dev/null
+++ b/c/dataStructure/栈和队列/队列/链队列/main.c
@@ -0,0 +1,28 @@
+#include "queue.h"
+
+int main(void)
+{
+    ElemType e;
+    pqueue head, tail;
+    InitQueue(&head);
+    InitQueue(&tail);
+
+    while ((e = getchar()) != '\n')
+    {
+        EnQueue(&tail, &e);
+        if (EmptyQueue(&head))
+            head = tail;
+    }
+
+    PrintQueue(&head);
+    ElemType retval;
+
+    DeQueue(&head, &retval);
+    printf("'%c' quit queue\n",retval);
+
+    PrintQueue(&head);
+
+    RsQueue(&head);
+
+    return 0;
+}
diff --git a/c/dataStructure/栈和队列/队列/链队列/queue.c b/c/dataStructure/栈和队列/队列/链队列/queue.c
new file mode 100755
index 0000000..94361d1
--- /dev/null
+++ b/c/dataStructure/栈和队列/队列/链队列/queue.c
@@ -0,0 +1,75 @@
+#include "queue.h"
+
+void InitQueue(pqueue * q)
+{
+    *q = NULL;
+}
+
+bool EmptyQueue(pqueue * qhead)
+{
+    if (!*qhead)
+        return true;
+    return false;
+}
+
+bool EnQueue(pqueue * qtail, ElemType * e)
+{
+    pqueue new = (pqueue) malloc (sizeof(Queue));
+    if (!new)
+        return false;
+    new->data = *e;
+    new->next = NULL;
+
+    if (!*qtail)
+        *qtail = new;
+    else
+    {
+        (*qtail)->next = new;
+        *qtail = new;
+    }
+
+    return true;
+}
+
+bool DeQueue(pqueue * qhead, ElemType * e)
+{
+    pqueue tmp = *qhead;
+    if (!*qhead)
+        return false;
+    *e = tmp->data;
+    *qhead = (*qhead)->next;
+    free(tmp);
+
+    return true;
+}
+
+bool RsQueue (pqueue * qhead)
+{
+    if (EmptyQueue(qhead))
+        return false;
+    pqueue tmp = *qhead;
+
+    while (!*qhead)
+    {
+        tmp = (*qhead)->next;
+        free(*qhead);
+        *qhead = tmp;
+    }
+
+    return true;
+}
+
+bool PrintQueue (pqueue * qhead)
+{
+    if (EmptyQueue(qhead))
+        return false;
+    pqueue tmp = *qhead;
+
+    while (tmp)
+    {
+        printf("%c", tmp->data);
+        tmp = tmp->next;
+    }
+    putchar('\n');
+    return true;
+}
diff --git a/c/dataStructure/栈和队列/队列/链队列/queue.h b/c/dataStructure/栈和队列/队列/链队列/queue.h
new file mode 100755
index 0000000..e444632
--- /dev/null
+++ b/c/dataStructure/栈和队列/队列/链队列/queue.h
@@ -0,0 +1,23 @@
+#ifndef _QUEUE_H
+#define _QUEUE_H
+
+#include<stdio.h>
+#include<stdlib.h>
+#include<stdbool.h>
+
+typedef char ElemType;
+
+typedef struct queue {
+    ElemType data;
+    struct queue * next;
+} Queue;
+typedef Queue * pqueue;
+
+void InitQueue  (pqueue * q);
+bool EnQueue    (pqueue * qtail, ElemType * e);
+bool DeQueue    (pqueue * qhead, ElemType * e);
+bool RsQueue    (pqueue * qhead);
+bool EmptyQueue (pqueue * qhead);
+bool PrintQueue (pqueue * qhead);
+
+#endif