栈的链表实现栈的链表实现|数据结构

除了使用数组, 我们还可以使用链表来实现堆栈。链表动态分配内存。但是, 对于所有操作（即推, 弹出和查看）, 两种情况下的时间复杂度都是相同的。
在堆栈的链表实现中, 节点不连续地保存在内存中。每个节点在堆栈中都包含一个指向其直接后继节点的指针。如果内存堆中剩余的空间不足以创建节点, 则称堆栈溢出。

文章图片
堆栈中最顶层的节点在其地址字段中始终包含null。让我们讨论在堆栈的链表实现中执行每个操作的方式。
将节点添加到堆栈（推送操作）将节点添加到堆栈称为推入操作。在链表实现中将元素推送到堆栈与数组实现不同。为了将元素推入堆栈, 需要执行以下步骤。

首先创建一个节点并为其分配内存。
如果列表为空, 则将该项目作为列表的起始节点进行推送。这包括将值分配给节点的数据部分, 并将null分配给节点的地址部分。
如果列表中已经有一些节点, 那么我们必须在列表的开头添加新元素（以免违反堆栈的属性）。为此, 请将起始元素的地址分配给新节点的地址字段, 并使新节点成为列表的起始节点。

检查下溢条件：当我们尝试从已经空的堆栈中弹出时, 发生下溢条件。如果列表的头指针指向空, 则堆栈将为空。
相应地调整头指针：在堆栈中, 仅从一端弹出元素, 因此, 必须删除头指针中存储的值, 并且必须释放节点。头节点的下一个节点现在成为头节点。

【栈的链表实现】

将头指针复制到一个临时指针。
在列表的所有节点之间移动临时指针, 并打印附加到每个节点的value字段。

#include <
stdio.h>
#include <
stdlib.h>
void push();
void pop();
void display();
struct node {int val;
struct node *next;
};
struct node *head;
void main (){	int choice=0;
		printf(“
\n*********Stack operations using linked list*********\n”
);
	printf(“
\n—
—
—
—
—
—
—
—
—
—
—
—
—
—
—
-\n”
);
	while(choice != 4)	{printf(“
\n\nChose one from the below options…
\n”
);
printf(“
\n1.Push\n2.Pop\n3.Show\n4.Exit”
);
printf(“
\n Enter your choice \n”
);
scanf(“
%d”
, &
choice);
switch(choice){case 1:{ push();
break;
}case 2:{pop();
break;
}case 3:{display();
break;
}case 4: {printf(“
Exiting…
.”
);
break;
 }default:{printf(“
Please Enter valid choice “
);
} 	};
}}void push (){	int val;
	struct node *ptr = (struct node*)malloc(sizeof(struct node));
 	if(ptr == NULL)	{printf(“
not able to push the element”
);
		}	else 	{printf(“
Enter the value”
);
scanf(“
%d”
, &
val);
if(head==NULL){ptr->
val = val;
ptr ->
 next = NULL;
head=ptr;
} else {ptr->
val = val;
ptr->
next = head;
head=ptr;
}printf(“
Item pushed”
);
	}}void pop(){	int item;
	struct node *ptr;
	if (head == NULL)	{printf(“
Underflow”
);
	}	else	{item = head->
val;
ptr = head;
head = head->
next;
free(ptr);
printf(“
Item popped”
);
	}}void display(){	int i;
	struct node *ptr;
	ptr=head;
	if(ptr == NULL)	{printf(“
Stack is empty\n”
);
	}	else	{printf(“
Printing Stack elements \n”
);
while(ptr!=NULL){printf(“
%d\n”
, ptr->
val);
ptr = ptr->
next;
}	}}