![[C基础]栈、单向链表和队列的简易C实现](http://www.mshxw.com/aiimages/31/779330.png "[C基础]栈、单向链表和队列的简易C实现")
C语言比较偏底层，很多常用的数据结构需要自己实现，不像高等语言直接就有现成的类库可使用。
1. 栈定义和实现下面是一个栈的简易实现，适合新人入门参考。可以方便的对任意数据类型进行压栈出栈操作。
#define MAX_STACK_DEPTH 4096
typedef struct _STACK
{
void *Array[MAX_STACK_DEPTH];
int Depth;
void (*Push)(struct _STACK *,void *);
void *(*Pop)(struct _STACK *);
}
STACK;
void StackPush(STACK *Stack, void *Element)
{
if (Stack->Depth < MAX_STACK_DEPTH)
{
Stack->Array[Stack->Depth++] = Element;
}
}
void *StackPop(STACK *Stack)
{
if (Stack->Depth <= 0)
{
return NULL;
}
return Stack->Array[--Stack->Depth];
}
注意：
为了简单，我们没有考虑栈溢出情况。如果使用环境可能存在压栈溢出。我们需要改进StackPush函数，增加溢出判断。
int StackPush(STACK *Stack, void *Element)
{
if (Stack->Depth >= MAX_STACK_DEPTH)
{
return -1;
}
Stack->Array[Stack->Depth++] = Element;
return 0;
}
2. 单向链表定义和实现
单向链表在实际使用中非常常见，下面是其定义和实现，包含了用来验证的创建、释放、打印函数。
typedef struct _NODE
{
struct _NODE *Next;
int Value;
}
NODE;
void ListPrint(NODE *Head)
{
while (Head)
{
printf("%d ", Head->Value);
Head = Head->Next;
}
printf("n");
}
void ListFree(NODE *Head)
{
NODE *tmp = NULL;
while (Head)
{
tmp = Head->Next;
free(Head);
Head = tmp;
}
}
NODE *ListCreate(void)
{
NODE *head = NULL, *lastNode = NULL, *curNode = NULL;
int val = 0;
printf("please input space-separated elements:n");
while (scanf("%d", &val) != EOF)
{
curNode = (NODE *)malloc(sizeof(NODE));
if (curNode == NULL)
{
return head;
}
curNode->Value = val;
curNode->Next = NULL;
if (head == NULL)
{
head = curNode;
}
if (lastNode == NULL)
{
lastNode = curNode;
}
else
{
lastNode->Next = curNode;
lastNode = curNode;
}
if (getchar() == 'n')
{
break;
}
}
return head;
}
栈和链表综合使用示例--单向链表的反转：
通常我们使用多个指针逐步实现链表反转，但是栈天生就具备反转特性，所以使用栈来实现更简洁一些。
NODE *ListReverse(NODE *Head)
{
NODE *curNode = NULL;
STACK stack = {.Depth = 0, .Push = StackPush, .Pop = StackPop};
if (Head == NULL)
{
return NULL;
}
while (Head)
{
stack.Push(&stack, (void *)Head);
Head = Head->Next;
}
Head = (NODE *)stack.Pop(&stack);
curNode = Head;
while (stack.Depth > 0)
{
curNode->Next = (NODE *)stack.Pop(&stack);
curNode = curNode->Next;
}
curNode->Next = NULL;
return Head;
}
完整示例代码：
#include3. 队列定义和实现#include #include #define MAX_STACK_DEPTH 4096 typedef struct _STACK { void *Array[MAX_STACK_DEPTH]; int Depth; void (*Push)(struct _STACK *,void *); void *(*Pop)(struct _STACK *); } STACK; void StackPush(STACK *Stack, void *Element) { if (Stack->Depth < MAX_STACK_DEPTH) { Stack->Array[Stack->Depth++] = Element; } } void *StackPop(STACK *Stack) { if (Stack->Depth <= 0) { return NULL; } return Stack->Array[--Stack->Depth]; } typedef struct _NODE { struct _NODE *Next; int Value; } NODE; void ListPrint(NODE *Head) { while (Head) { printf("%d ", Head->Value); Head = Head->Next; } printf("n"); } void ListFree(NODE *Head) { NODE *tmp = NULL; while (Head) { tmp = Head->Next; free(Head); Head = tmp; } } NODE *ListCreate(void) { NODE *head = NULL, *lastNode = NULL, *curNode = NULL; int val = 0; printf("please input space-separated elements:n"); while (scanf("%d", &val) != EOF) { curNode = (NODE *)malloc(sizeof(NODE)); if (curNode == NULL) { return head; } curNode->Value = val; curNode->Next = NULL; if (head == NULL) { head = curNode; } if (lastNode == NULL) { lastNode = curNode; } else { lastNode->Next = curNode; lastNode = curNode; } if (getchar() == 'n') { break; } } return head; } NODE *ListReverse(NODE *Head) { NODE *curNode = NULL; STACK stack = {.Depth = 0, .Push = StackPush, .Pop = StackPop}; if (Head == NULL) { return NULL; } while (Head) { stack.Push(&stack, (void *)Head); Head = Head->Next; } Head = (NODE *)stack.Pop(&stack); curNode = Head; while (stack.Depth > 0) { curNode->Next = (NODE *)stack.Pop(&stack); curNode = curNode->Next; } curNode->Next = NULL; return Head; } int main(int argc, char *argv[]) { NODE *list = NULL; list = ListCreate(); ListPrint(list); list = ListReverse(list); ListPrint(list); ListFree(list); return 0; }
下面是一个队列的建议实现，遵循先进先出原则，从队头Pop弹出元素，从队尾Push压入元素。
#define MAX_QUEUE_LENGTH 4096
typedef struct _QUEUE
{
void *Array[MAX_QUEUE_LENGTH];
int Length;
int Head;
int Tail;
void (*Push)(struct _QUEUE *, void *);
void *(*Pop)(struct _QUEUE *);
}
QUEUE;
void QueuePush(QUEUE *Queue, void *Element)
{
if (Queue->Length >= MAX_QUEUE_LENGTH)
{
return;
}
Queue->Array[Queue->Tail] = Element;
if (Queue->Tail < MAX_QUEUE_LENGTH - 1)
{
Queue->Tail++;
}
else
{
Queue->Tail = 0;
}
Queue->Length++;
}
void *QueuePop(QUEUE *Queue)
{
void *ele = NULL;
if (Queue->Length <= 0)
{
return NULL;
}
ele = Queue->Array[Queue->Head];
if (Queue->Head < MAX_QUEUE_LENGTH - 1)
{
Queue->Head++;
}
else
{
Queue->Head = 0;
}
Queue->Length--;
return ele;
}
注意：
为了简单，我们没有考虑队列溢出情况。如果使用环境可能存在队列溢出。我们需要改进QueuePush函数，增加溢出判断。
int QueuePush(QUEUE *Queue, void *Element)
{
if (Queue->Length >= MAX_QUEUE_LENGTH)
{
return -1;
}
Queue->Array[Queue->Tail] = Element;
if (Queue->Tail < MAX_QUEUE_LENGTH - 1)
{
Queue->Tail++;
}
else
{
Queue->Tail = 0;
}
Queue->Length++;
return 0;
}
队列和栈的示例--两个队列实现栈：
typedef struct _QUEUE_STACK
{
QUEUE Queue1;
QUEUE Queue2;
}
QUEUE_STACK;
int QueueStackDepth(QUEUE_STACK *Stack)
{
if (Stack->Queue1.Length == 0 && Stack->Queue2.Length == 0)
{
return 0;
}
else if (Stack->Queue1.Length == 0)
{
return Stack->Queue2.Length;
}
else
{
return Stack->Queue1.Length;
}
}
void QueueStackPush(QUEUE_STACK *Stack, void *Element)
{
if (Stack->Queue1.Length > 0)
{
Stack->Queue1.Push(&Stack->Queue1, Element);
}
else
{
Stack->Queue2.Push(&Stack->Queue2, Element);
}
}
void *QueueStackPop(QUEUE_STACK *Stack)
{
QUEUE *popQueue = NULL, *pushQueue = NULL;
void *ele = NULL;
if (Stack->Queue1.Length == 0 && Stack->Queue2.Length == 0)
{
return NULL;
}
else if (Stack->Queue1.Length == 0)
{
pushQueue = &Stack->Queue1;
popQueue = &Stack->Queue2;
}
else
{
pushQueue = &Stack->Queue2;
popQueue = &Stack->Queue1;
}
while (popQueue->Length > 1)
{
ele = popQueue->Pop(popQueue);
pushQueue->Push(pushQueue, ele)
}
return popQueue->Pop(popQueue);
}
完整示例代码如下，直接gcc编译执行：
#include#include #include #define MAX_QUEUE_LENGTH 4096 typedef struct _QUEUE { void *Array[MAX_QUEUE_LENGTH]; int Length; int Head; int Tail; void (*Push)(struct _QUEUE *, void *); void *(*Pop)(struct _QUEUE *); } QUEUE; void QueuePush(QUEUE *Queue, void *Element) { if (Queue->Length >= MAX_QUEUE_LENGTH) { return; } Queue->Array[Queue->Tail] = Element; if (Queue->Tail < MAX_QUEUE_LENGTH - 1) { Queue->Tail++; } else { Queue->Tail = 0; } Queue->Length++; } void *QueuePop(QUEUE *Queue) { void *ele = NULL; if (Queue->Length <= 0) { return NULL; } ele = Queue->Array[Queue->Head]; if (Queue->Head < MAX_QUEUE_LENGTH - 1) { Queue->Head++; } else { Queue->Head = 0; } Queue->Length--; return ele; } typedef struct _QUEUE_STACK { QUEUE Queue1; QUEUE Queue2; } QUEUE_STACK; int QueueStackDepth(QUEUE_STACK *Stack) { if (Stack->Queue1.Length == 0 && Stack->Queue2.Length == 0) { return 0; } else if (Stack->Queue1.Length == 0) { return Stack->Queue2.Length; } else { return Stack->Queue1.Length; } } void QueueStackPush(QUEUE_STACK *Stack, void *Element) { if (Stack->Queue1.Length > 0) { Stack->Queue1.Push(&Stack->Queue1, Element); } else { Stack->Queue2.Push(&Stack->Queue2, Element); } } void *QueueStackPop(QUEUE_STACK *Stack) { QUEUE *popQueue = NULL, *pushQueue = NULL; void *ele = NULL; if (Stack->Queue1.Length == 0 && Stack->Queue2.Length == 0) { return NULL; } else if (Stack->Queue1.Length == 0) { pushQueue = &Stack->Queue1; popQueue = &Stack->Queue2; } else { pushQueue = &Stack->Queue2; popQueue = &Stack->Queue1; } while (popQueue->Length > 1) { ele = popQueue->Pop(popQueue); pushQueue->Push(pushQueue, ele); } return popQueue->Pop(popQueue); } int main(int argc, char *argv[]) { QUEUE_STACK stack; int val = 0; stack.Queue1.Push = QueuePush; stack.Queue1.Pop = QueuePop; stack.Queue1.Length = stack.Queue1.Head = stack.Queue1.Tail = 0; stack.Queue2.Push = QueuePush; stack.Queue2.Pop = QueuePop; stack.Queue2.Length = stack.Queue2.Head = stack.Queue2.Tail = 0; printf("please input space-separated elements:n") while (scanf("%d", &val) != EOF) { QueueStackPush(&stack, (void *)val); if (getchar() == 'n') { break; } } while (QueueStackDepth(&stack) > 0) { val = (int)QueueStackPop(&stack); printf("%d ", val); } printf("n"); return 0; }
