Stack Data Structure

Last Updated : 30 Jul, 2024

A Stack is a linear data structure that follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). LIFO implies that the element that is inserted last, comes out first and FILO implies that the element that is inserted first, comes out last.

Table of Content

What is Stack Data Structure?

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It behaves like a stack of plates, where the last plate added is the first one to be removed.

Think of it this way:

Pushing an element onto the stack is like adding a new plate on top.
Popping an element removes the top plate from the stack.

Key Operations on Stack Data Structures

Push: Adds an element to the top of the stack.
Pop: Removes the top element from the stack.
Peek: Returns the top element without removing it.
IsEmpty: Checks if the stack is empty.
IsFull: Checks if the stack is full (in case of fixed-size arrays).

Applications of Stack Data Structures

Recursion
Expression Evaluation and Parsing
Depth-First Search (DFS)
Undo/Redo Operations
Browser History
Function Calls

Basics of Stack Data Structure

Implementations of Stack in Different Languages

Other Implementations of Stack Data Structures

Easy Problems on Stack Data Structures

Medium Problems on Stack Data Structures

Hard Problems on Stack Data Structures

Quick Links :

Recommended:

H

harendrakumar123

News

Improve

What is Stack Data Structure? A Complete Tutorial

Similar Reads

Static Data Structure vs Dynamic Data Structure

Data structure is a way of storing and organizing data efficiently such that the required operations on them can be performed be efficient with respect to time as well as memory. Simply, Data Structure are used to reduce complexity (mostly the time complexity) of the code. Data structures can be two types : 1. Static Data Structure 2. Dynamic Data

Stack Vs Heap Data Structure

What is Stack? A stack is a linear data structure where the last element entered exits first. The order of stack data structure might be LIFO, FILO: According to this technique, the piece that is in last will come out first. As an example, consider a stack of dishes stacked on top of each other. The plate we put last is on top, and because we take

Implement Dynamic Multi Stack (K stacks) using only one Data Structure

In this article, we will see how to create a data structure that can handle multiple stacks with growable size. The data structure needs to handle three operations: push(x, stackNum) = pushes value x to the stack numbered stackNumpop(stackNum) = pop the top element from the stack numbered stackNumtop(stackNum) = shows the topmost element of the sta

Design and Implement Special Stack Data Structure | Added Space Optimized Version

Question: Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1). To implement SpecialStack, you should only use standard Stack data structure

Top 50 Problems on Stack Data Structure asked in SDE Interviews

A Stack is a linear data structure in which the insertion of a new element and removal of an existing element takes place at the same end represented as the top of the stack. To learn about Stack Data Structure in detail, please refer to the Tutorial on Stack Data Structure. Given below are the most frequently asked interview questions on Stack:Eas

Basic Operations in Stack Data Structure with Implementations

In order to make manipulations in a stack, there are certain operations provided to us for Stack, which include: push() to insert an element into the stackpop() to remove an element from the stacktop() Returns the top element of the stack.isEmpty() returns true if the stack is empty else false.size() returns the size of the stack.In this post, we w

Stack Permutations (Check if an array is stack permutation of other)

A stack permutation is a permutation of objects in the given input queue which is done by transferring elements from the input queue to the output queue with the help of a stack and the built-in push and pop functions. The rules are: Only dequeue from the input queue.Use inbuilt push, and pop functions in the single stack.Stack and input queue must

Reversing a Stack with the help of another empty Stack

Given a Stack consisting of N elements, the task is to reverse the Stack using an extra stack. Examples: Input: stack = {1, 2, 3, 4, 5} Output: 1 2 3 4 5 Explanation: Input Stack: 5 4 3 2 1 Reversed Stack: 1 2 3 4 5 Input: stack = {1, 3, 5, 4, 2} Output: 1 3 5 4 2 Approach 1: Follow the steps below to solve the problem: Initialize an empty stack.Po

Sort a stack using a temporary stack

Given a stack of integers, sort it in ascending order using another temporary stack. Examples: Input : [34, 3, 31, 98, 92, 23] Output : [3, 23, 31, 34, 92, 98] Input : [3, 5, 1, 4, 2, 8] Output : [1, 2, 3, 4, 5, 8] Recommended PracticeSort a stackTry It! Algorithm: Create a temporary stack say tmpStack.While input stack is NOT empty do this: Pop an

Find maximum in stack in O(1) without using additional stack in Python

The task is to design a stack which can get the maximum value in the stack in O(1) time without using an additional stack in Python. Examples: Input: Consider the following SpecialStack 16 –> TOP29151918When getMax() is called it should return 29, which is the maximum element in the current stack. If we do pop two times on stack, the stack becom

Is array a Data Type or Data Structure?

What is Data Type? In computer programming, a data type is a classification of data that determines the type of values that can be stored, manipulated, and processed. It tells the computer what kind of data a particular variable or constant can hold, and what operations can be performed on that data. Common data types include integers, floating-poi

Data Structure Alignment : How data is arranged and accessed in Computer Memory?

Data structure alignment is the way data is arranged and accessed in computer memory. Data alignment and Data structure padding are two different issues but are related to each other and together known as Data Structure alignment. Data alignment: Data alignment means putting the data in memory at an address equal to some multiple of the word size.

Difference between data type and data structure

