分别用数组和链表实现栈和队列

2015.2.8
星期二,晴天

栈的数组操作:

栈的特点:先进后出,后进先出。

用数组的方式实现:首先需要创建一个结构体,在结构体里面包括数据指针、指向栈顶的”指针“和标记栈的大小的一个变量。数据指针是指向一定大小的数组的首地址。结构体和这个
数组够成一个完整的栈。

1.在创建栈的操作中,主要就是创建这个结构体和这个数组,并对其进行一定的初始化,这个操作和链表的创建比较类似,初始化的语句:
stack->max_depth = max_depth; //说明栈的大小
stack->pop = -1; //说明现在的栈是一个空栈

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;

typedef struct stack{ //创建一个结构体
data_t *data;
int pop;
int max_depth;
} sqstack_t;

sqsatck_t * Create_Empty_Sqstack(int max_depth)
{
sqstack_t *stack;
stack = (sqstack_t *)malloc(sizeof(sqstack_t)); //先创建栈
if(stack)
{
stack->data = (data_t *)malloc(sizeof(data_t) * max_depth); //创建数组,注意数组大小的算法
if(stack->data == NULL)
{
free(stack);
return NULL;
}
}

stack->max_depth = max_depth; //对栈的初始化操作
stack->pop = -1;

return stack;

}

void Destory_Sqstack(sqstack_t stack) //销毁一个栈,应为不是链表,所以不需要一个个释放数组中每个数据的内存,将指向内存的指针释放就行了
{
if(stack)
{
if(stack->data)
{
free(stack->data); //释放数组
stack->data = NULL;
}
free(stack); //释放结构体,此时整个栈就销毁了
stack = NULL;
return ;
}
}

void Clear_Sqstack(sqstack_t stack) //清空栈,同样不不用一个个清除,直接对栈顶指针进行操作就行了
{
if(stack == NULL)
{
return -1;
}

stack->pop = -1; //将栈顶指针指向空,表明此时的栈已经清空

return;
}
int Empty_Sqstack(sqstack_t stack) //判断栈是否为空,只需要查寻栈顶指针就行了
{
if(stack == NULL)
{
return -1;
}

return(stack->pop == -1 ? 1 : 0); //判断栈顶指针是否指向空

}
int Full_Sqstack(sqstack_t stack) //判断栈是否已经满了,只需要查寻栈顶指针是否和栈的长度长度相等就行了
{
if(stack == NULL)
{
return -1;
}
return(stack->pop + 1 == max_depth ? 1 : 0); // 查寻栈顶指针是否和栈的长度长度相等
}

int Push_Sqstack(sqstack_t stack,data_t x) //主要的操作来了,压栈,应为栈顶指针始终指向栈顶的数据,所以,压入数据之前需要移动栈顶指针,
{ 否则会覆盖原先的数据
if(Full_Sqstack(stack))
{
return -1;
}

stack->pop++; //移动栈顶指针
stack->data[stack->pop] = x; //压榨

return 0;
}
int Pop_Sqstack(sqstack_t stack,data_t *x) //也是主要操作,出栈,应为栈顶指针始终指向栈顶的数据,在出栈之前不需要对栈顶指针进行操作,但是
{ 出栈后需要将修改栈顶指针的位置,以便下次对栈进行操作
if(Empty_Sqstack(stack))
{
return -1;
}

if(x)
{
*x = stack->data[stack->pop]; //出栈
stack->pop--; //修改栈顶指针
return 0;
}
else
{
return -1;
}


}
int Get_Sqstack_Pop(sqstack_t stack,data_t *x) //取得栈顶的数据,这个功能只是取的栈顶的数据,所以,没有修改栈顶指针
{
if(Empty_Sqstack(stack))
{
return -1;
}

if(x)
{
*x = stack->data[stack->pop];
return 0;
}
else
{
return -1;
}
}


栈的链表操作:

链表实现的方式和单链表的很多操作都有相似之处,特别是在创建,初始化,清空栈的时候需要一个个清除链表中的数据,出栈时的销毁动作等都很类似

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;

typedef struct Lstack{ //创建一个简单的结构体
data_t data;
struct Lstack *next;
}linkstack_t;

