Scribd
Upload
37 views13 pages

Sesion 2

This document discusses stacks, including: - Stacks are linear data structures that use LIFO (Last In First Out) access, allowing insertion and deletion from one end. - Basic stack operations are Push, which adds an item to the top, and Pop, which removes an item from the top. - Other operations include initializing an empty stack, viewing the top item, checking if empty, and getting the size. - Stacks can be implemented using a linked list with nodes containing an element and a link to the next node. - Example C++ implementations of stack operations like Push, Pop, Top, and Size are provided.

Uploaded by

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

Sesion 2

This document discusses stacks, including: - Stacks are linear data structures that use LIFO (Last In First Out) access, allowing insertion and deletion from one end. - Basic stack operations are Push, which adds an item to the top, and Pop, which removes an item from the top. - Other operations include initializing an empty stack, viewing the top item, checking if empty, and getting the size. - Stacks can be implemented using a linked list with nodes containing an element and a link to the next node. - Example C++ implementations of stack operations like Push, Pop, Top, and Size are provided.

Uploaded by

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

Algorithms and Data Structures

Session 2 - Stacks

Esperanza Johnson
Stacks

• Introduction
• Stack Specification
• Stack Implementation
• Stacks in C++
• Tasks
Description

• Stacks are a linear data structure


• Can be implemented with a dynamic or a static model
• Insertion and deletion of elements is done from one end of the stack
• LIFO access (Last In, First Out)
• cout -> E, D, C, B, A E
D D top
top C
C C
top B
B B
B top A
A A
A top A
Stack Specification

• Two basic operations


• Push: adds items to the top of the stack
• Pop: removes items from the tops of the stack. Error if stack is empty.

Top
Stack Specification II

• Other operations:
• Stack or init: creates an empty stack
• Top: returns the element at the top without removing it
• isEmpty: returns if the stack is empty or not
• Size: returns number of items in stack
Stack Specification III

• Formal (algebraic, syntactic) specification of Stack ADT (Abstract Data


Type)
• Operations:
• Init :  stack
• Push : stack x el  stack
• Pop : stack  stack
• Top : stack  element
• isEmpty: stack  Boolean
• Size : stack  Integer
Implementation

• Internally this can be seen as implemented with a singly linked list


• This is a sequence of nodes that stores:
• An element
• A link to the next node next

element Node
top

e3 e2 e1 e0 null
Implementation I

Pop(){ Push(element){
if (isEmpty())  Error aux = new node (element, top)
else{ top = aux
size = size +1
element = get_element_top
}
top = get_next_element_of_top
size = size-1
Top(){
return element if (isEmpty())  Error
} else
} return top
}
Implementation II

Size(){
return size
}

isEmpty(){
if(size == 0) OR if top == null
}
Implementation II

Push(element){
aux = new node (element, top)
top = aux
size = size +1
}

Top(){
if (isEmpty())  Error
else
return top
}
Implementation in C++

• #include <stack>
• Operations:
• (constructor)
• Empty
• Size
• Top
• Push
• Emplace: Construct and Insert element
• Pop
• Swap: Swaps contents of one stack with another
Tasks

• What is the output of: push(5), push(10), top(), push(3), pop(), pop(),
push(8), push(9), top()??
• Create an empty stack and fill it with 5 numbers the user asks for, then
print out the result.
• Write a function that will invert the stack without using an additional data
structure (no aux stacks or arrays)
• Extra: Develop an algorithm that uses a stack to evaluate if the opening
and closing symbols of an arithmetic expression match (are balanced).
Useful links

• Stack in C++ [Link]


• Stack Reference C++ [Link]

You might also like