链表实现的堆栈

除了使用数组，我们还可以使用链表来实现堆栈。链表动态分配内存。然而，在这两种情况下，所有操作(如push, pop和peek)的时间复杂度是相同的。

在栈的链表实现中，节点是在内存中不连续维护的。每个节点都包含一个指向堆栈中其直接后继节点的指针。如果内存堆中剩余的空间不足以创建节点，则堆栈被溢出。

堆栈中最顶端的节点在其地址字段中总是包含null。我们来讨论一下，每个操作都是在栈的链表实现中执行的。

向栈中添加节点(Push操作)

将节点添加到堆栈中称为推操作。在链表实现中，将元素压入堆栈与在数组实现中不同。为了将一个元素压入堆栈，需要执行以下步骤。

1. 首先创建一个节点并为其分配内存。
2. 如果列表为空，则将该项目作为列表的开始节点推入。这包括为节点的数据部分赋值，并为节点的地址部分赋空。
3. 如果列表中已经有一些节点，那么我们必须在列表的开头添加新元素(为了不违反堆栈的属性)。为此，将起始元素的地址分配给新节点的地址字段，并使新节点成为列表的起始节点。

时间复杂度:0 (1)





C实现:

Void push () {int val;Struct node* ptr =(Struct node*)malloc(sizeof(Struct node));if(ptr == NULL) {printf("不能压入元素");} else {printf("输入值");scanf(“% d”,val);if(head==NULL) {ptr->val = val;ptr -> next = NULL;头= ptr;} else {ptr->val = val;Ptr ->下一个=头部; head=ptr; } printf("Item pushed"); } }

从堆栈中删除一个节点(POP操作)

从栈顶删除一个节点称为流行操作。从stack的链表实现中删除节点与在数组实现中删除节点不同。为了从堆栈中弹出一个元素，我们需要遵循以下步骤:

1. 检查下溢情况:当我们试图从已经空的堆栈弹出时，就会发生下流情况。如果列表的头指针指向空，则堆栈将为空。
2. 相应地调整头部指针:在堆栈中，元素只从一端弹出，因此，必须删除存储在头指针中的值，并且必须释放节点。头节点的下一个节点现在成为头节点。

时间复杂度:0 (n)

C实现

Void pop() {int item;Struct node *ptr;if (head == NULL) {printf("Underflow");} else {item = head->val;PTR =头部;Head = Head ->next;免费(ptr);printf("项破灭”);}}

显示节点(遍历)

显示堆栈的所有节点需要遍历以堆栈形式组织的链表的所有节点。为此，我们需要遵循以下步骤。

1. 将头指针复制到临时指针中。
2. 将临时指针移动到列表的所有节点，并打印附加到每个节点的值字段。

时间复杂度:0 (n)

C实现

无效显示(){int i;Struct node *ptr;ptr =头;if(ptr == NULL) {printf("堆栈为空\n");} else {printf("打印堆栈元素\n");while(ptr!=NULL) {printf("%d\n"，ptr->val);PTR = PTR ->next;}}

菜单驱动程序在C实现所有的堆栈操作使用链表:

#include <stdlib.h> #include <stdlib.h> void push();空白pop ();空白显示();Struct node {int val;Struct node *next;};Struct node *head;Void main () {int choice=0;printf (" \ n * * * * * * * * *栈使用链表操作 *********\ 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; } } }


下一个话题 DS队列



←上一页 下一个→