2/5/2018 Stack
Stack
Stack Concept
A stack is a useful data structure in programming. It is just like a pile of plates kept on
top of each other.
Think about the things you can do with such a pile of plates
Put a new plate on top
Remove the top plate
https://www.programiz.com/dsa/stack 1/6
2/5/2018 Stack
If you want the plate at the bottom, you have to rst remove all the plates on top. Such
kind of arrangement is called Last In First Out - the last item that was placed is the rst
item to go out.
Stack in Programming Terms
In programming terms, putting an item on top of the stack is called "push" and removing
an item is called "pop".
In the above image, although item 2 was kept last, it was removed rst - so it follows the
Last In First Out(LIFO) principle.
We can implement stack in any programming language like C, C++, Java, Python or C#, but
the speci cation is pretty much the same.
Stack Speci cation
A stack is an object or more speci cally an abstract data structure(ADT) that allows the
following operations:
Push : Add element to top of stack
Pop : Remove element from top of stack
IsEmpty : Check if stack is empty
IsFull : Check if stack is full
Peek : Get the value of the top element without removing it
https://www.programiz.com/dsa/stack 2/6
2/5/2018 Stack
How stack works
The operations work as follows:
1. A pointer called TOP is used to keep track of the top element in the stack.
2. When initializing the stack, we set its value to -1 so that we can check if the stack is
empty by comparing TOP == -1 .
3. On pushing an element, we increase the value of TOP and place the new element in
the position pointed to by TOP .
4. On popping an element, we return the element pointed to by TOP and reduce its
value.
5. Before pushing, we check if stack is already full
6. Before popping, we check if stack is already empty
Stack Implementation in programming language
The most common stack implementation is using arrays, but it can also be implemented
using lists.
Here is an implementation using arrays and C programming language.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define MAX 10
struct stack
{
https://www.programiz.com/dsa/stack 3/6
2/5/2018 Stack
int items[MAX];
};
int top;
typedef struct stack st;
void createEmptyStack(st *s)
{
s->top=-1;
}
int isfull(st *s)
{
if (s->top==MAX-1)
return 1;
else
return 0;
}
int isempty(st *s)
{
if (s->top==-1)
return 1;
else
return 0;
}
void push(st *s)
{
Use of stack
Although stack is a simple data structure to implement, it is very powerful. The most
common uses of a stack are:
To reverse a word - Put all the letters in a stack and pop them out. Because of LIFO
order of stack, you will get the letters in reverse order.
In compilers - Compilers use stack to calculate the value of expressions like 2+4/5*(7-
9) by converting the expression to pre x or post x form.
In browsers - The back button in a browser saves all the urls you have visited
previously in a stack. Each time you visit a new page, it is added on top of the stack.
When you press the back button, the current URL is removed from the stack and the
previous url is accessed.
https://www.programiz.com/dsa/stack 4/6
2/5/2018 Stack
Data Structure & Algorithms
Bubble Sort Algorithm
Insertion Sort Algorithm
Selection Sort Algorithm
Heap Sort Algorithm
Merge Sort Algorithm
Stack
Queue
Circular Queue
Linked List
Types of Linked List - Singly linked, doubly linked and circular
Linked List Operations
Tree Data Structure
Tree Traversal - inorder, preorder and postorder
Binary Search Tree(BST)
Graph Data Stucture
DFS algorithm
https://www.programiz.com/dsa/stack 5/6
2/5/2018 Stack
Adjacency List
Adjacency Matrix
Breadth rst search
Kruskal's Algorithm
Prim's Algorithm
Dynamic Programming
Dijkstra's Algorithm
Bellman Ford's Algorithm
Get Latest Updates on Programiz
Enter Your Email
Subscribe
ABOUT
CONTACT
ADVERTISE
Copyright © by Programiz | All rights reserved | Privacy Policy
https://www.programiz.com/dsa/stack 6/6
