【算法设计-链栈和链队列】链栈和链队列的实现

1.链队列。利用带有头结点的单链表来实现链队列,插入和删除的复杂度都为o(1)

代码：

#include<stdio.h>
#include<stdlib.h>
typedef struct Qnode
{
 int data;
 Qnode *next;
}Qnode;
typedef struct LinkQueue
{
Qnode *front;
Qnode *rear;
}LinkQueue;
void initialize(LinkQueue *LinkQueue)
{
LinkQueue->rear=(Qnode*)malloc(sizeof(Qnode));
LinkQueue->front=LinkQueue->rear;
LinkQueue->front->next=NULL;
}
void ENQUEUE(LinkQueue *LinkQueue)
{
Qnode* temp=(Qnode *)malloc(sizeof(Qnode));
printf("插入的数值?\n");
scanf("%d",&temp->data);
temp->next=NULL;
LinkQueue->rear->next=temp;
LinkQueue->rear=temp;
}
void show_queue(LinkQueue *LinkQueue1)
{
Qnode *temp=LinkQueue1->front;
while(temp->next!=NULL)
{
printf("%d,",temp->next->data);
temp=temp->next;
}
printf("\n");


}
void DEQUEUE(LinkQueue *LinkQueue)
{
printf("要删除队列的第一个结点%d\n",LinkQueue->front->next->data);
Qnode *temp=LinkQueue->front;
LinkQueue->front=temp->next;
free(temp);
}
int main(void)
{
LinkQueue *LinkQueue1;
LinkQueue1=(LinkQueue *)malloc(sizeof(LinkQueue));
initialize(LinkQueue1);
ENQUEUE(LinkQueue1);
ENQUEUE(LinkQueue1);
ENQUEUE(LinkQueue1);
show_queue(LinkQueue1);
DEQUEUE(LinkQueue1);
show_queue(LinkQueue1);
DEQUEUE(LinkQueue1);
show_queue(LinkQueue1);
DEQUEUE(LinkQueue1);
return 0;
}

结果展示：

2.链栈的实现

利用含有头结点的单链表来实现,插入和删除的复杂度都为o(1)

#include<stdio.h>
#include<stdlib.h>
typedef long ElemType;
typedef struct stack
{
ElemType data;
struct stack* next;
}STACK;
void initialize(STACK*);
void add(STACK*);
void delete_s(STACK*);
void get_top(STACK*);
void initialize(STACK* top)
{
top->next = NULL;//这里的top就相当于一个头结点指针。这个是头节点！！！！
}
void add(STACK* top)
{
ElemType m;
puts("请问您想插入的数字是?\n");
scanf("%d", &m);
STACK* temp;
temp = (STACK*)malloc(sizeof(STACK));
temp->data = m;
temp->next = top->next;
top->next = temp;
}
void delete_s(STACK* top)
{
ElemType value;
STACK* temp;
temp = top->next;
value = top->next->data;
top->next = temp->next;
free(temp);
printf("删除了%d\n",value);
}
void get_top(STACK* top)
{
printf("栈顶是%d",top->next->data);
}
int main(void)
{
STACK top;
initialize(&top);
int choice;
while (1)//注意因为下面利用了switch所以不能应用c primer plus第八章中的getchar()与scanf组合的方法。
{
printf("按下列选项选择您要进行的操作\n");
printf("1.添加数字\n");
printf("2.删除数字\n");
printf("3.显示栈顶\n");
printf("4.退出\n");
scanf_s("%d",&choice);
switch (choice)
{
case 1:
add(&top); break;
case 2:
delete_s(&top); break;
case 3:
get_top(&top); break;
case 4:
return 0;
default:
break;
}




}
printf("谢谢您的使用!\n");
}