栈和队列的实现

 Lei宝啊：个人主页（也许有你想看的）

愿所有美好不期而遇

---

---

前言 ：

栈和队列的实现与链表的实现很相似，新瓶装旧酒，没什么新东西。

可以参考这篇文章：

-------------------------无头单向不循环链表和带头双向循环链表的创建---------------------------

 

栈

逻辑图： 

 这里我们写顺序栈，不写链栈，因为栈数据的插入只能从栈顶入，栈顶出，这里链栈的优势就没有了，而大多数人所认为的另一个优势是顺序栈容易满？我们难道不能动态开一个，写一个checkcapacity吗，让他满了自动扩容，虽然有空间的损失，但这个并不是什么问题。再一个顺序栈的开辟与释放更为简单，直接释放掉动态开辟的数组空间就好。（当然，链栈也有其优势，但我更认可顺序栈）

头文件： 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int DataType;
typedef struct Stack
{DataType* data;int top;int capacity;
}Stack;void Init(Stack *st);
void Push(Stack* st, DataType x);
void Pop(Stack* st);
DataType GetTop(Stack* st);
bool Empty(Stack* st);
void Destroy(Stack* st);
int Size(Stack* st);

Test文件(main)：

#include "join_stack.h"void Test();int main()
{Test();return 0;
}void Test()
{Stack st;Init(&st);Push(&st, 1);Push(&st, 2);Push(&st, 3);Push(&st, 4);Push(&st, 5);Push(&st, 6);printf("size = %d\n", Size(&st));while (!Empty(&st)){printf("%d ", GetTop(&st));Pop(&st);}putchar('\n');Destroy(&st);
}

函数源文件：

#include "join_stack.h"void Init(Stack* st)
{assert(st);st->data = NULL;st->top = 0;st->capacity = 0;
}void Push(Stack* st, DataType x)
{assert(st);if (st->capacity == st->top){int newcapacity = (st->capacity == 0) ? 4 : st->capacity * 2;DataType* temp = (DataType*)realloc(st->data, sizeof(DataType) * newcapacity);if (temp == NULL){perror("realloc fail");exit(-1);}st->data = temp;st->capacity = newcapacity;}st->data[st->top++] = x;
}void Pop(Stack* st)
{assert(st);assert(st->top > 0);st->top--;
}DataType GetTop(Stack* st)
{assert(st);assert(st->top > 0);return st->data[st->top - 1];
}bool Empty(Stack* st)
{assert(st);return (st->top == 0);
}void Destroy(Stack* st)
{assert(st);free(st->data);st->data = NULL;st->top = st->capacity = 0;}int Size(Stack* st)
{assert(st);return st->top;
}

---

---

 

队列 

逻辑图：

队列我们就用链式结构，这和链表非常像，只是不能在中间插入，而且只能尾进头出。 

头文件：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int DataType;
typedef struct Queue
{DataType data;struct Queue *next;
}Queue;typedef struct Q
{Queue* head;Queue* tail;int size;
}Q;void Init(Q *qq);
void Destroy(Q* qq);
void QueuePush(Q* qq, DataType x);
void QueuePop(Q* qq);
DataType GetQueueFrontNum(Q* qq);
DataType GetQueueBackNum(Q* qq);
bool Empty(Q* qq);
int Size(Q* qq);

 Test文件(main):

#define _CRT_SECURE_NO_WARNINGS 1
#include "newQueue.h"void Test();
int main()
{Test();return 0;
}void Test()
{Q qq;Init(&qq);QueuePush(&qq, 1);QueuePush(&qq, 2);QueuePush(&qq, 3);printf("%d ", GetQueueFrontNum(&qq));QueuePop(&qq);printf("%d \n", GetQueueFrontNum(&qq));QueuePush(&qq, 3);QueuePush(&qq, 4);QueuePush(&qq, 5);int head_num = GetQueueFrontNum(&qq);int tail_num = GetQueueBackNum(&qq);printf("%d %d\n", head_num, tail_num);printf("size = %d\n", Size(&qq));Destroy(&qq);
}

函数源文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "newQueue.h"void Init(Q* qq)
{assert(qq);qq->head = NULL;qq->tail = NULL;qq->size = 0;
}void QueuePush(Q* qq, DataType x)
{assert(qq);Queue* temp = (Queue*)malloc(sizeof(Queue));if (temp == NULL){perror("malloc fail");exit(-1);}temp->data = x;temp->next = NULL;if (qq->tail == NULL)qq->head = qq->tail = temp;else{qq->tail->next = temp;qq->tail = temp;}qq->size++;
}void QueuePop(Q* qq)
{assert(qq);assert(!Empty(qq));if (qq->head == qq->tail){free(qq->head);qq->head = qq->tail = NULL;}else{Queue* next = qq->head->next;free(qq->head);qq->head = next;}qq->size--;
}DataType GetQueueFrontNum(Q* qq)
{assert(qq);assert(!Empty(qq));return qq->head->data;
}DataType GetQueueBackNum(Q* qq)
{assert(qq);assert(!Empty(qq));return qq->tail->data;
}bool Empty(Q* qq)
{assert(qq);return qq->size == 0;
}void Destroy(Q* qq)
{assert(qq);free(qq->head);free(qq->tail);free(qq);
}int Size(Q* qq)
{assert(qq);return qq->size;
}