What is complexity of push and pop for a stack implemented using a linked list?
Ngày đăng:14/02/2022
Trả lời:74599
Lượt xem:141
Stack
Stack is a LIFO data structure (Last In First Out). Which basically means, the last element that you add to the stack is the first one that you’ll pull out. I good analogy would be your email inbox. The most recent mail will be shown atthe top, and if you read your mails from top to bottom, you’ll read your most recent mails first. If you’re getting hundreds of mails a day, this might mean you’ll never see some of the mails that are on the bottom of your stack.
Some common operations on a stack are push, pop and peek. Push will, obviously, push an item onto a stack. Pop will return the item, and delete it from the stack, and peek will allow you to see what the item at the top of the stack is, but it will not remove it..
Let’s say you have five items on your stack like the image below shows:
You can push an item onto your stack, let’ say you want to push item six on it:
Now you have six items on the stack, and item five is no longer available to you, like so:
Now you can push another item on the stack, or you can pop an item from the stack. If you call the pop operation, you’ll get back item six, and that item will be removed from the stack, like the following image illustrates:
Now we’re back where we started, with five items on the stack.
Implement a stack using singly linked list
To implement a stack using singly linked list concept , all the singly linked list operations are performed based on Stack operations LIFO(last in first out) and with the help of that knowledge we are going to implement a stack using single linked list. Using singly linked lists , we implement stack by storing the information in the form of nodes and we need to follow the stack rules and implement using singly linked list nodes . So we need to follow a simple rule in the implementation of a stack which is last in first out and all the operations can be performed with the help of a top variable .Let us learn how to perform Pop , Push , Peek ,Display operations in the following article .
A stack can be easily implemented using the linked list. In stack Implementation, a stack contains a top pointer. which is “head” of the stack where pushing and popping items happens at the head of the list. First node have null in link field and second node link have first node address in link field and so on and last node address in “top” pointer. The main advantage of using linked list over an arrays is that it is possible to implement a stack that can shrink or grow as much as needed. In using array will put a restriction to the maximum capacity of the array which can lead to stack overflow. Here each new node will be dynamically allocate. so overflow is not possible. Stack Operations:
push() : Insert a new element into stack i.e just inserting a new element at the beginning of the linked list.
pop() : Return top element of the Stack i.e simply deleting the first element from the linked list.
peek(): Return the top element.
display(): Print all elements in Stack.
Below is the implementation of the above approach:
C++
// C++ program to Implement a stack
//using singly linked list
#include
using namespace std;
// Declare linked list node
struct Node
{
int data;
Node* link;
};
Node* top;
// Utility function to add an element
// data in the stack insert at the beginning
void push(int data)
{
// Create new node temp and allocate memory in heap
Node* temp = new Node();
// Check if stack (heap) is full.
// Then inserting an element would
// lead to stack overflow
if (!temp)
{
cout << "\nStack Overflow";
exit(1);
}
// Initialize data into temp data field
temp->data = data;
// Put top pointer reference into temp link
temp->link = top;
// Make temp as top of Stack
top = temp;
}
// Utility function to check if
// the stack is empty or not
int isEmpty()
{
//If top is NULL it means that
//there are no elements are in stack
return top == NULL;
}
// Utility function to return top element in a stack
int peek()
{
// If stack is not empty , return the top element
if (!isEmpty())
return top->data;
else
exit(1);
}
// Utility function to pop top
// element from the stack
void pop()
{
Node* temp;
// Check for stack underflow
if (top == NULL)
{
cout << "\nStack Underflow" << endl;
exit(1);
}
else
{
// Assign top to temp
temp = top;
// Assign second node to top
top = top->link;
//This will automatically destroy
//the link between first node and second node
// Release memory of top node
//i.e delete the node
free(temp);
}
}
// Function to print all the
// elements of the stack
void display()
{
Node* temp;
// Check for stack underflow
if (top == NULL)
{
cout << "\nStack Underflow";
exit(1);
}
else
{
temp = top;
while (temp != NULL)
{
// Print node data
cout << temp->data << "-> ";
// Assign temp link to temp
temp = temp->link;
}
}
}
// Driver Code
int main()
{
// Push the elements of stack
push(11);
push(22);
push(33);
push(44);
// Display stack elements
display();
// Print top element of stack
cout << "\nTop element is "
<< peek() << endl;
// Delete top elements of stack
pop();
pop();
// Display stack elements
display();
// Print top element of stack
cout << "\nTop element is "
<< peek() << endl;
return 0;
}
Java
// Java program to Implement a stack
// using singly linked list
// import package
import static java.lang.System.exit;
// Create Stack Using Linked list
class StackUsingLinkedlist {
// A linked list node
private class Node {
int data; // integer data
Node link; // reference variable Node type
}
// create global top reference variable global
Node top;
// Constructor
StackUsingLinkedlist()
{
this.top = null;
}
// Utility function to add an element x in the stack
public void push(int x) // insert at the beginning
{
// create new node temp and allocate memory
Node temp = new Node();
// check if stack (heap) is full. Then inserting an
// element would lead to stack overflow
if (temp == null) {
System.out.print("\nHeap Overflow");
return;
}
// initialize data into temp data field
temp.data = x;
// put top reference into temp link
temp.link = top;
// update top reference
top = temp;
}
// Utility function to check if the stack is empty or not
public boolean isEmpty()
{
return top == null;
}
// Utility function to return top element in a stack
public int peek()
{
// check for empty stack
if (!isEmpty()) {
return top.data;
}
else {
System.out.println("Stack is empty");
return -1;
}
}
// Utility function to pop top element from the stack
public void pop() // remove at the beginning
{
// check for stack underflow
if (top == null) {
System.out.print("\nStack Underflow");
return;
}
// update the top pointer to point to the next node
top = (top).link;
}
public void display()
{
// check for stack underflow
if (top == null) {
System.out.printf("\nStack Underflow");
exit(1);
}
else {
Node temp = top;
while (temp != null) {
// print node data
System.out.printf("%d->", temp.data);
// assign temp link to temp
temp = temp.link;
}
}
}
}
// main class
public class GFG {
public static void main(String[] args)
{
// create Object of Implementing class
StackUsingLinkedlist obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// print Stack elements
obj.display();
// print Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
System.out.printf("\nTop element is %d\n", obj.peek());
}
}
Python3
'''Python supports automatic garbage collection so deallocation of memory
is done implicitly. However to force it to deallocate each node after use,
add the following code:
import gc #added at the start of program
gc.collect() #to be added wherever memory is to be deallocated
'''
class Node:
# Class to create nodes of linked list
# constructor initializes node automatically
def __init__(self,data):
self.data = data
self.next = None
class Stack:
# head is default NULL
def __init__(self):
self.head = None
# Checks if stack is empty
def isempty(self):
if self.head == None:
return True
else:
return False
# Method to add data to the stack
# adds to the start of the stack
def push(self,data):
if self.head == None:
self.head=Node(data)
else:
newnode = Node(data)
newnode.next = self.head
self.head = newnode
# Remove element that is the current head (start of the stack)
def pop(self):
if self.isempty():
return None
else:
# Removes the head node and makes
#the preceding one the new head
poppednode = self.head
self.head = self.head.next
poppednode.next = None
return poppednode.data
# Returns the head node data
def peek(self):
if self.isempty():
return None
else:
return self.head.data
# Prints out the stack
def display(self):
iternode = self.head
if self.isempty():
print("Stack Underflow")
else:
while(iternode != None):
print(iternode.data,"->",end = " ")
iternode = iternode.next
return
# Driver code
MyStack = Stack()
MyStack.push(11)
MyStack.push(22)
MyStack.push(33)
MyStack.push(44)
# Display stack elements
MyStack.display()
# Print top element of stack
print("\nTop element is ",MyStack.peek())
# Delete top elements of stack
MyStack.pop()
MyStack.pop()
# Display stack elements
MyStack.display()
# Print top element of stack
print("\nTop element is ", MyStack.peek())
# This code is contributed by Mathew George
C#
// C# program to Implement a stack
// using singly linked list
// import package
using System;
// Create Stack Using Linked list
public class StackUsingLinkedlist
{
// A linked list node
private class Node
{
// integer data
public int data;
// reference variable Node type
public Node link;
}
// create global top reference variable
Node top;
// Constructor
public StackUsingLinkedlist()
{
this.top = null;
}
// Utility function to add
// an element x in the stack
// insert at the beginning
public void push(int x)
{
// create new node temp and allocate memory
Node temp = new Node();
// check if stack (heap) is full.
// Then inserting an element
// would lead to stack overflow
if (temp == null)
{
Console.Write("\nHeap Overflow");
return;
}
// initialize data into temp data field
temp.data = x;
// put top reference into temp link
temp.link = top;
// update top reference
top = temp;
}
// Utility function to check if
// the stack is empty or not
public bool isEmpty()
{
return top == null;
}
// Utility function to return
// top element in a stack
public int peek()
{
// check for empty stack
if (!isEmpty())
{
return top.data;
}
else
{
Console.WriteLine("Stack is empty");
return -1;
}
}
// Utility function to pop top element from the stack
public void pop() // remove at the beginning
{
// check for stack underflow
if (top == null)
{
Console.Write("\nStack Underflow");
return;
}
// update the top pointer to
// point to the next node
top = (top).link;
}
public void display()
{
// check for stack underflow
if (top == null)
{
Console.Write("\nStack Underflow");
return;
}
else
{
Node temp = top;
while (temp != null)
{
// print node data
Console.Write("{0}->", temp.data);
// assign temp link to temp
temp = temp.link;
}
}
}
}
// Driver code
public class GFG
{
public static void Main(String[] args)
{
// create Object of Implementing class
StackUsingLinkedlist obj = new StackUsingLinkedlist();
// insert Stack value
obj.push(11);
obj.push(22);
obj.push(33);
obj.push(44);
// print Stack elements
obj.display();
// print Top element of Stack
Console.Write("\nTop element is {0}\n", obj.peek());
// Delete top element of Stack
obj.pop();
obj.pop();
// print Stack elements
obj.display();
// print Top element of Stack
Console.Write("\nTop element is {0}\n", obj.peek());
}
}
// This code is contributed by 29AjayKumar
Javascript
Output:
44->33->22->11->
Top element is 44
22->11->
Top element is 22
Time Complexity:
The time complexity for all push(), pop(), and peek() operations is O(1) as we are not performing any kind of traversal over the list. We perform all the operations through the current pointer only.
Article Tags :
Linked List
Stack
Technical Scripter
Technical Scripter 2018
Practice Tags :
Linked List
Stack
Read Full Article
Linked list implementation of stack
Instead of using array, we can also use linked list to implement stack. Linked list allocates the memory dynamically. However, time complexity in both the scenario is same for all the operations i.e. push, pop and peek.
In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.
The top most node in the stack always contains null in its address field. Lets discuss the way in which, each operation is performed in linked list implementation of stack.
‘push’ with appending an item
First, we are going to append an item to our Array Lists Stack. The running time is O(1)*. * means average. Why is it important to say that the runtime is “constant on average” rather than simply constant? That’s because it takes a long time to create new contiguous blocks (usually copy the length of the block) and add item if the block is full already, otherwise the running time is O(1) to add item to the next to the last index.
Appending operation in Array Lists
Next, we perform the ‘peek’ operation. We know the length of the array list, and the last item we add is the item at the last index of the array list because we can simply append the item. Therefore, the item on the top of the stack is the item in index (the length of the array list)-1. This running time is O(1).
How about pop? We can use the built-in function ‘pop’, which returns and removes the last item. This running time is O(1)*.
‘push’ with prepending an item
When we append item to push, the running time for each operation is constant. We have one more option to push item. How long is the running time for each operation, when we insert item to the first index?
Let’s add new item at index 0. Wait… There is an item at index 0 already. How can we insert the new item at index 0? The answer is to create a new array list with the new item at the first index, pushing all other values up the list.Thus, we need another block of memory and have to copy the items. The running time is O(n) for n items in the last array list.
Prepending operation in Array Lists
We implement peek next. We returns the item at index 0 because the last item we push on the top is the first item in the array list. This running time is O(1).
Finally, we perform the ‘pop’ operation. We are going to remove and return the first item of the arraylist. We need another contiguous block of memory to duplicate the items except the first item. Therefore, it takes O(n) for n items in the arraylist.
Let’s summarize running times of each implementations.
We are going to implement stack with linked list. We have two starting ways of pushing an item to our Linked Stack. We append a new node after the tail (the last node) or prepend new node before the head.
Basics of Stack
A Stack is a Linear Data Structure in which Operations are performed in a specific order known as LIFO(Last In First Out) or FILO (First In Last Out). Operations on Stack occur only at one end called as the TOP of the stack. Stack can be implemented using Arrays and LinkedLists.
Stack have many applications like:
Conversion of infix to postfix expressions
Forward - Backward Surfing in browsers use Stack
Undo Mechanism uses Stacks internally.
Stacks are used to perform recursion
Real world Stack examples would include :
Plates on a tray
Stack of Books
Stack of coins etc.
Let's consider an example of stack
In this example above , we have 3 elements and the top of the stack is pointing towards the topmost element which is 3. The Top always points towards the last inserted element.
Operations on Stacks
The most common operations that we perform on stacks are :
Push in Stack
Push operation basically means insertion of an element into a stack , which is done through the top pointer, the top pointer points to the newest added element.
For example let's consider the stack below , the top points at 2 .
| |
| |
| 2 | <- Top of the Stack
|_1_|
Let's Push 3 into the stack , then the stack would look like:
| |
| 3 | <- Top of the Stack
| 2 |
|_1_|
Time Complexity
Worst Case Scenario would be O(n) in case of a array implementation of stack where the array is completely filled, then the array size needs to be changed and all the elements must be copied from one array to another , this would result in time being O(n). In case of a LinkedList approach, time remains constant O(1). Example:
| 3 | <- Top of the Stack
| 2 |
|_1_|
S
consider the above stack S , if we had to add another element say 4 to this Stack, it would result in an overflow as the array is filled, so how do we avoid it? We can extend the array size so we can accommodate more elements into the stack
| |
| |
| 4 | <- Top of the Stack
| 3 |
| 2 |
|_1_|
S
after extending and copying back the elements , new element can be inserted at the top of the stack.
Best Case Scenario is O(1) as only one elements needs to be pushed onto the stack.
Average Case Scenario would be O(1).
Space Complexity
Space complexity of Push Operation is O(1).
POP in Stack
Pop operation deletes an element from the stack and returns it , the topmost element pointed by the top is deleted in Pop operation.
For example let's consider the stack below , the top points at 3 .
| |
| 3 | <- Top of the Stack
| 2 |
|_1_|
Let's Pop from the stack , then the stack would look like:
| |
| |
| 2 | <- Top of the Stack
|_1_|
Time Complexity
Worst Case Scenario is O(1) , as Deletion operation only removes the top element.
Best Case Scenario is O(1).
Average Case Scenario would be O(1) as only the top element is needed to be removed.
Space Complexity
Space Complexity of Pop Operation is O(1) as no additional space is required for it.
Peek in Stack
Peek operation returns the topmost element from the stack , no addition or deletion is involved in this operation.
For example let's consider the stack below , the top points at 3 .
| |
| 3 | <- Top of the Stack
| 2 |
|_1_|
The Peek operation would return 3 , no changes to the stack are made.
Time Complexity
The Average , Worst and Best Time Complexities of Peek operation are O(1), as peeking only returns the top of the stack.
Space Complexity
Space Complexity of Peek Operation is O(1) as no additional space is required for it.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include
#include
// A Linked List Node
structNode
{
intdata;// integer data
structNode*next;// pointer to the next node
};
intnodesCount;
// Utility function to add an element `x` to the stack
voidpush(structNode**top,intx)// insert at the beginning
{
// allocate a new node in a heap
structNode*node=NULL;
node=(structNode*)malloc(sizeof(structNode));
// check if stack (heap) is full. Then inserting an element would
// lead to stack overflow
if(!node)
{
printf("Heap Overflow\n");
exit(-1);
}
printf("Inserting %d\n",x);
// set data in the allocated node
node->data=x;
// set the .next pointer of the new node to point to the current
// top node of the list
node->next=*top;
// update top pointer
*top=node;
// increase stack's size by 1
nodesCount+=1;
}
// Utility function to check if the stack is empty or not
intisEmpty(structNode*top){
returntop==NULL;
}
// Utility function to return the top element of the stack
intpeek(structNode*top)
{
// check for an empty stack
if(!isEmpty(top)){
returntop->data;
}
else{
printf("The stack is empty\n");
exit(EXIT_FAILURE);
}
}
// Utility function to pop a top element from the stack
intpop(structNode**top)// remove at the beginning
{
structNode*node;
// check for stack underflow
if(*top==NULL)
{
printf("Stack Underflow\n");
exit(EXIT_FAILURE);
}
// take note of the top node's data
intx=peek(*top);
printf("Removing %d\n",x);
node=*top;
// update the top pointer to point to the next node
*top=(*top)->next;
// decrease stack's size by 1
nodesCount-=1;
// free allocated memory
free(node);
returnx;
}
// Utility function to return the nodesCount of the stack
intsize(){
returnnodesCount;
}
intmain(void)
{
structNode*top=NULL;
push(&top,1);
push(&top,2);
push(&top,3);
printf("The top element is %d\n",peek(top));
pop(&top);
pop(&top);
pop(&top);
if(isEmpty(top)){
printf("The stack is empty\n");
}
else{
printf("The stack is not empty\n");
}
return0;
}
DownloadRun Code
What is the time complexity of push and pop operations?
August 15, 2020
Table of Contents
What is the time complexity of push and pop operations?
What is the time complexity of pop operation?
What is the time complexity of pop () operation when the stack is implemented using an linked list?
What is the time complexity of pop operation when stack is implemented using an array?
Are arrays faster than lists?
What is advantage of linked list over arrays?
Why would you use a linked list?
Why is it difficult to store linked list in an array?
Which of the following statements about Stack is incorrect?
