CS计算机代考程序代写 data structure Java c++ algorithm Slide 1

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 ), which is obviously the best STL class to use your Stack class.
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 m_stack; // encapsulated STL stack
};

*

//——————————————-
// It is a template, so we have to put all the code
// in the header file
//——————————————-

template
bool Stack::Push(const DataType &data)
{
bool okay = true;
try
{
m_stack.push(data);
}
catch (…)
{
okay = false;
}

return okay;
}

*

//——————————————-

template
bool Stack::Pop(DataType &data)
{
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 CharStack;

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 : This is a string
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?
*