linkstack_t * Create_Empty_Linkstack(int max_depth)
{
linkstack_t *stack;
stack = (linkstack_t *)malloc(sizeof(linkstack_t));
if(stack)
{
stack->next = NULL; //初始化栈顶,也就是表头
}

return stack;
}

void Clear_Linkstack(linkstack_t stack)
{
linkstack_t *node;
if(stack == NULL)
{
return -1;
}

if(NULL != stack->next) //清空操作,一个个清空内存,用到了标记指针
{
node = stack->next;
stack->next = node->next;
free(node);
}
return;
}

void Destory_Linkstack(linkstack_t stack) //销毁操作,大原则:先清空,后销毁(呵呵,貌似很环保)
{
if(stack)
{
Clear_Linkstack(stack);
free(stack);
stack = NULL;
}
}

int Empty_Linkstack(linkstack_t stack) //判断是否为空,只需要查寻表头指针就行了(备注一下,这里没有写判断栈满的函数,应为链表可以不断生长,所有不会满)
{
if(stack )
{
return (stack->next == NULL ? 1 : 0); //查寻表头指针是否指向空
}
else
{
return -1;
}
}

int Push_Linkstack(linkstack_t stack,data_t x) //压栈操作,始终将数据放到表头所指向的位置就行了,很简单
{
linkstack_t *node;

if(stack == NULL)
{
return -1;
}

node = (linkstack_t *)malloc(sizeof(linkstack_t));
if(node == NULL)
{
return -1;
}
node->data = x;

node->next = stack->next; //插入的操作
stack->next = node;

return 0;
}

int Pop_Linkstack(linkstaxk_t stack,data_t *x) //出栈的操作,出栈前需要判断栈是否空了,以免误操作,出栈后需要将栈顶的那个数据释放掉,所以,
{ 需要有个标志指针标记处需要释放的结构体,
linkstack_t *node;

if(stack == NULL || stack->next == NULL )
{
return -1;
}
node = stack->next; //对标记指针的操作
stack->next = node->next;

if(x)
{
*x = node->data;
}

free(node);

return 0;

}

int Get_Linkstack_Pop(linkstack_t stack,data_t *x) //取得栈顶的数据,这个时候只是取,不释放
{
if(stack == NULL || stack->next == NULL)
{
return -1;
}

*x = stack->next->data;

return 0;


}

队列的数组实现:

队列的特点:先进先出,后进后出

数组的方式实现:首先需要明确数组长度,这样标志队首和对尾的指针就能操作这个数组了,这里利用的是循环数组的方式,所以实际的数组长度等于存放的数据长度+1;
这里用到的两个重要的公式,分别对队首和队尾操作的:

queue->rear= (queue->rear+ 1) % N; //取队首的数据
queue->rear= (queue->rear+ 1) % N; //向队尾插入数据

queue->front == queue->rear //空栈的判断条件
queue->front == (queue->rear + 1) % N //满栈的判断条件


#include <stdio.h>
#include <stdlib.h>

#define FIFO_LEN 9 //存放数据的个数
#define N (FIFO_LEN + 1) //数组的实际长度

typedef int data_t;
typedef struct{
data_t data[N];
int front;
int rear;
}sequeue_t;

sequeue_t *Create_Empty_Queue() //创建一个空队列,这时需要的初始化操作是将队首和队尾的指针都指向标记位,空栈是0
{
sequeue_t *queue;
queue = (sequeue_t *)malloc(sizeof(sequeue_t));
if(queue == NULL)
{
return NULL;
}

queue->front = queue->rear = 0; //初始化队首和队尾指针
return queue;
}

void Destory_Queue(sequeue_t *queue) //销毁队列,直接释放结构体指针指向的内存就行了
{
if(queue)
{
free(queue);
}
}

int Empty_Queue(sequeue_t *queue) //判断队列是否为空,主要就是查寻队首和队尾的指针并进行比较
{
if(queue == NULL)
{
return -1;
}

return (queue->front == queue->rear ? 1 : 0); //空队列的比较比较公式
}

int Full_Queue(sequeue_t *queue) //判断队列是否已满
{
if(queue == NULL)
{
return -1;
}

return ((queue->rear + 1) % N == queue->front ? 1 : 0); //满队列的比较公式
}