Data Type A data type is the most basic and the most common classification of data. It is this through which the compiler gets to know the form or the type of information that will be used throughout the code. So basically data type is a type of information transmitted between the programmer and the compiler where the programmer informs the compile

Data Structures | Stack | Question 1

Following is C like pseudo code of a function that takes a number as an argument, and uses a stack S to do processing. void fun(int n) { Stack S; // Say it creates an empty stack S while (n > 0) { // This line pushes the value of n%2 to stack S push(&S, n%2); n = n/2; } // Run while Stack S is not empty while (!isEmpty(&S)) printf("

Data Structures | Stack | Question 2

Which one of the following is an application of Stack Data Structure? (A) Managing function calls (B) The stock span problem (C) Arithmetic expression evaluation (D) All of the above Answer: (D) Explanation: See http://en.wikipedia.org/wiki/Stack_(abstract_data_type)#Applications

Data Structures | Stack | Question 3

Which of the following is true about linked list implementation of stack? (A) In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end. (B) In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning. (C) Both of t

Data Structures | Stack | Question 4

Consider the following pseudocode that uses a stack C/C++ Code declare a stack of characters while ( there are more characters in the word to read ) { read a character push the character on the stack } while ( the stack is not empty ) { pop a character off the stack write the character to the screen } What is output for input \"geeksquiz\"? (A) gee

Data Structures | Stack | Question 5

Following is an incorrect pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced: C/C++ Code declare a character stack while ( more input is available) { read a character if ( the character is a \'(\' ) push it on the stack else if ( the character is a \')\' and the stack is not empty ) pop a chara

Data Structures | Stack | Question 6

The following postfix expression with single digit operands is evaluated using a stack: 8 2 3 ^ / 2 3 * + 5 1 * - Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are: (A) 6, 1 (B) 5, 7 (C) 3, 2 (D) 1, 5 Answer: (A) Explanation: The algorithm for evaluating any postfix expression is fairly

Data Structures | Stack | Question 7

Let S be a stack of size n >= 1. Starting with the empty stack, suppose we push the first n natural numbers in sequence, and then perform n pop operations. Assume that Push and Pop operation take X seconds each, and Y seconds elapse between the end of one such stack operation and the start of the next operation. For m >= 1, define the stack-l

Data Structures | Stack | Question 8

A single array A[1..MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (topl< top 2) point to the location of the topmost element in each of the stacks. If the space is to be used efficiently, the condition for “stack full” is (GATE CS 2004) (A) (top1 = MAXSIZE/2) and (top2 = MA

Difference Between Stack and Queue Data Structures

In computer science, data structures are fundamental concepts that are crucial for organizing and storing data efficiently. Among the various data structures, stacks and queues are two of the most basic yet essential structures used in programming and algorithm design. Despite their simplicity, they form the backbone of many complex systems and app

Applications of Queue Data Structure

Introduction : A queue is a linear data structure that follows the "first-in, first-out" (FIFO) principle. It is a collection of elements that supports two primary operations - enqueue and dequeue. In the enqueue operation, an element is added to the back of the queue, while in the dequeue operation, an element is removed from the front of the queu

Data Structure for a single resource reservations

Design a data structure to do reservations of future jobs on a single machine under following constraints. Every job requires exactly k time units of the machine. The machine can do only one job at a time. Time is part of the system. Future Jobs keep coming at different times. Reservation of a future job is done only if there is no existing reserva

A data structure for n elements and O(1) operations

Propose a data structure for the following: The data structure would hold elements from 0 to n-1. There is no order on the elements (no ascending/descending order requirement) The complexity of the operations should be as follows: Insertion of an element – O(1) Deletion of an element – O(1) Finding an element – O(1) We strongly recommend to minimiz

Tango Tree Data Structure

INTRODUCTION:' Tango Tree is a data structure for efficient dynamic connectivity and range minimum/maximum query on a set of elements. It is a type of balanced binary search tree that uses finger trees as the underlying data structure to achieve fast and efficient operations. The Tango Tree is designed to support both fast insertions and deletions

Applications of Graph Data Structure

A graph is a non-linear data structure, which consists of vertices(or nodes) connected by edges(or arcs) where edges may be directed or undirected. In Computer science graphs are used to represent the flow of computation.Google maps uses graphs for building transportation systems, where intersection of two(or more) roads are considered to be a vert

Which data structure is used by Map?

What is a Map? Before learning the data structure used by a map, let us have an overlook of map. Map is the part of the STL library that stores key value pairs in it and no two values have the same keys but the different keys can store similar values. The map stores keys in sorted order. These are some functions which map uses with their Time Compl

Applications of linked list data structure

A linked list is a linear data structure, in which the elements are not stored at contiguous memory locations. The elements in a linked list are linked using pointers as shown in the below image: Applications of linked list in computer science:Implementation of stacks and queuesImplementation of graphs: Adjacency list representation of graphs is th

Top 50 Problems on Heap Data Structure asked in SDE Interviews

A Heap is a special Tree-based Data Structure in which the tree is a complete binary tree. Generally, heaps are of two types: Max-Heap and Min-Heap. To know more about this Data Structure in-depth refer to the Tutorial on Heap Data-Structure. Given below are the most frequently asked interview questions on Heaps: Easy Interview Questions on Heap D

Article Tags :

Stack
DSA

Practice Tags :

Stack