Stacks using Dynamic Memory Allocation
A stack that dynamically allocates memory for each of its elements (just like a linked list) is also known as a linked stack.
The array-based representation of a stack suffers from the following limitations.
- The size of the stack must be known in advance.
- We may come across a situation when we need to push more elements in the stack, but cannot do so because we’ve reached the maximum size.
However, a stack is an abstract data structure and should not become full. Hence, abstractly, it is always possible to push an element onto the stack. A
stack as an array prohibits the growth of the stack beyond the finite number of elements.
Declaration of a Stack
The linked representation allows a stack to grow to the limit of the computer’s memory.
Syntax
typedef struct nodetype
{
int info;
struct nodetype *next;
} stack;
stack *top;
Here I have defined my own data type named stack, which is a self-referential structure and whose first element info holds the element of the stack and the second element next holds the address of the element under it in the stack.
The last line declares a pointer variable top of type stack.
Representation of Stack in Memory
Creating an Empty Stack
Before we can use a stack, it needs to be initialized. To initialize a stack, we will create an empty linked list. The empty linked list is created by setting pointer variable top to value NULL. (Note: NULL is defined a number of headers, including <stddef.h>, <stdlib.h> and <stdio.h>.)
void createstack(stack **top)
{
*top=NULL;
}
Testing a Stack for Underflow
bool isempty(stack *top)
{
if(top==NULL)
return true;
else
return false;
}
or
bool isempty(stack *top)
{
return (top==NULL)?true:false;
}
Note: bool can be defined as
typedef enum {false, true} bool;
Push operation
To push a new element onto the stack, the element is inserted in the beginning of the linked list.
void push(stack **top, int value)
{
stack *ptr;
ptr= malloc(sizeof(stack));
if(ptr==NULL)
{
printf("\n unable to allocate memory for new node…");
return;
}
ptr->info=value;
ptr->next=*top;
*top=ptr;
}
Pop Operation
To pop an element from the stack, the element is removed from the beginning of the linked list.
int pop(stack **top)
{
int temp;
stack *ptr;
temp=(*top)->info;
ptr=*top;
*top=(*top)->next;
free(ptr);
return temp;
}
Disposing a Stack
Because the stack is implemented using nodes that are dynamically allocated, it is the programmer’s job to write code to release the memory occupied by the stack.
void disposestack(stack **top)
{
stack *ptr;
while(*top!=NULL)
{
ptr=*top;
*top=(*top)->next;
free(ptr);
}
}
Complete Program
/**
* Stack using dynamically allocated nodes.
* http://www.tech-faq.com
*/
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h> /*For malloc and free*/
typedef struct nodetype
{
int info;
struct nodetype *next;
} stack;
typedef enum {false, true} bool;
void createstack(stack **top);
bool isempty(stack *top);
void push(stack **top, int value);
int pop(stack **top);
void disposestack(stack **top);
void display(stack *top);
int main()
{
char ch = 'y';
stack *top;
int data;
createstack(&top);
while (ch=='y' || ch=='Y')
{
printf("\nEnter new node data: ");
fflush(stdout);
scanf("%d", &data);
push(&top, data);
puts("Node pushed in stack...");
puts("Now the stack is: ");
display(top);
printf("Continue(y/n): ");
fflush(stdout);
scanf(" %c", &ch);
}
printf("\nDo you want to pop a node(y/n): ");
fflush(stdout);
scanf(" %c", &ch);
while (ch=='y' || ch=='Y')
{
pop(&top);
display(top);
printf("\nDo you want to pop a node(y/n): ");
fflush(stdout);
scanf(" %c", &ch);
}
return 0;
}
void createstack(stack **top)
{
*top=NULL;
}
bool isempty(stack *top)
{
if(top==NULL)
return true;
else
return false;
}
void push(stack **top, int value)
{
stack *ptr;
ptr= malloc(sizeof(stack));
if(ptr==NULL)
{
printf("\n unable to allocate memory for new node…");
exit(1);
}
puts("New node successfully created...");
ptr->info=value;
ptr->next=*top;
*top=ptr;
}
int pop(stack **top)
{
int temp;
stack *ptr;
temp=(*top)->info;
ptr=*top;
*top=(*top)->next;
free(ptr);
return temp;
}
void disposestack(stack **top)
{
stack *ptr;
while(*top!=NULL)
{
ptr=*top;
*top=(*top)->next;
free(ptr);
}
}
void display(stack *top)
{
while (top!=NULL)
{
printf("%d ->", top->info);
top = top->next;
}
printf("\b\b \n");
}
Output
Enter new node data: 78
New node successfully created...
Node pushed in stack...
Now the stack is:
78
Continue(y/n): y
Enter new node data: 45
New node successfully created...
Node pushed in stack...
Now the stack is:
45 ->78
Continue(y/n): y
Enter new node data: 34
New node successfully created...
Node pushed in stack...
Now the stack is:
34 ->45 ->78
Continue(y/n): y
Enter new node data: 89
New node successfully created...
Node pushed in stack...
Now the stack is:
89 ->34 ->45 ->78
Continue(y/n): n
Do you want to pop a node(y/n): y
34 ->45 ->78
Do you want to pop a node(y/n): n
|
|
- Stacks
Stacks are one of the commonly used data structures. A stack is also known as a last in first out (LIFO) system. It can be considered as a linear list in which insertion and deletion can take place only at one end called the top. This structure operates in much the same way as a [...]...
- Traversing and Searching a Linear Linked List
Traversing a list A linear list can be traversed in two ways In order traversal Reverse order traversal In order Traversal To traverse the linear linked list, we walk the list using the pointers, and process each element until we reach the last element. .cf { font-family: Lucida Console; font-size: 9pt; color: black; background: white; [...]...
- Insertion in a Linear Linked List
To insert an element in the list, the first task is to create a new node, assign the element to be inserted to the info field of the node, and then place the new node at the appropriate position by adjusting the appropriate pointers. Insertion in the list can take place at the following positions: [...]...
- Inserting in a Doubly Linked List
Inserting an Element To insert an element in the list, the first task is to allocate memory for a new node, assign the element to be inserted to the info field of the node, and then the new node is placed at the appropriate position by adjusting appropriate pointers. Insertion in the list can take [...]...
- Deleting an Element from a Doubly Linked List
To delete an element from the list, first the pointers are set properly and then the memory occupied by the node to be deleted is deallocated (freed). Deletion in the list can take place at the following positions. At the beginning of the list At the end of the list After a given element Before [...]...