Stack (Abstract Data Type)

Icon representing a stack.
Source: Layers by Adrien Coquet from the Noun Project

A stack is a collection of items or elements used in programming languages. It is usually referred to as an abstract data type (ADT) as it provides abstract or essential details of its implementation (using an array or linked list). A stack is based on linear data structure or works on the principle of  Last In First Out (LIFO) or First in Last out (FILO). It consists of two main operations named Push (adding data to the stack) and Pop (removing data from the stack). A stack has only one end; therefore, its operations happen on the top position. 

How is a stack implemented?

Further, a stack may have either a fixed size or a dynamic implementation. However, if an attempt is made to push an element while the stack is already full, it causes a stack overflow. On the other hand, whenever an attempt is made to remove an element from an empty stack, then it leads to stack underflow.

When a new element is added to the stack, the stack pointer or register moves to the new element and copies that element to the register. Typically, a stack consists of a linear sequence of items in contrast to a queue that follows the principle of First in First out (FIFO). 

What are the basic operations a stack supports?

The term is often used in discussing allocation and access of system memory in computers. Key stack operations include:

  • Push: Push operation involves placing an item on the top of the stack.
  • Pop: Popping means an element is taken from the top of the stack.
  • Peek: Allows users to view the top item in the stack.
  • Duplicate: Duplication is the process of copying a top item’s value and pushing it back.
  • Swap: Swap involves swapping the two topmost items.
  • Rotate: Rotate involves moving topmost elements as specified by a number of items to be moved in a rotating fashion.
  • Display: Shows all the elements of the stack.

How is a stack implemented?

The implementation is a stack is done using the linked lists or using arrays. 

Linked list implementation

There is no pre-allocated storage for the stack with linked list implementation. It allocates memory as nodes according to the run time requirements. In a linked list, only one private data member, or stack pointer, is required by the class, and it’s the node at the top of the stack. 

Array implementation

Stack implementation using an array is easy as it includes a dimensional array of a specific size. Due to the specific size of the array, it becomes easy to either delete or add values into the array by leveraging the principle of LIFO. The pointer concept is not involved in array implementation as memory is fixed. 

Main applications of a stack

Here are some of the top applications of a stack:

  • Memory management: A stack uses unused system memory for temporary data storage.
  • Expression evaluation: Stacks can be used to evaluate the programming expressions Infix Expressions, Prefix Expressions, and Postfix Expressions. 
  • Expression conversion: It is used to convert from one expression to another.  
  • String reversal: The first element of the stack on the bottom and the last element on the top. After completing a pop, all elements get in a String in reverse order.
  • Parenthesis checking: Stack is used to store parenthesis—(, ), {, }—and control the flow of programming.
  • Syntax parsing: Most compilers use a stack for syntax parsing.
  • Function call: Stacks can store the address of a call that coders make from one function to another while programming.

Finally, stacks can be used to reverse the order of elements or items. Stacks efficiently allocate space; therefore, memory never gets fragmented. However, it possesses predefined storage space, and it’s not flexible.

Siji Roy
Siji Roy
Siji Roy specializes in technology, finance, and content marketing. She helps organizations to communicate with their target audience. She received her Master’s degree in Communication and Journalism from the University of Calicut, India. She is fortunate to be married to a lovely person and blessed with three naughty boys.

Top Articles

List of Windows Operating System Versions & History [In Order]

The Windows operating system (Windows OS) refers to a family of operating systems developed by Microsoft Corporation. We look at the history of Windows...

How to Create a Website Shortcut on Your Desktop

Website Shortcut on Your Desktop reviewed by Web Webster   This Webopedia guide will show you how to create a website shortcut on your desktop using...

What are the Five Generations of Computers? (1st to 5th)

Reviewed by Web Webster Each generation of computer has brought significant advances in speed and power to computing tasks. Learn about each of the...

Hotmail [Outlook] Email Accounts

Launched in 1996, Hotmail was one of the first public webmail services that could be accessed from any web browser. At its peak in...

Conti Ransomware

Conti ransomware first emerged in 2020. It uses a ransomware as a service...

Crypt888 Ransomware

Crypt888, also known as Mircop, is ransomware that encrypts files on desktops, downloads,...

AutoLocky Ransomware

AutoLocky is ransomware written in the popular AutoIt scripting language. It uses strong...