{"id":8765,"date":"2021-07-20T08:14:06","date_gmt":"2021-07-20T13:14:06","guid":{"rendered":"https:\/\/www.pythonforbeginners.com\/?p=8765"},"modified":"2021-07-20T08:14:09","modified_gmt":"2021-07-20T13:14:09","slug":"implement-stack-in-python","status":"publish","type":"post","link":"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python","title":{"rendered":"Implement Stack in Python"},"content":{"rendered":"\n

Stack is a data structure which follows last in first out (LIFO) order for accessing the elements. In a stack, we can only access the most recently added element. Stacks have many uses in applications like expression handling, backtracking and function calls. In this article, we will try to implement stack data structure with linked lists in python.<\/p>\n\n\n\n

Implement stack in Python using linked list<\/h2>\n\n\n\n

A linked list is a linear data structure in which each data object points to one another. To implement a stack with linked list, we will have to perform insertion and deletion and deletion of elements from a linked list such that it takes a constant amount of time. This is only possible when we insert as well as delete the elements at the start of the linked list.<\/p>\n\n\n\n

To implement a stack with linked list in python, we will first define a node object which will have the current element, will point to the node which was inserted just before it using a reference next. The Node can be implemented as follows in python.<\/p>\n\n\n\n

class Node:\n    def __init__(self,data,size):\n        self.data=data\n        self.next=None<\/code><\/pre>\n\n\n\n
When we implement a stack with linked list, it will have an element named top which will refer to the most recent element inserted in the linked list. All other  elements can be accessed with the help of that.We can implement an empty stack in python with top initialized to None and stackSize initialized to 0 as follows .<\/p>\n\n\n\n
class Stack:\n    def __init__(self):\n        self.top=None\n        self.stackSize=0<\/code><\/pre>\n\n\n\n
Implement Push operation in stack in Python<\/h2>\n\n\n\n
When we insert an element into the stack, the operation is called push operation. To implement push operation in stack with the help of linked list, for every insertion we will add the element to be inserted at the start of the linked list . In this way, the most recent element will always be at the start of the linked list. Then we will point the top element of the stack to the start of the linked list and increment the stackSize by 1. The push operation can be implemented using linked lists in python as follows.<\/p>\n\n\n\n
 def push(self,data):\n        temp=Node(data)\n        if self.top is None:\n            self.top=temp\n            self.stackSize= self.stackSize+1\n        else:\n            temp.next=self.top\n            self.top=temp\n            self.stackSize=self.stackSize+1<\/code><\/pre>\n\n\n\n
Implement Pop operation in stack in Python<\/h2>\n\n\n\n
When we take out an element from the stack, the operation is said to be a pop operation. The element to be taken out from stack is the most recently added element to the stack. As we know that during a push operation, we add the most recent element to the start of the linked list which is pointed by the top of stack hence we will remove the element pointed by top and will point top to the next recent element. Before performing pop operation, we will check if stack is empty. If the stack is empty i.e. top points to None, we will raise an exception using python try except<\/a> with a message that stack is empty. We can implement the pop operation as follows.<\/p>\n\n\n\n
 def pop(self):\n        try:\n            if self.top == None:\n                raise Exception(\"Stack is Empty\")\n            else:\n                temp=self.top\n                self.top=self.top.next\n                tempdata=temp.data\n                self.stackSize= self.stackSize-1\n                del temp\n                return tempdata\n        except Exception as e:\n            print(str(e))<\/code><\/pre>\n\n\n\n
How to access topmost element of stack<\/h2>\n\n\n\n
As the topmost element of the stack is being referenced by top, we just have to return the data in the node pointed by top. It can be implemented as follows.<\/p>\n\n\n\n
def top_element(self):\n        try:\n            if self.top == None:\n                raise Exception(\"Stack is Empty\")\n            else:\n                return self.top.data\n        except Exception as e:\n            print(str(e))<\/code><\/pre>\n\n\n\n
Get the size of the stack<\/h2>\n\n\n\n
As we keep the current size of stack in stackSize variable, we just have to return the value in the stackSize variable top. This can be done as follows.<\/p>\n\n\n\n
def size(self):\n        return self.stackSize<\/code><\/pre>\n\n\n\n
Check if the stack is empty<\/h2>\n\n\n\n
The element top refers to the most recent element in the stack. If there is no element in the stack, top will point to None. Thus, to check if the stack is empty, we just have to check if top points to None or stackSize variable has a value 0. We can implement isEmpty() method to check if the stack is empty as follows.<\/p>\n\n\n\n
def isEmpty(self):\n        if self.stackSize==0:\n            return True\n        else:\n            return False<\/code><\/pre>\n\n\n\n
The full working code to implement stack using linked list in python is as follows.<\/p>\n\n\n\n
#!\/usr\/bin\/env python3\n# -*- coding: utf-8 -*-\n\"\"\"\nCreated on Sun Apr 25 00:28:19 2021\n\n@author: aditya1117\n\"\"\"\n\nclass Node:\n    def __init__(self,data):\n        self.data=data\n        self.next=None\nclass Stack:\n    def __init__(self):\n        self.top=None\n        self.stackSize=0\n    def push(self,data):\n        temp=Node(data)\n        if self.top is None:\n            self.top=temp\n            self.stackSize= self.stackSize+1\n        else:\n            temp.next=self.top\n            self.top=temp\n            self.stackSize=self.stackSize+1\n    def pop(self):\n        try:\n            if self.top == None:\n                raise Exception(\"Stack is Empty\")\n            else:\n                temp=self.top\n                self.top=self.top.next\n                tempdata=temp.data\n                self.stackSize= self.stackSize-1\n                del temp\n                return tempdata\n        except Exception as e:\n            print(str(e))\n    def isEmpty(self):\n        if self.stackSize==0:\n            return True\n        else:\n            return False\n    def size(self):\n        return self.stackSize\n    def top_element(self):\n        try:\n            if self.top == None:\n                raise Exception(\"Stack is Empty\")\n            else:\n                return self.top.data\n        except Exception as e:\n            print(str(e))\ns=Stack()\ns.push(1)\nprint(s.size())\n\ns.push(2)\nprint(s.size())\n\nprint(s.pop())\nprint(s.size())\nprint(s.pop())\nprint(s.stackSize)\n\nprint(s.top_element())\nprint(s.isEmpty())<\/code><\/pre>\n\n\n\n
Output:<\/p>\n\n\n\n
1\n2\n2\n1\n1\n0\nStack is Empty\nNone\nTrue<\/code><\/pre>\n\n\n\n
Conclusion<\/h2>\n\n\n\n
In this article, we have implemented stack and all its operations using linked list in python. To gain more insight into it and understand how stack is different from inbuilt data structures like python dictionary<\/a>, list and set , copy the full code given in the above example and experiment with the operations in it. Stay tuned for more informative articles.<\/p>\n","protected":false},"excerpt":{"rendered":"
Stack is a data structure which follows last in first out (LIFO) order for accessing the elements. In a stack, we can only access the most recently added element. Stacks have many uses in applications like expression handling, backtracking and function calls. In this article, we will try to implement stack data structure with linked […]<\/p>\n","protected":false},"author":7,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_genesis_hide_title":false,"_genesis_hide_breadcrumbs":false,"_genesis_hide_singular_image":false,"_genesis_hide_footer_widgets":false,"_genesis_custom_body_class":"","_genesis_custom_post_class":"","_genesis_layout":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[206],"tags":[],"class_list":{"0":"post-8765","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-data-types","7":"entry"},"yoast_head":"\nImplement Stack in Python - PythonForBeginners.com<\/title>\n<meta name=\"description\" content=\"Implement Stack in Python will help you improve your python skills with easy to follow examples and tutorials. Click here to view code examples.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Implement Stack in Python - PythonForBeginners.com\" \/>\n<meta property=\"og:description\" content=\"Implement Stack in Python will help you improve your python skills with easy to follow examples and tutorials. Click here to view code examples.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python\" \/>\n<meta property=\"og:site_name\" content=\"PythonForBeginners.com\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/pythonbeginners\" \/>\n<meta property=\"article:published_time\" content=\"2021-07-20T13:14:06+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-07-20T13:14:09+00:00\" \/>\n<meta name=\"author\" content=\"Aditya Raj\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@pythonbeginners\" \/>\n<meta name=\"twitter:site\" content=\"@pythonbeginners\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Aditya Raj\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/data-types\\\/implement-stack-in-python#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/data-types\\\/implement-stack-in-python\"},\"author\":{\"name\":\"Aditya Raj\",\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/#\\\/schema\\\/person\\\/dfbeed7ea64bdf47ddfd1a86a70d6c60\"},\"headline\":\"Implement Stack in Python\",\"datePublished\":\"2021-07-20T13:14:06+00:00\",\"dateModified\":\"2021-07-20T13:14:09+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/data-types\\\/implement-stack-in-python\"},\"wordCount\":700,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/#organization\"},\"articleSection\":[\"Data Types\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/www.pythonforbeginners.com\\\/data-types\\\/implement-stack-in-python#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/data-types\\\/implement-stack-in-python\",\"url\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/data-types\\\/implement-stack-in-python\",\"name\":\"Implement Stack in Python - PythonForBeginners.com\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/#website\"},\"datePublished\":\"2021-07-20T13:14:06+00:00\",\"dateModified\":\"2021-07-20T13:14:09+00:00\",\"description\":\"Implement Stack in Python will help you improve your python skills with easy to follow examples and tutorials. Click here to view code examples.\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/data-types\\\/implement-stack-in-python#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/www.pythonforbeginners.com\\\/data-types\\\/implement-stack-in-python\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/data-types\\\/implement-stack-in-python#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Implement Stack in Python\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/#website\",\"url\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/\",\"name\":\"PythonForBeginners.com\",\"description\":\"Learn By Example\",\"publisher\":{\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/#organization\",\"name\":\"PythonForBeginners.com\",\"url\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/#\\\/schema\\\/logo\\\/image\\\/\",\"url\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/wp-content\\\/uploads\\\/2020\\\/05\\\/PFB-Logo-Final.png\",\"contentUrl\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/wp-content\\\/uploads\\\/2020\\\/05\\\/PFB-Logo-Final.png\",\"width\":1868,\"height\":318,\"caption\":\"PythonForBeginners.com\"},\"image\":{\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/#\\\/schema\\\/logo\\\/image\\\/\"},\"sameAs\":[\"https:\\\/\\\/www.facebook.com\\\/pythonbeginners\",\"https:\\\/\\\/x.com\\\/pythonbeginners\"]},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/#\\\/schema\\\/person\\\/dfbeed7ea64bdf47ddfd1a86a70d6c60\",\"name\":\"Aditya Raj\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a464376c828c3a1ba1c354635f5bcb090e3072ebac0e96af3c0f741c717175c1?s=96&d=mm&r=g\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a464376c828c3a1ba1c354635f5bcb090e3072ebac0e96af3c0f741c717175c1?s=96&d=mm&r=g\",\"contentUrl\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a464376c828c3a1ba1c354635f5bcb090e3072ebac0e96af3c0f741c717175c1?s=96&d=mm&r=g\",\"caption\":\"Aditya Raj\"},\"description\":\"A python enthusiast.I love teaching and writing articles on computer science and related subjects.\",\"url\":\"https:\\\/\\\/www.pythonforbeginners.com\\\/author\\\/aditya\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Implement Stack in Python - PythonForBeginners.com","description":"Implement Stack in Python will help you improve your python skills with easy to follow examples and tutorials. Click here to view code examples.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python","og_locale":"en_US","og_type":"article","og_title":"Implement Stack in Python - PythonForBeginners.com","og_description":"Implement Stack in Python will help you improve your python skills with easy to follow examples and tutorials. Click here to view code examples.","og_url":"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python","og_site_name":"PythonForBeginners.com","article_publisher":"https:\/\/www.facebook.com\/pythonbeginners","article_published_time":"2021-07-20T13:14:06+00:00","article_modified_time":"2021-07-20T13:14:09+00:00","author":"Aditya Raj","twitter_card":"summary_large_image","twitter_creator":"@pythonbeginners","twitter_site":"@pythonbeginners","twitter_misc":{"Written by":"Aditya Raj","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python#article","isPartOf":{"@id":"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python"},"author":{"name":"Aditya Raj","@id":"https:\/\/www.pythonforbeginners.com\/#\/schema\/person\/dfbeed7ea64bdf47ddfd1a86a70d6c60"},"headline":"Implement Stack in Python","datePublished":"2021-07-20T13:14:06+00:00","dateModified":"2021-07-20T13:14:09+00:00","mainEntityOfPage":{"@id":"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python"},"wordCount":700,"commentCount":0,"publisher":{"@id":"https:\/\/www.pythonforbeginners.com\/#organization"},"articleSection":["Data Types"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python","url":"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python","name":"Implement Stack in Python - PythonForBeginners.com","isPartOf":{"@id":"https:\/\/www.pythonforbeginners.com\/#website"},"datePublished":"2021-07-20T13:14:06+00:00","dateModified":"2021-07-20T13:14:09+00:00","description":"Implement Stack in Python will help you improve your python skills with easy to follow examples and tutorials. Click here to view code examples.","breadcrumb":{"@id":"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/www.pythonforbeginners.com\/data-types\/implement-stack-in-python#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.pythonforbeginners.com\/"},{"@type":"ListItem","position":2,"name":"Implement Stack in Python"}]},{"@type":"WebSite","@id":"https:\/\/www.pythonforbeginners.com\/#website","url":"https:\/\/www.pythonforbeginners.com\/","name":"PythonForBeginners.com","description":"Learn By Example","publisher":{"@id":"https:\/\/www.pythonforbeginners.com\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.pythonforbeginners.com\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/www.pythonforbeginners.com\/#organization","name":"PythonForBeginners.com","url":"https:\/\/www.pythonforbeginners.com\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.pythonforbeginners.com\/#\/schema\/logo\/image\/","url":"https:\/\/www.pythonforbeginners.com\/wp-content\/uploads\/2020\/05\/PFB-Logo-Final.png","contentUrl":"https:\/\/www.pythonforbeginners.com\/wp-content\/uploads\/2020\/05\/PFB-Logo-Final.png","width":1868,"height":318,"caption":"PythonForBeginners.com"},"image":{"@id":"https:\/\/www.pythonforbeginners.com\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/pythonbeginners","https:\/\/x.com\/pythonbeginners"]},{"@type":"Person","@id":"https:\/\/www.pythonforbeginners.com\/#\/schema\/person\/dfbeed7ea64bdf47ddfd1a86a70d6c60","name":"Aditya Raj","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/a464376c828c3a1ba1c354635f5bcb090e3072ebac0e96af3c0f741c717175c1?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/a464376c828c3a1ba1c354635f5bcb090e3072ebac0e96af3c0f741c717175c1?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/a464376c828c3a1ba1c354635f5bcb090e3072ebac0e96af3c0f741c717175c1?s=96&d=mm&r=g","caption":"Aditya Raj"},"description":"A python enthusiast.I love teaching and writing articles on computer science and related subjects.","url":"https:\/\/www.pythonforbeginners.com\/author\/aditya"}]}},"jetpack_publicize_connections":[],"featured_image_src":null,"featured_image_src_square":null,"author_info":{"display_name":"Aditya Raj","author_link":"https:\/\/www.pythonforbeginners.com\/author\/aditya"},"jetpack_featured_media_url":"","jetpack-related-posts":[],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.pythonforbeginners.com\/wp-json\/wp\/v2\/posts\/8765","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.pythonforbeginners.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.pythonforbeginners.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.pythonforbeginners.com\/wp-json\/wp\/v2\/users\/7"}],"replies":[{"embeddable":true,"href":"https:\/\/www.pythonforbeginners.com\/wp-json\/wp\/v2\/comments?post=8765"}],"version-history":[{"count":4,"href":"https:\/\/www.pythonforbeginners.com\/wp-json\/wp\/v2\/posts\/8765\/revisions"}],"predecessor-version":[{"id":9269,"href":"https:\/\/www.pythonforbeginners.com\/wp-json\/wp\/v2\/posts\/8765\/revisions\/9269"}],"wp:attachment":[{"href":"https:\/\/www.pythonforbeginners.com\/wp-json\/wp\/v2\/media?parent=8765"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.pythonforbeginners.com\/wp-json\/wp\/v2\/categories?post=8765"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.pythonforbeginners.com\/wp-json\/wp\/v2\/tags?post=8765"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}