Slide 1
Data Structures and Abstractions
Stacks
Lecture 21
*
Temporary Storage
When processing it is often necessary to put data into temporary storage.
This can happen, for example, when:
processing events in an event-driven OS;
processing email in and out of a server;
scheduling jobs on a main-frame;
doing calculations;
sorting or merging;
The most common data structures for temporary storage are stacks, queues, heaps and priority queues.
*
Stacks
Stacks are ADS that emulate, for example, a stack of books: you can only put things on or take them off at the top.
There are only two operations allowed on a stack:
Push (something on to it)
Pop (something off it)
Plus two query methods:
Empty ()
Full () // optional
Since the last thing on is the first thing off, they are known as LIFO (Last In, First Out) data structures, or sometimes FILO (First In, Last Out).
In essence, a stack reverses the order of the data.
*
Stack Implementation
Stacks can be implemented any way you want, the encapsulation of the container used ensures that it does not matter.
As long as it only has Push, Pop, Empty and (optionally) Full, then it is a stack.
Most commonly they are implemented using arrays, lists or an STL structure.
If none of these exactly fit the required abstraction that we are after, they should be encapsulated inside our own Stack. [1]
*
1.
The STL stack does fit a particular abstraction of stack which specifies that pop() just deletes the item at the top of the stack. If data from the top of the stack is needed then top() is used. top() doesn’t delete data.
The key difference in the STL stack and the Stack that is described in the lecture notes (which encapsulates the STL stack) is the abstraction that we have for the pop operation. The lecture notes Stack has pop which not only deletes the element from the stack, but also returns the data element to the client. This is a more intuitive concept of what a stack is. Also, Stack returns a Boolean indicating the success or failure of an operation.
Error Conditions for Stacks
If you try to Push() onto a stack that has no free memory, then you get overflow.
If you try to Pop() from an empty stack then you have underflow.
So Push() and Pop() return a boolean to indicate if one of these errors has occurred.
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
m_top
m_top
NULL
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(10)
10
m_top
NULL
m_top
m_top
10
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(1)
10
1
m_top
NULL
m_top
m_top
10
1
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(23)
10
1
23
m_top
NULL
m_top
m_top
10
1
23
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Pop (num)
10
1
23
m_top
NULL
m_top
m_top
num
23
10
1
23
*
Stack Example (Animation)
* of 37
Array Implementation
Linked List Implementation
Pop (num)
10
1
m_top
NULL
m_top
m_top
num
1
10
1
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Pop (num)
10
m_top
NULL
m_top
m_top
num
10
10
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Pop (num)
m_top
NULL
m_top
num
UNDERFLOW
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(12)
12
m_top
NULL
m_top
m_top
12
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(34)
12
34
m_top
NULL
m_top
m_top
12
34
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(23)
10
1
23
m_top
NULL
m_top
m_top
10
1
23
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(36)
10
1
23
36
m_top
NULL
m_top
m_top
10
1
23
36
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(98)
10
1
23
36
98
m_top
NULL
m_top
m_top
10
1
23
36
98
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(8)
10
1
23
36
98
8
m_top
NULL
m_top
m_top
10
1
23
36
98
8
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(76)
10
1
23
36
98
8
76
m_top
NULL
m_top
m_top
10
1
23
36
98
8
76
*
Stack Example (Animation)
Array Implementation
Linked List Implementation
Push(66)
10
1
23
36
98
8
76
m_top
NULL
m_top
OVERFLOW
END
10
1
23
36
98
8
76
66
*
Array Push Algorithm
PUSH (DataType data): boolean
IF m_top >= ARRAY_SIZE-1
return FALSE
ELSE
Increment m_top
Place data at position m_top
return TRUE
ENDIF
END Push
*
Array Pop Algorithm
POP (DataType data): boolean
IF m_top < 0
return FALSE
ELSE
data = data at position m_top
Decrement m_top
return TRUE
ENDIF
END Pop
*
Linked List Push Algorithm
PUSH (DataType data): boolean
IF there is memory on the heap
Get newNode from the heap
Put data into the newNode
IF m_top is NULL
m_top = newNode
ELSE
newNode.next = m_top
m_top = newNode
ENDIF
return TRUE
ELSE
return FALSE
ENDIF
END Push
m_top
NULL
76
66
*
Linked List Pop Algorithm
POP (DataType data): boolean
IF m_top == NULL
return FALSE
ELSE
data = m_top.data
oldNode = m_top
m_top = oldNode.next
release oldNode memory
oldNode = NULL
return TRUE
ENDIF
END Pop
m_top
NULL
76
66
oldNode
*
Using the STL
The other possibility is to use one of the STL structures.
If using a vector or list, then the algorithms above barely change.
However, remember that the structure must still be encapsulated in a class, otherwise it will not have just the Pop() and Push() that it is supposed to have.
Finally, there is the STL stack class, (requiring
STL stack is an adapted STL container (container adapter) for special use as a stack. No iterators are provided.
However, even this must be encapsulated if it does not conform to our abstraction of what a stack should be (pointed out earlier and see slide notes from earlier). [1]
*
[1]
See the reference book, Introduction to Algorithms section on “Stacks and Queues” in the chapter on “Elementary Data Structures” (10).
You will see that how removed the STL stack is from the abstract stack. We want to deal with the highest level of abstraction. This means
that you encapsulate a STL data structure.
Features of the STL stack which don’t fit in with our Abstraction
Its pop() method, only removes the data, it does not pass it back to the calling method.
In fact there is a top() method which returns the data (by reference) at the top of the stack.
Neither pop(), top() nor push() return a boolean: overflow and underflow must be checked separately.
Given the abstraction we are after, even the STL stack must be encapsulated.
*
Stack Header File using STL stack
// Stack.h
//
// Stack class
// Version
// Nicola Ritter
// modified smr
//——————————————-
#ifndef MY_STACK
#define MY_STACK
//——————————————-
#include
#include
using namespace std;
*
template
class Stack
{
public:
Stack () {};
~Stack () {};
bool Push(const DataType &data);
bool Pop (DataType &data);
bool Empty () const {return m_stack.empty();}
private:
stack
};
*
//——————————————-
// It is a template, so we have to put all the code
// in the header file
//——————————————-
template
bool Stack
{
bool okay = true;
try
{
m_stack.push(data);
}
catch (…)
{
okay = false;
}
return okay;
}
*
//——————————————-
template
bool Stack
{
if (m_stack.size() > 0)
{
data = m_stack.top();
m_stack.pop();
return true;
}
else
{
return false;
}
}
//——————————————-
#endif
*
Simple (and useless) Example of Stack Use
// StackTest.cpp
//
// Tests Stack classes
//
// Nicola Ritter
// Version 01
// modified smr
// Reverse a string
//
//——————————————————–
#include
#include
#include “Stack.h“ //Our stack
using namespace std;
*
//——————————————————–
typedef Stack
void Input (string &str);
void Reverse (const string &str, CharStack &temp);
void Output (CharStack &temp); // const – check what it
//does first??
//——————————————————–
int main()
{
string str;
CharStack temp;
Input (str);
Reverse (str, temp); [1]
Output (temp);
cout << endl;
return 0;
}
*
[1]
Illustrates concepts but program design can be improved.
For example, Reverse(..), should reverse the string, not return a stack object.
How would you refactor so that the stack is used only inside Reverse(..). What is returned
is the reversed string which is then printed by the main routine.
So the code in main becomes
Input (str);
cout << Reverse (str) << endl;
//--------------------------------------------------------
void Input (string &str)
{
cout << "Enter a string, then press
getline(cin,str);
}
//——————————————————–
void Reverse (const string &str, CharStack &temp)
{
bool okay = true;
for (int index = 0; index < str.length() && okay; index++)
{
okay = temp.Push(str[index]);
}
}
*
//--------------------------------------------------------
void Output (CharStack &temp) // would const work?
{
bool okay;
char ch;
cout << "Your string reversed is: ";
okay = temp.Pop(ch);
while (okay)
{
cout << ch;
okay = temp.Pop(ch);
}
cout << endl;
}
//--------------------------------------------------------
*
Screen Output
Enter a string, then press
Your string reversed is: gnirts a si sihT
Press any key to continue . . .
* of 37
*
Advantages of Implementations
It is assumed for each of the containers below, that our Stack encapsulates it.
Array Linked List list/vector/deque STL stack
Easy to code Full memory control Easy to code Easier to code compared to all the others.
Memory ‘never’ runs out.
Memory ‘never’ runs out. Memory ‘never’ runs out.
*
Disadvantages of Implementations
It is assumed for each of the containers below, that our Stack encapsulates it.
Array Linked List list/vector/deque STL stack
Can run out of space easily. More difficult to code as it uses pointers. Excess code sitting ‘behind’ the implementation. Excess code sitting ‘behind’ the implementation.
Only available in with some languages.
e.g C++ has STL, Java has Java collections framework Only available with some languages.
e.g. C++ has STL, Java has Java collections framework
*
Readings
Textbook: Stacks and Queues, entire section on Stacks.
For a more details of Stacks with some level of language independence, see the reference book, Introduction to Algorithms section on “Stacks and Queues” in the chapter on “Elementary Data Structures”. You will see that how removed the STL stack is from the abstract stack. We want the abstract level – see earlier lecture notes on level of abstractions.
Textbook: Standard Template Library, section on Container Adapters
Library Ereserve: Deitel & Deitel, C++ how to program [ECMS]. Chapter 15 part A. [1]
[1]
The List data structure shown here is a little bloated. It has List::Print(). It might be convenient for console ouput, but it is not good for reuse. What if you wanted output in a GUI?
*