Scribd
Upload
4 views10 pages

Stack Data Structure Overview and Implementation

The document provides an overview of stacks, a data structure characterized by LIFO (Last In First Out) operations, where items are added and removed from the top. It outlines various operations on stacks, such as push, pop, and checking if the stack is empty or full, and discusses applications in parsing code, function tracking, and sorting. Additionally, it includes implementation details for stacks using arrays and linked lists, along with example code snippets.

Uploaded by

siddojigariarpi6979
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views10 pages

Stack Data Structure Overview and Implementation

The document provides an overview of stacks, a data structure characterized by LIFO (Last In First Out) operations, where items are added and removed from the top. It outlines various operations on stacks, such as push, pop, and checking if the stack is empty or full, and discusses applications in parsing code, function tracking, and sorting. Additionally, it includes implementation details for stacks using arrays and linked lists, along with example code snippets.

Uploaded by

siddojigariarpi6979
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Data Structures

Stack
Introduction
Stack: A stack is a basic data structure (An ADT) in which insertion and deletion of
items takes place at one end called top of the stack.

The basic implementation of stack is also called LIFO (Last In First Out)

It is a list like structure, but elements can be inserted or deleted from only
one end. It makes stack less flexible than lists.

Many applications need simpler stack rather than lists.


Operations on Stack
Push
Adds an item onto the stack at the top.
Top
Returns the last item pushed onto the stack.
Pop
Removes the most-recently-pushed item from the stack.
is-empty
True if no more items can be popped and there is no top item.
is-full
True if no more items can be pushed.
get-size
Returns the number of elements on the stack.
Applications of Stack
 Parsing code (Compilers)
 Matching parenthesis

 XML (e.g., XHTML)

 Tracking function calls

 Convert decimal to binary

 Infix, postfix and prefix conversions

 Quick Sort

 The redo and Undo operations in editors


Implementation of Stack
1. Using Single Linked Lists

2. Using Arrays
Implementation of Stack using arrays

#define MAX 10

struct stack

int arr[MAX] ;

int top ;

};
Implementation of Stack using arrays
void main( ) i = pop ( &s ) ;
{ printf ( "\n\nItem popped: %d", i ) ;
struct stack s ;
int i ; i = pop ( &s ) ;
initstack ( &s ) ; printf ( "\nItem popped: %d", i ) ;

push ( &s, 11 ) ; i = pop ( &s ) ;


push ( &s, 23 ) ; printf ( "\nItem popped: %d", i ) ;
push ( &s, -8 ) ;
push ( &s, 16 ) ; i = pop ( &s ) ;
push ( &s, 27 ) ; printf ( "\nItem popped: %d", i ) ;
push ( &s, 14 ) ;
push ( &s, 20 ) ; i = pop ( &s ) ;
push ( &s, 39 ) ; printf ( "\nItem popped: %d", i ) ;
push ( &s, 2 ) ;
push ( &s, 15 ) ; }
push ( &s, 7 ) ;
Implementation of Stack using arrays

/* intializes the stack */


void initstack ( struct stack *s ) /* removes an element from the stack
{ */
s -> top = -1 ; int pop ( struct stack *s )
} {
int data ;
/* adds an element to the stack */ if ( s -> top == -1 )
void push ( struct stack *s, int item ) {
{ printf ( "\nStack is empty." ) ;
if ( s -> top == MAX - 1 ) return NULL ;
{ }
printf ( "\nStack is full." ) ; data = s -> arr[s -> top] ;
return ; s -> top-- ;
} return data ;
s -> top++ ; }
s -> arr[s ->top] = item ;
}
Assignment
Write a C Program implements linked list as a stack
Write a C Program implements array as a stack.

You might also like