int Clear_Queue(sequeue_t *queue) //清空队列的操作,主要就是讲队首和队尾的指针指向空栈的标志位就好了
{
if(queue == NULL)
{
return -1;
}
queue->front = queue->rear = 0; //清空操作,和初始化一样
return 0;
}

int En_Queue(sequeue_t *queue,data_t x) //向队列的尾插入一个数组,首先需要判断队列是否已满,然后在根据条件插入数据
{
if(queue == NULL || Full_Queue(queue) == 1)
{
return -1;
}

queue->rear= (queue->rear+ 1) % N; //将队尾指针修改为需要插入数据的位置,然后再插入数据
queue->data[queue->rear] = x;
return 0;

}

int De_Queue(sequeue_t *queue, data_t *x) //去出对首的数据,首先需要判空,因为数据时存放在数组里,后面插入数据的时候可以直接覆盖,所以不需要进行清除操作
{
if(queue == NULL || Empty_Queue(queue)== 1)
{
return -1;
}

queue->front= (queue->front+ 1) % N; //修改队首指针,使其指向将要获取的数据
if(x)
{
*x = queue->data[queue->front] //取数据
}

return 0;
}


链表实现的队列:

链表实现队列的操作:这里将队首和队尾的指针封装在一个结构体里面,操作这个两个指针的方式和稍有不同,特别是在创建空队列的时候,不是对链表的数据结构体进行操作,
而是对这两个指针进行相应的操作,多体会体会。

#include <stdio.h>
#include <stdlib.h>

typedef int data_t;
typedef struct Lqueue{
data_t data;
struct Lqueue *next;
}queuenode_t,*queuelist_t;

typedef struct{
queuelist_t front,rear;
}linkqueue;

queue_link *Create_Empty_Linkqueue() //创建空队列:创建封装了指针的结构体,然后对这个两个指针进行初始化操作
{
linkqueue *queue;

queue = (linkqueue *)malloc(sizeof(linkqueue)); //创建队列的表头
if(queue == NULL)
{
return NULL;
}
queue->rear = queue->front = NULL; //初始化表头
return queue;
}

void Clear_Linkqueue(linkqueue *queue) //清空队里,链表实现的队列需要一个个清空,这里的的队首指针始终指向第一个数据结构体
{
queuelist_t node_free;

if(queue == NULL)
{
return -1;
}

while(queue->front != NULL)
{
node_free = queue->front;
queue->front = node->free->next;
free(node_free);
}

return ;


}

void Destory_Linkqueue(sequeue_t * queue) //销毁队列:大原则,先清空,后销毁
{
if(queue)
{
Clear_Linkqueue(queue);
free(queue);
}
}

int Empty_Linkqueue(linkqueue *queue) //判断队列是否为空,只要查寻对首指针是否为空就行了
{
if(queue == NULL)
{
return -1;
}
return(queue->front == NULL ? 1 : 0);
}

int En_Linkqueue(linkqueue *queue,data_t x) //向队列中插入数据,此时分两种情况,需要判断原先队列中是否存在数据,然后根据不同的情况进行不同的插入操作
{ 这里要注意:插入数据后需要相应的修改队尾指针,第一次插入数据时还需要修改对首指针。
queuelist_t node_new;

if(queue == NULL)
{
return -1;
}

node_new = (queuelist_t)malloc(sizeof(queuenode_t));

if(node_new == NULL)
{
return -1;
}

node_new->data = x;
node_new->next = NULL;

if(queue->front == NULL) //队列中原先没有数据
{
queue->front = queue->rear = node_new;
}
else //队列中原先已有数据
{
queue->rear->next = node_new; //插入数据到队列尾
queue->rear = node_new; //修改队尾指针,指向最后插入的数据
}

return 0;
}

int De_Linkqueue(linkqueue *queue,data_t *x) //从队列中取数据:根据取数据后队列是否为空分为两种操作,分别修改队首或者对首指针!!!
{
queuelist_t node_remove;
if(queue == NULL || queue->front == NULL)
{
return -1;
}

node_remove = queue->fornt;
queue->front = node_remove->next;

if(queue->front == NULL) //取完数据后队列为空队列,需要修改对尾指针
{
queue->rear = NULL; //需要修改对尾指针
}

if(x)
{
*x = node_remove->data;
}

free(node_remove);

return 0;
}

原文地址:https://www.cnblogs.com/cnlg/p/4280658.html